Sudoku Solver - 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

那麼，最簡​​單的方法之一使用Sudoku解算器（不是最高效的）可以用遞歸方式（可能類似於「Backtracking」算法）解決每個單元格的問題，直到找到完整答案爲止。

另一種選擇（我會說這是更好的）是遍歷所有的廣場解決所有的「簡單」的廣場和存儲可能的答案在其他廣場，然後重複（現在你有更多的解決），重複直到數獨解決或者沒有更多的方格可以直接解決。然後你可以嘗試其餘的蠻力或回溯（也許半數以上的數獨已經解決了，所以它可能是相對有效的）

無論如何，快速搜索我發現this Wikipedia page其中一些Sudoku求解算法是用僞代碼示例進行解釋，希望這些對您有用