Building an EFFICIENT Sudoku Solver

Question

Yes, I know this is nothing new and there are many questions already out there (it even has its own tag), but I'd like to create a Sudoku Solver in Java solely for the purpose of training myself to write code that is more efficient.

Probably the easiest way to do this in a program is have a ton of for loops parse through each column and row, collect the possible values of each cell, then weed out the cells with only one possibility (whether they contain only 1 number, or they're the only cell in their row/column that contains this number) until you have a solved puzzle. Of course, a sheer thought of the action should raise a red flag in every programmer's mind.

What I'm looking for is the methodology to go about solving this sucker in the most efficient way possible (please try not to include too much code - I want to figure that part out, myself).

I want to avoid mathematical algorithms if at all possible - those would be too easy and 100% not my work.

If someone could provide a step-by-step, efficient thought process for solving a Sudoku puzzle (whether by a human or computer), I would be most happy :). I'm looking for something that's vague (so it's a challenge), but informative enough (so I'm not totally lost) to get me started.

Many thanks,

Justian Meyer

EDIT:

Looking at my code, I got to thinking: what would be some of the possibilities for storing these solving states (i.e. the Sudoku grid). 2D Arrays and 3D Arrays come to mind. Which might be best? 2D might be easier to manage from the surface, but 3D Arrays would provide the "box"/"cage" number as well.

EDIT:

Nevermind. I'm gonna go with a 3D array.

Barograph

Also, if you go with the "weed out until there's only one possibility left" you'll still not be able to solve some sudokus. There's a good amount of "harder" sudokus where you actually have to perform some sort of search before you can be sure which number to put where (DFS/BFS). Otherwise, looping through each column and so on isn't really -that- horrible or inefficient as long as you set up the data structures accordingly, but as I said, it won't solve -all- sudokus. – Gelatinate

@wasatz: Yeah, I've done a bit of research and found that. However, it looks like so many other people have found more efficient work-arounds that, although I hate to admit it, are way above my level of understanding. – Barograph

@Justian, I did some fast googling and found some recommendations for using the "Dancing Links Algorithm" (en.wikipedia.org/wiki/Dancing_Links). I haven't seen this algorithm before (and I don't really have time to read into it right at this moment) but it looks promising. Maybe something worth having a look at? :) – Gelatinate

@wasatz: Thanks for the link, but that's one of those methods that are "... above my level of understanding" ;). One person even explains it in terms of Java, but I still find it confusing (ocf.berkeley.edu/~jchu/publicportal/sudoku/…). People have consulted the SO community for help explaining it, but from what I have seen, no one has given a solid answer. – Barograph

This is a pretty interesting visualization of the backtracking method: youtube.com/watch?v=JtTThE93WNI&feature=related – Barograph

@Justian Meyer: before reading on very complicated stuff, you probably do want to read on backtracking, which shall always prove to be something valuable for you as a programmer (unless say Dancing links which, honestly, a great many great programmers have never actually used). Solving Sudoku programmatically is the typical example of backtracking. I've got a super fast solver who's recursive method is about 12 lines of code long. That's the beauty of recursivity and backtracking: en.wikipedia.org/wiki/Backtracking – Mayest

@Justian Meyer: Here are a few good starting points: en.wikipedia.org/wiki/Algorithmics_of_sudoku Note that the naive supposedly hard example they're giving that take "45 minutes to solve on a 3 Ghz machine" is solved in 80 seconds by my totally unoptimized backtracking+randomization solver (lauching four solvers in parallels, rotating the board 90 degrees each time + using randomization). I lol'ed when I threw that "hard" example at my tiny solver :) – Mayest

@NoozNooz42: Could I perchance see your source code? As I said, this is just for fun, but I'd like to see what you did with the concept. I tried doing it the long way like wasatz suggested, but my code is already far too long as it is and it only covers two VERY basic sudoku soving strategies. – Barograph

You have conflicting requirements: (1) be simple and easy to understand and (2) be faster than the obvious brute-force methods. I think you must pick one or the other. – Outandout

