Patrik Berggren och David Nilsson
En studie om Sudokulösningsalgoritmer
Sammanfattning
Den här exjobbsrapporten på kandidatnivå presenterar tre olika lösningsalgoritmer för Sudoku.
Studiens huvudsyfte är att studera lösningsprestanda men analyserar även svårighetsgrad, möjligheter till generering och parallelisering.
Samtliga aspekter studeras för varje algoritm och jämförs även mellan enskilda algoritmer.
De utvalda algoritmerna är backtrack, regelbaserad och Boltzmann-maskiner.
Samtliga mätningar görs på en databas med pussel som har 17 ledtrådar, med vissa anpassningar för Boltzmann-maskiner.
Resultaten presenteras med fördelningar som visar lösningstider för varje algoritm separat.
Slutsatsen är att regelbaserade lösare är effektivast på att lösa Sudokupussel.
En korrelation mellan den regelbaserades och den backtrack-baserade lösares svårighetsrating visas.
Parallelisering visas vara tillämpbart till olika grad för de olika algoritmerna och är enklast att tillämpa på sökbaserade lösare.
Generering konstateras vara lättast att implementera med deterministiska algoritmer som backtrack och rule-based.