数独算法没有按预期工作

Question

我正在尝试解决数独问题。但它并没有像我预期的那样工作。

import numpy as np

grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0],#x0
        [6, 0, 0, 1, 9, 5, 0, 0, 0],#x1
        [0, 9, 8, 0, 0, 0, 0, 6, 0],#x2
        [8, 0, 0, 0, 6, 0, 0, 0, 3],#x3
        [4, 0, 0, 9, 0, 3, 0, 0, 1],#x4
        [7, 0, 0, 0, 2, 0, 0, 0, 6],#x5
        [0, 6, 0, 0, 0, 0, 2, 8, 0],#x6
        [0, 0, 0, 4, 1, 9, 0, 0, 5],#x7
        [0, 0, 0, 0, 8, 0, 0, 7, 9]]#x8
#       y0 y1 y2 y3 y4 y5 y6 y7 y8    
    
def possible(x,y,n, matris):
        for i in range(0, 9):
                if matris[x][i] == n:
                        return False
        for i in range(0, 9):
                if matris[i][y] == n:
                        return False
        x0 = (x//3)*3
        y0 = (x//3)*3
        for i in range(0, 3):
                for j in range(0, 3):
                        if matris[x0+i][y0+j] == n:
                                return False
        return True


def solve(sudoku):
        for x in range(9):
                for y in range(9):
                        if sudoku[x][y] == 0: 
                                for n in range(1, 10):
                                        if possible(x, y, n, sudoku):
                                                sudoku[x][y]=n
        return np.matrix(sudoku)
                          
print(solve(grid))

如您所见，输出没有给我未解决的数独网格的结果。我看不出是什么问题。

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

可能是什么问题，有什么想法吗？

Answer 1

首先，您在问题中列出的谜题无解。您可以在 Sudoku Solutions 上验证它。单击加载按钮并输入“trincot_for_so”作为识别码以加载拼图。

如果你把中间的3x3方框的9改成0，就有解决办法了。该解决方案将在该单元格中显示 8。

其次，您的代码在这一行中有一个 (copy/paste) 错误：

y0 = (x//3)*3

应该是：

y0 = (y//3)*3

要解决有解的谜题，您需要实施回溯。为此，您可以使用递归。您的主要功能如下所示：

def solve(sudoku):
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                for n in range(1, 10):
                    if possible(x, y, n, sudoku):
                        sudoku[x][y] = n
                        # Use recursion to solve the rest of the puzzle
                        result = solve(sudoku)
                        # If rest of the puzzle could be solved, return the solution
                        if result is not None:
                            return result
                        # Backtrack. Allow inner loop to try another value
                        sudoku[x][y] = 0
                # If none of the values for this cell work: no solution (None)
                return
    # We only get here when solve was called with a completely filled-in grid
    return np.matrix(sudoku)

数独算法没有按预期工作

Sudoku Alogirthm does not working as expected

python

algorithm

logic

sudoku

puzzle