Sudoku Solving in a Snap

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.

Here’s my program solving the infamous ‘Al Escargot’ Sudoku Puzzle, famed to be the ‘most difficult’ puzzle in existence.

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)

Advertisements

Tags:

8 Responses to “Sudoku Solving in a Snap”

  1. Scott Yelvington Says:

    listen dude, as awesome as this is. you’re going about this whole thing all wrong. as far as I’ve read EVERYONE IS! but I haven’t read all too far because I just learned sudoku like 3 days ago haha :). but it didn’t take me long to realize guessing and search trees are a load of horse shit. a sudoku puzzle by definition has only one solution. I did some chess engine programming and chess search engines are N based searches where the depth is unknown. sudoku has defined parameters so the N based search makes no sense here! if you’re guessing or your program is guessing then you’ve already gone in the wrong direction. It’s about simple deductive reasoning. Like I said, I started sudoku 3 days ago and in 3 days I came up with all the tricks I needed to solve the hardest problems in the average puzzle book in about 25 minutes. I took a stab at Al Escargot this afternoon using pen and paper only and after failing once (due to bad penmanship) and losing an hour and a half I threw everything away and started blank. the second shot I succeeded in 2hours 2 minutes and 53ish seconds. I didn’t make a single guess once. Don’t guess, develop an algorithm! I did and I bet if I or someone else fine tunes the process it could even be a web based solver with minimal processor footprint.

    • gieseanw Says:

      Scott,
      You couldn’t be more right! This project was part of an AI project on searching. the DFS variation I used was mostly to demonstrate this concept. If I really wanted to, I could code in logic (maybe even using Donald Knuth’s Dancing Links implementation of his Algorithm X!) that would definitely solve it every time! Being lazy, I just reused my solver from the AI project and built a GUI around it. Thanks for the interest, and very thorough comment.
      -Andy

    • gieseanw Says:

      Well Scott, you did it, you convinced me to return to the Sudoku solver and rebuild the logic so every board is solvable. I’m attempting to implement Knuth’s Algorithm X with his Dancing Links data structure. Hopefully I’ll have it done in a week or so.

      -Andy

      • Scott Yelvington Says:

        right on man! Cant wait to see your results!

      • Scott Yelvington Says:

        awesome dude! what OS did you code it on? or is it web based? if it’s web based I’d worship you forever haha. I just started programming on the mac where I used to be a web guy and if it’s mac, again, I’d worship you forever. but not as much as a server side script haha. you rule dude and I can’t wait to see your results!

        • gieseanw Says:

          It’s all C++ code, coded in Visual Studio 2008 on a laptop running Windows XP. I’ll definitely post all the code with many comments if you want to follow. There’s a few tricky bits, but overall the algorithm is fairly easy to follow. At the moment it just runs in the console window (no GUI like the last program), but it’s wicked fast (hardest sudokus I could find all solved in a few milliseconds).

  2. Solving Sudoku, Revisited « Andy G's Blog Says:

    […] to Scott Y’s comments in my article regarding a Sudoku Solver I wrote as part of an AI project, I decided to write a real solver that […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: