ansaurus

Question

Brute-force sudoku solver: backtracking?

Answer 1

+2 A:

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.

Amber 2010-07-23 17:06:20

OP: Yep, backtracking is what you want, and this is how you implement it.

torak 2010-07-23 17:10:02

Well, if I do that, the 7 changes to a 3 and the following 0 remains, but the last 0 becomes a 7. The program just modifies the cell that was last changed.

Yktula 2010-07-23 17:21:34

Is it the fault of cells that came before ?

Yktula 2010-07-23 17:36:33

When you go back to a previous cell, you then need to start your filling from the cell after that - if you backtrack, you then have to start working forward again from right after where you backtracked to.

Amber 2010-07-23 17:56:48

How do I know where to backtrack to ? Anything other than just changing previous cells and seeing if the ones that were zeroed can start to change ?

Yktula 2010-07-23 18:09:20

Since your algorithm appears to work left-to-right, to-to-bottom, you should always backtrack to the previous cell (left, unless at the beginning of a row, then up to the rightmost of the previous row). If that cell has no more remaining valid numbers, then you backtrack another cell, and so on until you find one with a a remaining number.

Amber 2010-07-23 18:45:56

How do you suggest I keep track of which cells are mutable (i.e., initially zeros) ? The algorithm does work the way you indicated; it simply iterates through the cells and changes ones valued at zero.

Yktula 2010-07-23 18:55:09

I'd say you might want to keep a separate array which is the "original" state of the board (and is never modified), and check against that.

Amber 2010-07-23 19:31:42

Answer 2

A:

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.

mvds 2010-07-23 17:08:46

Answer 3

+1 A:

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.

Nathon 2010-07-23 17:21:55

So, keep every working cell value on the stack, every working guess, or replace my multi-dimentional array (representing the cells) with a stack?

Yktula 2010-07-23 17:50:36

The easiest way is probably to keep the guesses on the stack. You'll want to keep your 2-D array around so you can easily get an idea of what the legal values for your current cell are.

Nathon 2010-07-23 19:18:49

ansaurus

tags:

views:

answers:

Brute-force sudoku solver: backtracking?

related questions