Utvärdering av sudokulösare baserade på mänskliga lösningstekniker : En jämförelse med Dancing links som referensalgoritm

Sammanfattning: Syftet med den här rapporten var att undersöka under vilka förutsättningar en regelbaserad algoritm eventuellt skulle kunna vara effektivare 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 flesta 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.