A rudimentary puzzle solver practice project
A friend of mine learning Python set out to write an automatic sudoku solver as a practice project;
- The sudoku puzzle is to be provided as an 81-entry long one-dimensional array of integers of numbers ranging from 1-9, where a 0 equals an empty slot.
- The solver, be it complete, should be capable of timing itself for comparison against other potential algorithms.
They planned to go about this by simply brute-forcing every possible combination for the blanks until a solution is found. Hearing of this, however, I proposed a handful of theoretical improvements to one such script:
- Firstly, cycle through all blank spaces on the board, and check which digits are so far yet free to be used for each blank space.
- If any of these blank spaces turn out to only have one potential digit in its current state (a so-called "absolute answer" moving forward), add that to the solution, and try again toimage.png see if the sudoku board, with these newly filled-in digits, allow for any further "absolute answers".
- Once no further "absolute answers" can be found, iterate over the board, much like a traditional brute-force attack, only with the limited set of potential digits previously calculated in the former step.
This method would theoretically greatly improve the performance of such a program, by eliminating much of what we can already surmise is unnecessary.
- 🐍 Python 3 (Developed @ 3.10.6)
That's it! No third-party modules or packages.
Once all the "absolute answers" have been put in place, it's time to iterate over the remaining slots.
- The easy but slow way of doing this would be to simply count all of the empty slots that remain, (eg; 6), and simply iterate from 0 to 999999, putting each digit in a respective remaining spot on the board, and testing every combination. This would work since counting upwards from 0 to any number of digits inherently exhausts every possible combination that can be made with a said count of digits. However, this would get ridiculously slow, as each space would exponentially increase the amount of work needed by a factor of 10; although we might be able to get away with testing 6 empty spaces, meaning iterating from 0 to 999.999, the current board, post "absolute answering", still has 39 empty spaces, meaning we'd have to iterate from 0 to 999999999999999999999999999999999999999, were we generous and said each test took 1 millisecond, that would still leave us with around 34446649029982363315696649029 years of iteration on our hands, and that, simply won't do.
- The better way to do this would be to instead only iterate the digits that are plausible in each blank, meaning if we have a spot we know will only take 2, 5 or 7, there is no need to test it with 1, 3, 4, 6, 8, or 9. If we just keep doing this while iterating through every blank, we should at some point arrive at the last blank with only one fitting digit, we can be sure we've arrived at a valid solution.