Building an EFFICIENT Sudoku Solver

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 state开发者_StackOverflow社区s (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.

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.

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/

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.

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 :).