Utvärdering av sudokulösare baserade på mänskliga lösningstekniker
En jämförelse med Dancing links som referensalgoritm
Syftet med den här rapporten var att undersöka under vilka förutsättningar en regelbaserad algoritm eventuellt skulle kunna vara e?ektivare för att lösa sudokupussel än Donald Knuths totalsökningsalgoritm Dancing links. Förutsättningarna som testades var pusselstorlek och pusselsvårighetsgrad. Den regelbaserade lösarens regler implementerades utifrån ett antal vanliga lösningstekniker som människor brukar använda sig av och referenslösaren baserades på Knuths egna pseudokod för algoritmen Dancing links. De två lösarna implementerades i Java och deras respektive körtider för varje pussel plus övrig information om körningen och de testade pusslen sparades. Resultatet visade att den regelbaserade lösaren klarade av att lösa de ?esta pusslen testade i rimlig tid, och de största pusslen med högre svårighetsgrad snabbare än Dancing links. Slutsatsen som kunde dras var att även om det fanns fall då den regelbaserade lösaren var bättre så var den dels besvärligare att implementera och dels sämre för den vanligaste pusselstorleken 9x9, vilket begränsade dess användningsområden.