Agility sudoku solver: rollback?

Question

Implementing brute force algorithms to solve Sudoku puzzles fails if a cell is found in which any of the numbers 1–9 is placed will be an illegal step.

The implementation is written in C with a board represented by a 9x9 array. The solver counts from 9 until a legal number is reached, and if not one of them is reached, he will put zero in place.

Zero also represents a cell that must be filled. Here's the output (truncated) if the string of zeros (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, because the values ​​filled in earlier do not change. How can I stop the solver from crashing like this?

Answer 1

If you applied zero to a spot, instead go back to the previous place where you put the number and continue to count down until you find another value for this place.

For example, in your example:

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

Instead of setting zero below three, you will come back instead and try to put 6 below 4.

Answer 2

Do not treat every “move” as the right move. For instance. the placement of the last 7 seemed normal, but makes it such that there are no valid moves left in the next cell. Therefore, having hit the “no movement” situation, go back and try the next option. Iterate and you will have your decision.

, , ; . all-zero,

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

, .

Answer 3

You can do this by pushing your guesses onto the stack. Each time you end up wanting to get zero, instead lay your last answer off the board and keep reading it.

So, if you guess 3 in (2,3), and then you look (3,3) and get to zero, go back to (2,3) and try 2, then 1, then press to your (2,3) conjecture etc.