algorithm - 数独求解器 - Scilab

Question

我在 SciLab 中编写了一个解决数独问题的程序。但它只能解决总是有一个可能值为 1 的正方形的数独。就像 brainbashers.com 上非常简单和简单的数独游戏。

中等数独总是会到达一个点，即它们没有具有 1 个可能值的正方形。我如何修改我的代码来解决这些更难的数独问题？

///////////////////////////////////////////////////////////////////////////
//////////////////////////   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

function [x,y]=firstEmptyValue(board)           // Checks the first empty square of the sudoku    
R=%T                                        // and returns the position (x,y)
for i=1 : 9
    for j=1 : 9
        if board(i,j) == 0 & R = %T then
            x=i
            y=j
            R=%F
        end
    end
end
endfunction

function A=numberOfPossibilities(V)             // this checks the number of possible values for a position
A=0                                         // so basically it returns the number of elements different from 0 in the vector V
for i=1 : 9
    if V(i)>0 then
        A=A+1
    end
end
endfunction

function u=getUniquePossibility(M,x,y)          // this returns the first possible value for that square
pos = []                                    // in function fillInValue we only use it
pos = PossibilitiesPosition(M,x,y)          // when we know that this square (x,y) has only one possible value
for n=1 : 9
    if pos(n)>0 then
        u=pos(n)
    end
end
endfunction




///////////////////////////////////////////////////////////////////////////
//////////////////////////   Solve Sudoku   ///////////////////////////////
///////////////////////////////////////////////////////////////////////////

function G=fillInValue(M)               // fills in a square that has only 1 possibile value
x=0
y=0
pos = []

for i=1 : 9
        for j=1 : 9
            if M(i,j)==0 then
                if numberOfPossibilities(PossibilitiesPosition(M,i,j)) == 1 then
                    x=i
                    y=j
                    break
                end
            end
        end
        if x>0 then
            break
        end
    end
M(x,y)=getUniquePossibility(M,x,y)
G=M
endfunction

function H=solve(M)                     // repeats the fillInValue until it is a fully solved sudoku
P=[]
P=M
if check(M)=%F then
   P=fillInValue(M)
   H=solve(P)        
else
    H=M
end
endfunction


//////////////////////////////////////////////////////////////////////////////

所以它解决了第一个

// Very easy and easy sudokus from brainbashers.com get solved completely
// 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]

但它并没有解决这个媒介:

M2= [0 0 6 8 7 1 2 0 0
     0 0 0 0 0 0 0 0 0
     5 0 1 3 0 9 7 0 8
     1 0 7 0 0 0 6 0 9
     2 0 0 0 0 0 0 0 7
     9 0 3 0 0 0 8 0 1
     3 0 5 9 0 7 4 0 2
     0 0 0 0 0 0 0 0 0
     0 0 2 4 3 5 1 0 0]

尝试解决中等数独时的错误代码:

-->solve(M2)
 !--error 21 
Invalid index.
at line      14 of function PossibilitiesPosition called by :  
at line       3 of function getUniquePossibility called by :  
at line      20 of function fillInValue called by :  
at line     182 of function solve called by :  
at line     183 of function solve called by :  
at line     183 of function solve called by :  
at line     183 of function solve called by :  
at line     183 of function solve called by :  
solve(M2)
at line     208 of exec file called by :    
_SCILAB-6548660277741359031.sce', 1
while executing a callback

Answer 1

好吧，编写数独求解器的最简单方法之一(不是最有效的)可能是使用所有可能的选项递归地求解每个单元格(这可能类似于“回溯”算法)，直到得到完整答案找到了。

另一种选择(我会说它更好)是遍历所有方 block 解决所有“简单”方 block 并将可能的答案存储在其他方 block 中，然后重复(现在你已经解决了更多)，重复这个过程直到解出数独或不能直接解出更多的方 block 。然后你可以尝试剩下的用暴力或回溯(也许数独已经解出一半或更多，所以它可能相对有效)

无论如何，通过快速搜索我找到了this Wikipedia page其中一些数独求解算法用伪代码示例进行了解释，希望这些对您有用