数独求解器 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 未定义变量：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)

递归函数必须提供两件事：一种将修改后的任务委托给自身的另一个实例的方法，和一种将结果return传递给实例的方法那叫它。你没有第二件事。

另一个较小的问题是您对 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 上的双循环应该是另一个函数，它接收一个矩阵和 returns 第一个 (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 的值在函数结束时被简单地忘记了。如果给定一个无法解决的难题，您的代码将进入无限递归。

数独求解器 Scilab

Sudoku Solver Scilab

algorithm

runtime-error

sudoku

scilab

backtracking