@finnw: Understandable, as that's often the case with efficient code. I was really hoping for a variety of answers, so I could weigh my options. @everyone: I've received a number of up/down votes for this question. I'd prefer that there be an explanation for the down votes if you're going to so; otherwise, please don't vote at all. There's no way I can understand what single number's supposed to mean. – Barograph

@Justian, I recommend you spend some more time trying to understand the Dancing Links implementation. – Outandout

@finnw: Do you think I would benefit more from learning that over backtracking? (in terms of long-term experience) – Barograph

@Justian, No not long-term, it's just well suited to this kind of problem. – Outandout

@finnw: Since the Dancing Links implementation is not really my solution and learning proper backtracking can help me in the future, is it maybe better that I attempt a Brute Force method? – Barograph

@Justian, you will need backtracking either way, whether you use Dancing Links or brute force. – Outandout

Answer 1

It depends on how you define efficient.

You can use a brute force method, which searches through each column and row, collects the possible values of each cell, then weeds out the cells with only one possibility.

If you have cells remaining with more than one possibility, save the puzzle state, pick the cell with the fewest possibilities, pick one of the possibilities, and attempt to solve the puzzle. If the possibility you picked leads to a puzzle contradiction, restore the saved puzzle state, go back to the cell and choose a different possibility. If none of the possibilities in the cell you picked solves the puzzle, pick the next cell with the fewest possibilities. Cycle through the remaining possibilities and cells until you've solved the puzzle.

Attempt to solve the puzzle means searching through each column and row, collecting the possible values of each cell, then weeding out the cells with only one possibility. When all of the cells are weeded out, you've solved the puzzle.

You can use a logical / mathematical method, where your code tries different strategies until the puzzle is solved. Search Google with "sudoku strategies" to see the different strategies. Using logical / mathematical methods, your code can "explain" how the puzzle was solved.

Punctuality

This is a bit of a better explanation of backtracking (thanks for that), but this still seems like a mess. With your description of backtracking ("... and ATTEMPT TO SOLVE THE PUZZLE ..."), it seems as if the computer is taking a weak statistic and blindly finding it's way down a dark tunnel hoping not to bump into anything. Is there any way I can guide it a bit? – Barograph

@Justian Meyer: Nope. That's why it's called a brute force method. You're only going to do a lot of backtracking on the most logically complex sudoku puzzles. But you do have to code for the possibilities. – Punctuality

I expected as much =/. I'm probably going to have to do a number of these problems myself to decide when and where I apply certain strategies for a better perspective. – Barograph

Answer 2

When I made mine, I thought I could solve every board using a set of rules without doing any backtracking. This proved impossible as even puzzles targeting human players potentially require making a few hypothesis.

So I starting with implementing the basic "rules" for solving a puzzle, trying to find the next rule to implement that would allow the resolution of where it stopped last time. In the end, I was forced to add a brute forcing recursive algorithm, but most puzzles are actually solved without using that.

I wrote a blog post about my sudoku solver. Just read through the "The algorithm" section and you'll get a pretty good idea how I went about it.

http://www.byteauthor.com/2010/08/sudoku-solver/

Klingensmith

Answer 3

Should anyone need a reference Android implementation, I wrote a solution that uses the algorithm from the post above.

Full open-source code here: https://github.com/bizz84/SudokuSolver

Additionally, this solution loads Sudoku Puzzles in JSON format from a web server and posts back the results.

Clabo

Answer 4

You should think about reducing the Sudoku Problem to a SATisfiability problem.

This method will avoid you to think too mathematically but more logically about the AI.

The goal step by step is basically :

* Find all the constraints that a Sudoku has. (line, column, box).
* Write these constraints as boolean constraints.
* Put all these constraints in a Boolean Satisfiability Problem.
* Run a SAT solver (or write your own ;) ) on this problem.
* Transform the SAT solution into the solution of the initial Sudoku.

It has been done by Ivor Spence by using SAT4J and you can find the Java Applet of his work here : http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html.

You can also download directly the Java code from SAT4J website, to see how it look like : http://sat4j.org/products.php#sudoku.

And finally, the big advantage of this method is : You can solve N*N Sudokus, and not only the typical 9*9, which is I think, much more challenging for an AI :).

Rumelia