Change search
ReferencesLink to record
Permanent link

Direct link
Comparison of how common sudoku solving techniques perform when adapted and applied to jigsaw sudokus
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2014 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Sudoku and Jigsaw sudoku are two similar logic puzzles. The goal of the puzzles is to place numbers in a 9*9 grid until certain rules are met. In both Jigsaw sudoku and normal sudoku the numbers 1 to 9 needs to be placed in every row, column and box. The difference between the two puzzles is that in a normal sudoku every box is a symmetric 3*3 square, while in the jigsawv ariant the boxes have irregular, altough still nine cells big, boxes.When implementing algorithms for solving the normal sudoku, it normal touse the fact that all the boxes are symmetric. This will not work for the jigsaw sudoku though.In this report we will investigate the effectiveness of the three most common sudoku solving algorithms Rule Based backtracking, Human-Like solving and Dancing Links and how we arrived at the result that Human-Like solving was,in almost every case, the most effective algorithm for solving both sudoku and jigsaw sudoku.

Abstract [sv]

Sudoku och Jigsaw sudoku är två likartade logik spel som går ut på att placera ut tal enligt vissa regler på en spelplan som har 9*9 rutor. I Både jigsaw sudoku och vanligt sudoku ska talen ett till nio finnas med i varje kolumn, rad och box exakt en gång. Det som skiljer dem åt är att i sudoku är boxarna symmetriska och 3*3 rutor stora medan i jigsaw sudoku har de varierande form av 9 rutor.Vid implementation av algoritmer för lösning av sudoku är det enkelt att använda symmetrin av hur de ser ut, medan det för jigsaw sudoku inte fungerar då boxarna ej är symmetriska.I denna rapport undersöker vi effektiviteterna hos de tre algoritmerna Rule Based backtracking, Human-Like solving och Dancing Link för att visa hur vi kom fram till resultatet att Human-Like solving i nästan alla fall var den effektivare algoritmen både för vanliga sudoku och jigsaw sudoku.

Place, publisher, year, edition, pages
National Category
Computer Science
URN: urn:nbn:se:kth:diva-157490OAI: diva2:770174
Available from: 2014-12-10 Created: 2014-12-10 Last updated: 2015-08-27Bibliographically approved

Open Access in DiVA

fulltext(2118 kB)223 downloads
File information
File name FULLTEXT01.pdfFile size 2118 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 223 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 145 hits
ReferencesLink to record
Permanent link

Direct link