python 中的数独解算器，带回溯

Question

我看到了一些数独解算器的实现，但我无法找出我的代码中的问题。我有一个 sudokusolver 函数，它变成了数独板并且必须 return 解决数独板。

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 和运行ning，我不得不手动复制数字（我的问题）。无论如何，下面是一个非常简单的解决方案。在你的代码中（我稍微修改一下以理解矩阵）你必须找到一种正确的方法来停止数独完全解决的那一刻。为此，我使用了一些非常困难的方法，例如 sys.exit() 但您可以实施额外的检查并在矩阵完成后移出整个循环。否则，您将在完成的顶部写上新的零，并且您将运行一次又一次地执行相同的步骤。

我只做了一个小的调试，但你可以引入额外的打印输出并检查矩阵本身是如何演变的:-)

至少现在可以正常工作，希望您能投票支持我的 "short term" 解决方案。祝您玩得开心，玩得开心！！

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)

python 中的数独解算器，带回溯

Sudoku solver in python with backtracking

python

sudoku