Sudoku Solver Scilab

Question

我正在编写一个程序来解决sudoku的回溯问题。我现在用的是刀疤。我在递归算法中不断出错，我肯定做错了什么。欢迎任何帮助。

我把我的错误代码放在了底部。

///////////////////////////////////////////////////////////////////////////
//////////////////////////   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未定义变量:s在函数解的第31行被调用：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在函数解题的第24行，由：

在exec文件的第184行被以下调用：

B-8525585618758424927.sce'，执行回调时

Answer 1

主要问题是这一行：

solve(board) 

这应该是

S = solve(board)

递归函数必须提供两种功能:一种将修改后的任务委托给其自身的另一个实例的方法，另一种将结果返回给调用它的实例的方法。你没有第二件事。

另一个较小的问题是你对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上，但循环在我继续。快速解决办法：

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的值就会被遗忘。如果给出一个无法解决的谜题，您的代码将进入无限递归。