Brute-force sudoku solver: backtracking?

An implementation of a brute-force algorithm to solve Sudoku puzzles fails if a cell is discovered in which placing any of the digits 1-9 would be an illegal move.

The implementation is written in C, with the board represented by a 9x9 array. The solver counts down from 9 until a legal number's reached, and if none can be reached, it outputs a zero in its place.

A zero also represents a cell to be filled in. Here's the output (truncated) if a string of zeros (an empty board) is the input:

9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0

Those last three zeros are there because the values f开发者_如何转开发illed in previously aren't changing. How can I stop the solver from failing like this?

If you would currently put a zero in a spot, instead go back to the previous spot you put a number in and continue to count down till you find another value number for that spot.

For instance, in your example:

9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0

Instead of putting the zero in below the three, you would instead go back and try putting a 6 in below the 4.

don't treat every "move" like the right move. E.g. placing the last 7 seemed ok but makes it so that in the next cell no valid moves are left. So upon hitting the "no move possible" situation, go back, and try the next option. Iterate and you will have your solution.

A better way of course would be to start brute forcing for places with a small set of options left; run through all cells and start brute forcing with the cell with the least number of options left. When starting out with all-zero, you would then end up with

9 8 7 6 5 4 3 2 1
6 5 4 0 0 0 0 0 0
3 2 1 0 0 0 0 0 0

which is legal, without backtracking once.

You can do this by pushing your guesses onto a stack. Every time you end up wanting to output a zero, instead pop your last answer off the board and continue counting from it.

So if you guess 3 in (2,3) and next you're looking at (3,3) and get to zero, go back to (2,3) and try 2, then 1, then pop to before your (2,3) guess, etc.