Solving Sudoku efficiently with Dancing Links
| Autor: | HARRYSSON, MATTIAS, LAESTANDER, HJALMAR |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Text |
| Popis: | 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. 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|