用python跟回溯的數獨求解器

Question

我看到了一些數獨求解器的實現，但我無法弄清楚我的代碼中的問題。我有一個功能sudokusolver成爲sudoku董事會，必須返回解決sudoku板。

def sudokutest(s,i,j,z): 
    # z is the number 
    isiValid = np.logical_or((i+1<1),(i+1>9)); 
    isjValid = np.logical_or((j+1<1),(j+1>9)); 
    iszValid = np.logical_or((z<1),(z>9)); 
    if s.shape!=(9,9): 
     raise(Exception("Sudokumatrix not valid")); 
    if isiValid: 
     raise(Exception("i not valid")); 
    if isjValid: 
     raise(Exception("j not valid")); 
    if iszValid: 
     raise(Exception("z not valid")); 

    if(s[i,j]!=0): 
     return False; 

    for ii in range(0,9): 
     if(s[ii,j]==z): 
      return False; 

    for jj in range(0,9): 
     if(s[i,jj]==z): 
      return False; 

    row = int(i/3) * 3; 
    col = int(j/3) * 3; 
    for ii in range(0,3): 
     for jj in range(0,3): 
      if(s[ii+row,jj+col]==z): 
       return False; 

    return True; 

def possibleNums(s , i ,j): 
    l = []; 
    ind = 0; 
    for k in range(1,10): 
     if sudokutest(s,i,j,k): 
      l.insert(ind,k); 
      ind+=1; 
    return l; 

def sudokusolver(S): 
    zeroFound = 0; 
    for i in range(0,9): 
     for j in range(0,9): 
      if(S[i,j]==0): 
       zeroFound=1; 
       break; 
     if(zeroFound==1): 
      break; 
    if(zeroFound==0): 
      return S; 

    x = possibleNums(S,i,j); 
    for k in range(len(x)): 
     S[i,j]=x[k]; 
     sudokusolver(S); 
    S[i,j] = 0; 

    return S; 

sudokutest和possibleNums是正確的，只是sudokusolver給予RecursionError

Answer 1

最後我得到了NumPy的啓動和運行，我不得不用手（我的問題）來複制的數量。總之在一個非常簡單的解決方案下。在你的代碼中（我修改了一下以瞭解矩陣），你必須找到一個合適的方法來阻止數獨完全解決的時刻。要做到這一點，我已經使用了很多像sys.exit（）這樣的東西，但是你可以在矩陣完成後實現額外的檢查並移出整個循環。否則，你會用新的零寫在已完成的零之上，並且你將一次又一次地運行相同的步驟。

我已經做只有一個小的調試，但可以引入更多的打印出來，並檢查如何矩陣本身是不斷髮展的:-)

至少現在是工作，希望你會投票給我的「短期」解。 祝您有個美好的一天，玩得開心！

def sudokutest(s,i,j,z): 
    # z is the number 
    isiValid = numpy.logical_or((i+1<1),(i+1>9)); 
    isjValid = numpy.logical_or((j+1<1),(j+1>9)); 
    iszValid = numpy.logical_or((z<1),(z>9)); 
    if s.shape!=(9,9): 
     raise(Exception("Sudokumatrix not valid")); 
    if isiValid: 
     raise(Exception("i not valid")); 
    if isjValid: 
     raise(Exception("j not valid")); 
    if iszValid: 
     raise(Exception("z not valid")); 

    if(s[i,j]!=0): 
     return False; 

    for ii in range(0,9): 
     if(s[ii,j]==z): 
      return False; 

    for jj in range(0,9): 
     if(s[i,jj]==z): 
      return False; 

    row = int(i/3) * 3; 
    col = int(j/3) * 3; 
    for ii in range(0,3): 
     for jj in range(0,3): 
      if(s[ii+row,jj+col]==z): 
       return False; 

    return True; 

def possibleNums(s , i ,j): 
    l = []; 
    ind = 0; 
    for k in range(1,10): 
     if sudokutest(s,i,j,k): 
      l.insert(ind,k); 
      ind+=1; 
    return l; 

def sudokusolver(S): 
    zeroFound = 0; 
    for i in range(0,9): 
     for j in range(0,9): 
      if(S[i,j]==0): 
       zeroFound=1; 
       break; 
     if(zeroFound==1): 
      break; 
    if(zeroFound==0): 
     print("REALLY The end") 
     z = numpy.zeros(shape=(9,9)) 
     for x in range(0,9): 
      for y in range(0,9): 
       z[x,y] = S[x,y] 
     print(z) 
     return z 


    x = possibleNums(S,i,j); 

    for k in range(len(x)): 
     S[i,j]=x[k]; 
     sudokusolver(S); 
    S[i,j] = 0; 


if __name__ == "__main__": 
    import numpy 
    #s = numpy.zeros(shape=(9,9)) 

    k = numpy.matrix([0,0,0,0,0,9,0,7,8,5,1,0,0,0,0,0,6,9,9,0,8,0,2,5,0,0,0,0,3,2,0,0,0,0,0,0,0,0,9,3,0,0,0,1,0,0,0,0,4,0,0,0,8,0,8,0,0,0,9,0,7,0,0,6,0,1,0,0,0,0,0,0,0,0,0,0,7,0,8,0,1]).reshape(9,9) 
    print(k) 
    print('*'*80) 
    sudokusolver(k)