For my AI class in the second half of 2009, we were given a project where we had to solve a single sudoku problem using one of a few problem space-searching algorithms. I decided to go a little further and create a general solver.
I started initially with an implementation of an A* algorithm. This was surprisingly easy to get working. Unfortunately, writing an A* algorithm requires you to be able to evaluate all the children you currently have generated via a heuristic that tells you how good or bad that child is. This can be great if you already know the solution, or what goal state you want to reach, but for solving a problem with an unknown goal state it’s awfully hard to write an admissable heuristic.
Why? Well, how do you know which Sudoku board is good and which is bad? Is it some combination of how many rows/columns/boxes you’ve filled? Or does it favor just filling in a box and then moving onto the next one? I tried many heuristics with little to no luck. Well, I guess they would technically work in the long run, but when the search space is on the order of billions, you don’t want a program that will ‘technically work in the long run.’
So, after about 48 hours of aggregate coding, I tossed it. I tossed it all in the trash and started over. Sometimes you just have to realize you’re on a sinking ship.
What I did next was a sort of Depth-First-Search with many modifications. The search would generate only a ‘best child’ of the current state. If there was a cell I could definitely say had only one possible number in its list of possibilities, that was the best child and would become the next board. But it’s not that easy.
If it was that easy, I wouldn’t need a tree structure, I could just iteratively solve the board. Given enough logic programmed into the puzzle, you could do just that, but this project was about search spaces.
I programmed in some basic logic, all the way out to Naked Twins Exclusions (thanks to Sudoku Dragon for greatly aiding me in my understanding of Sudoku). Then I would run the DFS to generate a best child. On all easy and most medium puzzles, this solver doesn’t have to make any guesses and simply generates a straight-shot solution in milliseconds. But on harder puzzles there just isn’t enough logic programmed in to narrow down a cell to just one possibility every time. So I guessed.
I had the program take the most optimal guess with the highest probability of success. That is, cells with less #s in their possibility lists were more optimal. (p(0.5) * p(0.5) > p(0.25) * p(0.3)) Over time, taking guesses on cells less #s in their possibility lists would have higher probability of success compared to cells with more #s.
But the guesses obviously aren’t always right. Sometimes the search tree makes a series of guesses leading to a solution that is invalid. Here, we need to backtrack. I used the Ariadne’s Thread technique for backtracking, which is just a fancy way of saying that I track from which states I make a guess, and when the guess results in a wrong answer, I go back up the tree to the last parent that made a guess, and make a new guess on that state. Rinse and repeat, going up and down the tree until a solution is found.
But my implementation wasn’t that pretty to begin with. First of all, I just didn’t have time to write a user interface before the project was due. The motivation for that came from the need to give my mother something for her birthday. She loves Sudoku, so I thought I would give her a solver. Her main gripe with most online solvers is that they don’t show her the steps they used (the intermediate boards) to come to a solution.
So I tracked all the intermediate boards between start and finish, and have a little feature in the bottom right corner where the user can scroll through all the intermediate boards. But like I said, the solver sometimes makes guesses, so I had to output when it took a guess or else my mom would be really lost.
The final user interface is rendered using openGL. An interesting thing to note is that openGL doesn’t natively support buttons so I created a button class from scratch. I think they turned out fairly well!
The user enters in each number by left clicking to increase the cell value and right clicking to decrease (this is so the user clicks a maximum of 5 times in any one cell to get to the desired number). The answer #s are filled in and rendered in blue to be easily distinguished. If the solver can’t find a solution after a short while, it backs out and tells the user it has failed (this happens, although rarely).
I’d say this is one of my best self-motivated projects to date. All the time and effort was worth it to have my mom enjoy it down the road.
(Note: If you would like a copy of this solver, I would be happy to provide one! Find my e-mail address on my ‘About Me’ page)