There are several good puzzle solvers online and available, but most of them implement only a few solution-seeking algorithms and then fall back on a ‘brute force’ method. I wanted to see if I could create a solver program that approached puzzles the way a human being would, using multiple algorithms.
Frankly, when I started the programming, I did not realize that there was much beyond naked and hidden singles and thought I would be done with the effort pretty quickly. Only after trying my initial attempts at more complex and diabolical puzzles did I realize that I was in for almost a year’s effort in reading, understanding, programming, and testing ever more complex solution algorithms. I ended up implementing:
1. Naked Single
2. Hidden Single
3. Pointing and Claiming (Locked Candidates)
4. Naked Pair, Triple, Quad
5. Hidden Pair, Triple, Quad
6. X-Wing
7. Y-Wing (aka XY-Wing)
8. XYZ-Wing
9. WXYZ-Wing
10. Swordfish
11. Jellyfish
12. Unique Rectangle (Type 1)
13. Unique Rectangle (Type 2)
14. Unique Rectangle (Type 3)
15. Unique Rectangle (Type 4)
16. Unique Rectangle (Type 5)
17. Hidden Rectangle
These solution algorithms use a classic "candidate-based" approach using an initial build of all candidate entries or each cell that is not initially filled by the input grid. This would be the same approach a ‘human’ would take in identifying all the candidates and making pencil marks.
Since they are so much faster than the chain, Medusa and other approaches, the program tries these iteratively first – and that’s often enough for the simple and easy puzzles.
If the algorithm-based solutions fail (and they do for more complex input puzzles!), the program switches first to "Forcing Chain" algorithms including XY-Chain, X-Chain, Medusa 3_D, Forbidding Chain and Remote Pair and finally to a "Recursive Descent/Backtrack" solution search that is optimized using only the remaining candidates for each attempt made to fill the remaining empty cells. That should work for any legal input puzzle and the ‘brute force’ is ONLY used as a last resort.
The programming was done in C++ on an Arduino Mega 2560 because I needed the large memory capacity. Input is done via numeric keypad and there are two display screens. The first shows the puzzle grid both initially and as it is solved and the second shows each removal of a candidate and placement of a number and the technique that achieved it. The keypad and two screens are built into a clear plastic case so you can see the ‘guts’. The actual computer chip is about ¾” square. The solver goes to sleep after not being used for a while and displays time, date, day of week and temperature.
The input is quite easy with shortcuts to navigate the grid quickly. Navigation includes up, down, next square, and backup/erase. During and after input is complete, you can ask the solver to check for apparent rules compliance before proceeding to solving it.
There are 25 built-in demo puzzles of varying complexity so you can watch the program at work.
Typical solution time is 20 seconds for most puzzles, although really complex puzzles with multiple chain approaches can take longer. There are two Arto Inkala published puzzles built in as demos and they take over 2000 ‘tries’ and 4 minutes each to solve.
Its fun to either run one of the demo puzzles or enter a daily diabolical and let it run, watching the progress, what works and what doesn’t as the solution progresses.
Comments