I am trying to write a program that solves sudoku's using backtracking. I'm using scilab at the moment. I keep getting errors in my recursive algorithm, I must be doing something wrong. Any help is welcome.
I put my error code at the bottom.
///////////////////////////////////////////////////////////////////////////
////////////////////////// Check Sudoku ///////////////////////////////
///////////////////////////////////////////////////////////////////////////
function r=OneToNine(V) // function checks if the given vector V contains 1 to 9
r = %T // this works
u = %F
index = 1
while r == %T & index < 10
for i=1 : length(V)
if V(i)==index then
u = %T
end
end
index=index+1
if u == %F then r = %F
else u = %F
end
end
if length(V) > 9 then r = %F
end
endfunction
function y=check(M) // Checks if the given matrix M is a solved sudoku
y = %T // this works too
if size(M,1)<>9 | size(M,2)<>9 then // if it has more or less than 9 rows and columns
y = %F // we return false
end
for i=1 : size(M,1) // if not all rows have 1-9 we return false
if OneToNine(M(i,:)) == %F then
y = %F
end
end
endfunction
function P=PossibilitiesPosition(board, x, y)
// this one works
// we fill the vector possibilites with 9 zeros
// 0 means empty, 1 means it already has a value, so we don't need to change it
possibilities = [] // a vector that stores the possible values for position(x,y)
for t=1 : 9 // sudoku has 9 values
possibilities(t)=0
end
// Check row f the value (x,y) for possibilities
// we fill the possibilities further by puttin '1' where the value is not possible
for i=1 : 9 // sudoku has 9 values
if board(x,i) > 0 then
possibilities(board(x,i))=1
end
end
// Check column of the value (x,y) for possibilities
// we fill the possibilities further by puttin '1' where the value is not possible
for j=1 : 9 // sudoku has 9 values
if board(j, y) > 0 then
possibilities(board(j, y))=1
end
end
// Check the 3x3 matrix of the value (x,y) for possibilities
// first we see which 3x3 matrix we need
k=0
m=0
if x >= 1 & x <=3 then
k=1
else if x >= 4 & x <= 6 then
k = 4
else k = 7
end
end
if y >= 1 & y <=3 then
m=1
else if y >= 4 & y <= 6 then
m = 4
else m = 7
end
end
// then we fill the possibilities further by puttin '1' where the value is not possible
for i=k : k+2
for j=m : m+2
if board(i,j) > 0 then
possibilities(board(i,j))=1
end
end
end
P = possibilities
// we want to see the real values of the possibilities. not just 1 and 0
for i=1 : 9 // sudoku has 9 values
if P(i)==0 then
P(i) = i
else P(i) = 0
end
end
endfunction
///////////////////////////////////////////////////////////////////////////
////////////////////////// Solve Sudoku ///////////////////////////////
///////////////////////////////////////////////////////////////////////////
function S=solve(board) // the real solving function, here must be a problem somewhere
x=1
y=1
possibilities = [] // an empty vector to put in the possible value later on
if check(board) == %T then // if it's a fully solved sudoku the function gives the solution
S = board
else
for i=1 : 9 // sudoku has 9 values
for j=1 : 9 // sudoku has 9 values
if board(i,j)==0 then // if the value board(i,j) is empty so 0
x=i // we put the coordinates in x and y
y=j // break means stop the loop
break
end
end
end
possibilities = PossibilitiesPosition(board,x,y) //we check the possibilities
for p=1 : 9 // sudoku has 9 values
if possibilities(p) > 0 then // if this is a possibility
board(x,y) = possibilities(p) // we put in that value
solve(board) // and we repeat until check(board) gives true
end
end
board(x,y)=0 // if we went trough al the possibilities
end // and there is still no solution we have to put that value back to 0
// this is called backtracking
endfunction
//////////////////////////////////////////////////////////////////////////////
Error code:
// Very Easy sudoku from brainbashers.com
M = [0 2 0 0 0 0 0 4 0
7 0 4 0 0 0 8 0 2
0 5 8 4 0 7 1 3 0
0 0 1 2 8 4 9 0 0
0 0 0 7 0 5 0 0 0
0 0 7 9 3 6 5 0 0
0 8 9 5 0 2 4 6 0
4 0 2 0 0 0 3 0 9
0 1 0 0 0 0 0 8 0]
solve(M)
!--error 4
Undefined variable: S
at line 31 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
at line 24 of function solve called by :
solve(M)
at line 184 of exec file called by :
B-8525585618758424927.sce', 1
while executing a callback
The main issue is this line:
solve(board)
which should be
S = solve(board)
A recursive function must provide two things: a way to delegate a modified task to another instance of itself, and a way to return the result to the instance that called it. You didn't have the second thing.
Another, lesser issue, is your search for x,y:
for i=1 : 9 // sudoku has 9 values
for j=1 : 9 // sudoku has 9 values
if board(i,j)==0 then // if the value board(i,j) is empty so 0
x=i // we put the coordinates in x and y
y=j // break means stop the loop
break
end
end
end
The break command only stops the loop from which it was called. So, it breaks your loop over j, but then the loop over i continues. A quick fix:
x=0 // instead of 1
y=0 // instead of 1
// other stuff you have there
for i=1 : 9 // sudoku has 9 values
for j=1 : 9 // sudoku has 9 values
if board(i,j)==0 then // if the value board(i,j) is empty so 0
x=i // we put the coordinates in x and y
y=j // break means stop the loop
break
end
end
if x>0 then
break
end
end
Also, you probably wanted disp(solve(M)) at the end; otherwise the end result of computation is neither shown nor kept in any variable.
With these corrections, your code does work, outputting this solution:
1. 2. 6. 8. 9. 3. 7. 4. 5.
7. 3. 4. 6. 5. 1. 8. 9. 2.
9. 5. 8. 4. 2. 7. 1. 3. 6.
5. 6. 1. 2. 8. 4. 9. 7. 3.
8. 9. 3. 7. 1. 5. 6. 2. 4.
2. 4. 7. 9. 3. 6. 5. 1. 8.
3. 8. 9. 5. 7. 2. 4. 6. 1.
4. 7. 2. 1. 6. 8. 3. 5. 9.
6. 1. 5. 3. 4. 9. 2. 8. 7.
Things to consider:
return [i,j] inside of the double loop, stopping the whole double loop:for i=1 : 9 // sudoku has 9 values
for j=1 : 9 // sudoku has 9 values
if board(i,j)==0 then // if the value board(i,j) is empty so 0
return [i,j]
end
end
end
// do something if the matrix is full
board(x,y)=0 has no effect, since the value of local variable board is simply forgotten when the function ends. Your code would go into infinite recursion if given an unsolvable puzzle.