algorithm - 数独求解器 Scilab

Question

我正在尝试编写一个使用回溯解决数独问题的程序。我现在正在使用 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在执行回调时

Answer 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.  

---

需要考虑的事情:

1. 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 

1. 回溯未正确实现。命令board(x,y)=0没有效果，因为局部变量的值 board当函数结束时，它就会被遗忘。如果给定一个无法解决的难题，您的代码将进入无限递归。