Change search
ReferencesLink to record
Permanent link

Direct link
Solving Sudoku efficiently with Dancing Links
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]

With this thesis, we hope to motivate software developers to seek out already existing solving algorithms instead of attempting to use a bruteforce algorithm or specialized solving algorithms.The reason for choosing the Sudoku puzzle as a platform to demonstrate this is because it is well known around the world and easy to understand, while the reduction to an exact cover problem provides a challenge. Because of the challenge in the reduction and because we did not find any earlier research which explained in detail how the reduction from a Sudoku puzzle to an exact cover problem is done, we decided to focus on that subject in this thesis. Using our previous knowledge in reduction and the information found during our research, the reduction was eventually solved.Our conclusion is that Dancing Links is an effective solver for the exact cover problem and that a good reduction algorithm can greatly lower the solving time. The benchmarks also indicate that the number of clues in a Sudoku puzzle may not be the deciding factor of its difficulty rating. Since the reduction to an exact cover problem was arguably the hardest part in this thesis, future research can hopefully make use of our detailed explanation of the reduction and use the time saved to explore other topics in more depth, such as the difficulty rating of Sudoku puzzle.

Abstract [sv]

Med denna rapport så hoppas vi motivera mjukvaruutvecklare att sökaefter redan existerande lösningsalgoritmer istället för att försöka använda en brute force-algoritm eller en lösningsalgoritm som är specialiserad på ett specifikt område. Anledningen till att vi valde att använda Sudoku som ett verktyg för att demonstrera detta är för att det är känt runt om i världen och lätt att förstå, men också för att det är svårt att utföra en reducering till ett exakt mängdtäckningsproblem. På grund av utmaningen i reduktionen och eftersom vi inte hittade någon tidigare forskning som detaljerat förklarade hur reduktionen från ett Sudokupussel till ett exakt mängdtäckningsproblem går till, bestämde vi oss för att fokusera kring det i denna rapport. Genom att använda vår tidigare kunskap inom reduktion och med den information vi hittade under informationssökningen kunde vi slutligen lösa reduktionen.Vår slutsats är att Dancing Links är en effektiv lösare till det exakta mängdtäckningsproblemet och att en bra implementerad reduktion kraftigt kan sänka lösningstiden. Mätningarna visar också att antalet ledtrådar i ett Sudokupussel inte behöver vara den avgörande faktorn för sin svårighet.Eftersom reduceringen till ett exakt mängdtäckningsproblem var den svåraste delen i vår rapport så hoppas vi att framtida forskninghar användning av vår genomgång av reduceringen och istället kan använda den tiden till att utforska andra ämnen mer djupgående, som exempelvis svårighetsgraden för Sudokupussel.

Place, publisher, year, edition, pages
2014.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-157551OAI: oai:DiVA.org:kth-157551DiVA: diva2:770655
Examiners
Available from: 2014-12-11 Created: 2014-12-11 Last updated: 2014-12-11Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 228 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: 650 hits
ReferencesLink to record
Permanent link

Direct link