Subj : Re: Help finishing my sudoku solver
To   : comp.programming
From : websnarf
Date : Tue Jul 19 2005 02:26 pm

Allan Bruce wrote:
> I have made a small program to solve sudoku puzzles.  It attempts to solve
> the puzzle algorithmically which seems to work for most puzzles however I
> have found a few that it cannot solve.  To get around this, I have also
> added a brute-force method to try and solve the problem but it doesnt quite
> seem to work, it is very close though.  The method works by trying the first
> non-set cell and setting it to its lowest value then recursing to the next
> cell.  If a cell that is encountered that cant be set is found then the
> recursion backtracks.
>
> I have put my code on my website:
> http://allanbruce.redirectme.net/~allan/SudokuSolver.zip
>
> It has the source, and two boards.  testboard2.txt works fine as it doesnt
> need the brute-force attack, however testboard.txt requires the brute-force
> method.  I have given the solution to testboard too, and I have a line in
> the source (SudokuBoard.java#185) which sees when one particular cell is set
> to the value it should be however this never gets attempted.  Can anybody
> tell me where I am going wrong?  I am so close.

No idea, but you can check your code against mine if you like:

    http://www.pobox.com/~qed/sudoku.zip

It has no problems solving the testboard2.txt puzzle.

Some people have claimed that brute force is generally never required
to solve sudokus.  I don't know if that's true -- I have tried to solve
many by hand and have not yet encountered one than stumped me, and I
certainly am not using brute force search in my head.

My program does not use all the techniques that I use myself, and thus
has a weak brute force solver in it (that works.)  The most important
thing about my brute force solver is that it is not recursive at all,
and also is used to check for non-uniqueness errors in the puzzle
(since at least one newspaper puzzle was published with exactly this
sort of error in it.)

So in theory there could be sudokus my program currently doesn't solve,
however I am currently unaware of any.  Besides, making the fully
recursive brute force trial and error routine would be fairly
straightforward, but is likely overkill.  It would probably be better
to incorporate more deduction routines.  In this way, the program could
also be extended to measure the "difficulty" of a puzzle by the the
complexity of the techniques used to solve it.

-- 
Paul Hsieh
http://www.pobox.com/~qed/

.