使用回溯的python中的Sudoku求解器 [英] Sudoku solver in python using backtracking

问题描述

我看到了几个数独求解器的实现，但是我无法在代码中找出问题所在.我有一个功能sudokusolver，它变成了sudoku Board，必须返回已解决的sudoku board.

I saw a few sudoku solvers implementations ,but I cant figure out the problem in my code. I have a function sudokusolver which becomes sudoku Board and must return solved sudoku board.

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;
    sudokusolver(S);
    return S;

sudokutest和possibleNums是正确的，只有sudokusolver给出RecursionError

sudokutest and possibleNums are correct , only sudokusolver give a RecursionError

推荐答案

在回溯递归搜索中，您还可以通过使用一些启发式算法(例如最小剩余值启发式算法)和约束传播技术(例如前向检查和arc-通过确保一致性来减少要分配的变量的域的一致性.

Along with backtracking recursive search, you could also improve your algorithm by using some heuristics such as least remaining value heuristic and constraint propagation techniques such as forward checking and arc-consistency to reduce the domain of the variables to be assigned, by ensuring consistency.

以下动画显示了具有所有启发式和约束传播的Sudoku拼图解决方案示例，从而使递归BT搜索更快.

The following animation shows an example Sudoku puzzle solution with all the heuristics and constraint propagation, thereby making the recursive BT search much faster.

有关详细信息，您可能要参考

For details you may want to refer to https://sandipanweb.wordpress.com/2017/03/17/solving-sudoku-as-a-constraint-satisfaction-problem-using-constraint-propagation-with-arc-consistency-checking-and-then-backtracking-with-minimum-remaning-value-heuristic-and-forward-checking/?frame-nonce=9d28c0c035

这篇关于使用回溯的python中的Sudoku求解器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！