如何修复我的数独解算器基于回溯

Question

我试图用python创建一个基于回溯的数独求解算法，但是它总是不返回任何关于数独不正确的信息。你知道吗

这是我的密码：

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

e = [0, 0]

def checkEmpty():
    for i in range(0, 9):
        for j in range(0, 9):
            if board[i][j] == 0:
                e[0] = i
                e[1] = j
                return True
    return False

def vLine(i, test):
    for j in range(9):
        if board[i][j] == test:
            return True
    return False

def vColumn(j, test):
    for i in range(9):
        if board[i][j] == test:
            return True
    return False

def vBlock(i, j, test):
    for I in range(3):
        for J in range(3):
            if(board[i+I][j + J] == test):
                return True
    return False

def validMove(i, j, test):
    if vColumn(j, test) == False and vBlock(i, j, test) == False and vLine(i, test) == False:
        return True
    else:
        return False

def solve():
    e = [0, 0]
    if checkEmpty() == False:
        return True
    i = e[0]
    j = e[1]
    for k in range(1, 10):
        if validMove(i, j, k) == True:
            board[i][j] = k
            if solve() == True:
                return True
            board[i][j] = 0
    return False

if solve():
    print("solved!")
else:
    print("No solution exists")

问题是，if函数if validMove(i, j, k) == True:中的代码似乎从未执行过。 但是我在这个函数中找不到任何错误。你知道吗

另外，我真的不知道我应该在这里缩进、删除还是保留这行board[i][j] = 0。你知道吗

Answer 1

你的方块检查器是错误的-如果你输入2，2，9它将不会检查正确的方块，但一些错位。你知道吗

def vBlock(i, j, test):
    for I in range(3):
        for J in range(3):
            if(board[i+I][j + J] == test):   # checks 2-5. 2-5 row&col
                return True
    return False

把它改成

def vBlock(i, j, test):
    for I in range(3):
        for J in range(3):
            if(board[i//3+I][j//3 + J] == test): # this way it cecks the blocks correctly 
                # if you input 2,2,9 it checks 2//3+range == 0+0-3 
                return True
    return False

这不会改变整体误差，但至少补偿一个误差。你知道吗

---

您递归到solve()而从不更改当前选中的e行/列列表-您的solve()使用局部变量e-您的checkEmpty()更改全局e，这些更改永远不会反映在solve()中。你知道吗

修正：

def checkEmpty():
    global e        # explicitly use the global e
    for i in range(0, 9):
        for j in range(0, 9):
            if board[i][j] == 0:
                e[0] = i
                e[1] = j
                return True
    return False

def solve():
    global e        # explicitly use the global e
    if checkEmpty() == False:
        return True
    i = e[0]
    j = e[1]
    print(e)
    for k in range(1, 10): 
        if validMove(i, j, k) == True:
            board[i][j] = k
            if solve() == True:
                return True
            board[i][j] = 0

    return False

---

即使修复了这两个错误：

你需要能够放弃早期的发现-f.e.在开始的时候，一个空间可能会被9,1,3,4填满-你先检查1-宾果-把它放进去，但是在这个块中，后来遇到了问题，因为这个位置只能容纳1。现在1被放弃了，你没有解决办法。你知道吗

您需要首先为所有0计算“所有可能的”数字，然后填写那些只有1个可能性的数字，从相应的行/列/块0可能性列表中删除该数字，然后继续，直到所有可能的数字都填写完毕。你知道吗

一句话：用可用的第一个选择来解决这个问题，可能会导致一个局部极小值，它会解决12个剩余零中的10个，然后你就会陷入困境。你知道吗