How to make a Sudoku solution with a backtracking algorithm?
This weekend I was working on a Sudoku Solver ( Ruby quiz ) based on a backtracking algorithm. Sudoku is loaded into an array sudoku_arr
of 81 integers (9x9 grid), where 0 are empty spaces. There is a method valid?
that checks if sudoku_arr
sudoku is valid.
the official backtracking algorithm is as follows: try the value on the next blank, check if it is really sudoku if not increase the value by 1 (to 9) if the value is valid, and try the first value in the next place if not increment the previous one 0.
So we have to keep track of the previous array and this is where I go wrong and I'm not sure if it can be solved. The part of my code below that doesn't work is solve_by_increasing_value_previous_index
in a class SudokuSolver
. Here's the code:
require 'pp'
sudoku_str = "
+-------+-------+-------+
| _ 6 _ | 1 _ 4 | _ 5 _ |
| _ _ 8 | 3 _ 5 | 6 _ _ |
| 2 _ _ | _ _ _ | _ _ 1 |
+-------+-------+-------+
| 8 _ _ | 4 _ 7 | _ _ 6 |
| _ _ 6 | _ _ _ | 3 _ _ |
| 7 _ _ | 9 _ 1 | _ _ 4 |
+-------+-------+-------+
| 5 _ _ | _ _ _ | _ _ 2 |
| _ _ 7 | 2 _ 6 | 9 _ _ |
| _ 4 _ | 5 _ 8 | _ 7 _ |
+-------+-------+-------+"
class SudokuException < StandardError
attr_reader :sudoku_arr
def initialize(message, sudoku_arr)
super(message)
@sudoku_arr = sudoku_arr
end
end
class Sudoku
attr_accessor :sudoku_arr,
:index_of_tried_value,
:tried_value
def initialize(sudoku_arr, index_of_tried_value, tried_value)
@sudoku_arr = sudoku_arr
@index_of_tried_value = index_of_tried_value
@tried_value = tried_value
end
def rows_valid?
rows_have_unique_values?(@sudoku_arr)
end
def columns_valid?
rows_have_unique_values?(@sudoku_arr.each_slice(9).to_a.transpose.flatten!)
end
def squares_valid?
tmp_a = @sudoku_arr.each_slice(3).to_a
rows_have_unique_values?(
(tmp_a[0] << tmp_a[3] << tmp_a[6] << tmp_a[1] << tmp_a[4] << tmp_a[7] <<
tmp_a[2] << tmp_a[5] << tmp_a[8] << tmp_a[9] << tmp_a[12] << tmp_a[15] <<
tmp_a[10] << tmp_a[13] << tmp_a[16] << tmp_a[11] << tmp_a[14] << tmp_a[17] <<
tmp_a[18] << tmp_a[21] << tmp_a[24] << tmp_a[19] << tmp_a[22] << tmp_a[25] <<
tmp_a[20] << tmp_a[23] << tmp_a[26]).flatten!)
end
def valid?
rows_valid? && columns_valid? && squares_valid?
end
def rows_have_unique_values?(arr)
(arr[0,9]- [0]).uniq.size == (arr[0,9]- [0]).size &&
(arr[9,9]- [0]).uniq.size == (arr[9,9]- [0]).size &&
(arr[18,9]-[0]).uniq.size == (arr[18,9]-[0]).size &&
(arr[27,9]-[0]).uniq.size == (arr[27,9]-[0]).size &&
(arr[36,9]-[0]).uniq.size == (arr[36,9]-[0]).size &&
(arr[45,9]-[0]).uniq.size == (arr[45,9]-[0]).size &&
(arr[54,9]-[0]).uniq.size == (arr[54,9]-[0]).size &&
(arr[63,9]-[0]).uniq.size == (arr[63,9]-[0]).size &&
(arr[72,9]-[0]).uniq.size == (arr[72,9]-[0]).size
end
end
class SudokuSolver
attr_accessor :sudoku_arr,
:indeces_of_zeroes
def initialize(str)
@sudoku_arr = str.gsub(/[|\+\-\s]/,"").gsub(/_/,'0').split(//).map(&:to_i)
@indeces_of_zeroes = []
@sudoku_arr.each_with_index { |e,index| @indeces_of_zeroes << index if e.zero? }
end
def solve
sudoku_arr = @sudoku_arr
try_index = @indeces_of_zeroes[0]
try_value = 1
sudoku = Sudoku.new(sudoku_arr, try_index, try_value)
solve_by_increasing_value(sudoku)
end
def solve_by_increasing_value(sudoku)
if sudoku.tried_value < 10
sudoku.sudoku_arr[sudoku.index_of_tried_value] = sudoku.tried_value
if sudoku.valid?
pp "increasing_index..."
solve_by_increasing_index(sudoku)
else
pp "increasing_value..."
sudoku.tried_value += 1
solve_by_increasing_value(sudoku)
end
else
pp "Increasing previous index..."
solve_by_increasing_value_previous_index(sudoku)
end
end
def solve_by_increasing_index(sudoku)
if sudoku.sudoku_arr.index(0).nil?
raise SudokuException(sudoku.sudoku_arr.each_slice(9)), "Sudoku is solved."
end
sudoku.index_of_tried_value = sudoku.sudoku_arr.index(0)
sudoku.tried_value = 1
solve_by_increasing_value(sudoku)
end
def solve_by_increasing_value_previous_index(sudoku)
# Find tried index and get the one before it
tried_index = sudoku.index_of_tried_value
previous_index = indeces_of_zeroes[indeces_of_zeroes.index(tried_index)-1]
# Setup previous Sudoku so we can go back further if necessary:
# Set tried index back to zero
sudoku.sudoku_arr[tried_index] = 0
# Set previous index
sudoku.index_of_tried_value = previous_index
# Set previous value at index
sudoku.tried_value = sudoku.sudoku_arr[previous_index]
pp previous_index
pp sudoku.tried_value
# TODO Throw exception if we go too far back (i.e., before first index) since Sudoku is unsolvable
# Continue business as usual by increasing the value of the previous index
solve_by_increasing_value(sudoku)
end
end
sudoku_solver = SudokuSolver.new(sudoku_str)
sudoku_solver.solve
Unfortunately, the code doesn't go back to the beginning. The code prints:
"increasing_index ..." "Increasing_value ..." "Increasing_value ..." "Increasing_value ..." "Increasing_value ..." "Increasing_value ..." "Increasing_value ..." "Increasing_value ..." "Increasing_value ... "" Increasing the previous index ... "16 2
in a loop until it pops out SystemStackError
because the stack level is too deep.
What happens is that "backtracking" does not go further than one index. When solve_by_increasing_value_previous_index
it moves to the previous index, it returns to the previous value. In this case it's 2, but 2 doesn't work, so we have to reduce it to 1 and continue, and if that doesn't work, drop 2 and make it 0 again and go back.
Unfortunately, I don't see an easy way to implement this algorithm. (I thought it was a variable @too_much_looping
that gets incremented when called solve_by_increasing_value_previous_index
, and after 81 times gets reset. But it only helps to go back, we can't go back to the beginning.\
I hope someone can help me! General comments are very welcome too, I have a suspicion this is not 100% idiomatic Ruby.
source to share
I haven't skipped your code yet, but the backtracking algorithm boils down to this:
int solve(char board[81]) {
int i, c;
if (!is_valid(board)) return 0;
c = first_empty_cell(board);
if (c<0) return 1; /* board is full */
for (i=1; i<=9; i++) {
board[c] = i;
if (solve(board)) return 1;
}
board[c] = 0;
return 0;
}
It is a recursive function that tries every value from 1
to 9
in the first empty cell it finds (returns first_empty_cell()
). If none of these values lead to a solution, you should be on a dead branch of the search tree, so the corresponding cell can be reset to zero (or whatever value you use to indicate an empty cell).
Of course, there are many other things you could do to get your software to be in solution faster, but as far as backtracking goes, that's all it needs.
Adding:
Ok, now I'm working my way through your code. It looks like you are storing index_of_tried_value
as an attribute of the sudoku grid. It won't work. You need to store this value in a local variable of the solver procedure so that it can be pushed onto the stack and restored when you bounce the search tree.
source to share
There is an algo called "Dance References" invented by "knuth" that can be applied to Sudoku. http://en.wikipedia.org/wiki/Dancing_Links
The Soduko problem can be solved with the exact coverage problem. Here is the article http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
here is my code for solving the exact cap problem, it can solve sudoku as well and the back part is in dlx ()
const int INF = 0x3f3f3f3f;
const int T = 9;
const int N = T*T*T+10;
const int M = T*T*T*4+T*T*4+10;
int id;
int L[M],R[M],U[M],D[M];
int ANS[N],SUM[N],COL[M],ROW[M],H[N];
struct Dancing_links
{
Dancing_links() {}
Dancing_links(int n,int m)
{
for(int i=0; i<=m; i++)
{
SUM[i] = 0;
L[i+1] = D[i] = U[i] = i;
R[i]=i+1;
}
L[m+1]=R[m]=0,L[0]=m,id=m+1;
clr(H,-1);
}
void remove(int c)
{
L[R[c]] = L[c];
R[L[c]] = R[c];
for(int i=D[c]; i!=c; i=D[i])
for(int j=R[i]; j!=i; j=R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
SUM[COL[j]]--;
}
}
void resume(int c)
{
for(int i=U[c]; i!=c; i=U[i])
for(int j=L[i]; j!=i; j=L[j])
{
U[D[j]] = D[U[j]] = j;
SUM[COL[j]]++;
}
L[R[c]] = R[L[c]] = c;
}
void add(int r,int c)
{
ROW[id] = r,COL[id] = c;
SUM[c]++;
D[id] = D[c],U[D[c]] = id,U[id] = c,D[c] = id;
if(H[r] < 0)
H[r] = L[id] = R[id] = id;
else
R[id] = R[H[r]],L[R[H[r]]] = id,L[id] = H[r],R[H[r]] = id;
id++;
}
int dlx(int k)
{
if(R[0] == 0)
{
/*output the answer*/return k;
}
int s=INF,c;
for(int i=R[0]; i; i=R[i])
if(SUM[i] < s)
s=SUM[c=i];
remove(c);
for(int r=D[c]; r!=c; r=D[r])
{
ANS[k] = ROW[r];
for(int j=R[r]; j!=r; j=R[j]) remove(COL[j]);
int tmp = dlx(k+1);
if(tmp != -1) return tmp; //delete if multipal answer is needed
for(int j=L[r]; j!=r; j=L[j]) resume(COL[j]);
}
resume(c);
return -1;
}
};
source to share