我正在尝试编写一个使用回溯解决数独问题的程序。 我现在正在使用 scilab。 我的递归算法不断出错，我一定是做错了什么。欢迎任何帮助。
我把我的错误代码放在底部。
///////////////////////////////////////////////////////////////////////////
////////////////////////// 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
//////////////////////////////////////////////////////////////////////////////
错误代码:
// 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)
!--错误4
undefined variable :S
在调用函数 solve 的第 31 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
在函数 solve 调用的第 24 行:
求解(M)
在调用的 exec 文件的第 184 行:
B-8525585618758424927.sce', 1
在执行回调时
最佳答案
主要问题是这一行:
solve(board)
应该是
S = solve(board)
递归函数必须提供两件事:一种将修改后的任务委托(delegate)给自身的另一个实例的方法，和一种将结果返回给调用它的实例的方法。你没有第二件事。
另一个较小的问题是您对 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
break命令仅停止调用它的循环。所以，它打破了你在 j 上的循环，但随后在 i 上的循环继续。快速修复:
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
此外，您可能需要 disp(solve(M))在最后;否则计算的最终结果既不会显示也不会保存在任何变量中。
通过这些更正，您的代码可以正常工作，输出此解决方案:
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.
需要考虑的事情:
- i,j 上的双循环应该是另一个函数，它接收一个矩阵并返回第一个 (x,y) 坐标，其中的条目为零。那么这个函数就只有
return [i,j]在双循环内部，停止整个双循环:
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没有效果，因为局部变量的值board当函数结束时，它就会被遗忘。如果给定一个无法解决的难题，您的代码将进入无限递归。
关于algorithm - 数独求解器 Scilab，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30277003/