python 中的数独求解器未打印板

Question

我一直在开发 python 程序来解决数独难题，但我不确定我做错了什么。我以为我已经修好了，但现在我无法让它打印电路板或解决它。我已经编写了要解决的算法以及创建电路板的功能。如果有人能告诉我哪里出了问题，我将不胜感激。这是我的代码（抱歉缩进错误 - 它们是由复制和粘贴引起的）：

    class Sudoku:
def __init__(self, board, cells):
    self.board = board
    self.cells = cells

#Creates a board
def newboard(self):
    values = self.cells.split(" ")
    val_counter = 0

    if len(values) != 81:
        print("Error: Not enough values.")
        exit()

    else:
        for i in range(9):
            for j in range(9):
                self.board[i][j] = values[val_counter]
                val_counter += 1

# Returns row
def findValidRow(self):
    for i in range(9):
        for j in range(9):
            if int(self.board[i][j]) == 0:
                return int(i)
    return -1

# Returns col
def findValidCol(self):
    for i in range(9):
        for j in range(9):
            if int(self.board[i][j]) == 0:
                return int(j)
    return -1

def possible(self, row, col, val):
    # Check row for value
    for i in range(9):
        if self.board[row][i] == val:
            return False
    # Checks col for value
    for j in range(9):
        if self.board[j][col]:
            return False
    # Checks square for value
    coordX, coordY = 3 * (row // 3), 3 * (col // 3)
    for x in range(coordX, coordX + 3):
        for y in range(coordY, coordY + 3):
            if coordX == row and coordY == col:
                continue
            if self.board[coordX][coordY] == val:
                return False
    return True

    # Solves the board

def solve(self):
    # Checks if cells are all solved
    if self.findValidCol() == -1:
        print(self.board)
        return True

    # Finds first cell to fill
    row = self.findValidRow()
    col = self.findValidCol()

    for i in range(1, 10):
        if self.possible(row, col, i):
            self.board[row][col] = i
            # Updates values to find new cell to fill

            if self.solve():
                return True
            # Backtracks
            self.board[row][col] = 0

    return False


    # Get cell values and calls solve function
    get_cells = input("Enter cell values seperated by 1 space. Enter 0 for empty cells: ")
    b = Sudoku([[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0,    0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0]], get_cells)
    b.newboard()
    b.solve()

Answer 1

你的第一个问题在这里：

# Check row for value
for i in range(9):
    if self.board[row][i] == val:
        return False
# Checks col for value
for j in range(9):
    if self.board[j][col]:
        return False

具体来说，行：

if self.board[j][col]:

应该是：

if self.board[j][col] == val:

下一个问题在这里：

coordX, coordY = 3 * (row // 3), 3 * (col // 3)
for x in range(coordX, coordX + 3):
    for y in range(coordY, coordY + 3):
        if coordX == row and coordY == col:
            continue
        if self.board[coordX][coordY] == val:
            return False

当我认为您应该使用 x 和 y 时，您在循环中使用 coordX 和 coordY 的地方：

for x in range(coordX, coordX + 3):
    for y in range(coordY, coordY + 3):
        if x == row and y == col:
            continue
        if self.board[x][y] == val:
            return False

否则，您将一遍又一遍地重复相同的测试。我在打印电路板时看到的最后一个问题是，您的电路板内容是 int 和 str 的混合体——您需要尽早掌握这一点并且只使用其中一个。

下面是我对你的代码的修改，它解决了我手头的测试数独问题：

class Sudoku:
    def __init__(self, board, cells):
        self.board = board
        self.cells = cells

    def newBoard(self):
        ''' Creates a board '''

        values = self.cells.split(" ")

        assert len(values) == 81, "Error: Not enough values."

        for i in range(9):
            for j in range(9):
                self.board[i][j] = int(values.pop(0))

    def findValidCell(self):
        ''' Returns empty cell indicies or None '''

        for row in range(9):
            for col in range(9):
                if self.board[row][col] == 0:
                    return (row, col)
        return None

    def possible(self, row, col, val):
        # Check row for value
        for i in range(9):
            if self.board[row][i] == val:
                return False

        # Checks col for value
        for j in range(9):
            if self.board[j][col] == val:
                return False

        # Checks square for value
        coordX, coordY = 3 * (row // 3), 3 * (col // 3)

        for x in range(coordX, coordX + 3):
            for y in range(coordY, coordY + 3):
                if x == row and y == col:
                    continue

                if self.board[x][y] == val:
                    return False

        return True

    def printBoard(self):
        print(*self.board, sep='\n')

    def solve(self):
        ''' Solves the board '''

        # Checks if cells are all solved
        cell = self.findValidCell()

        if cell is None:
            return True

        # Finds first cell to fill
        row, col = cell

        for i in range(1, 10):
            if self.possible(row, col, i):
                self.board[row][col] = i
                # Updates values to find new cell to fill

                if self.solve():
                    return True

                # Backtracks
                self.board[row][col] = 0

        return False

# Get cell values and calls solve function
get_cells = input("Enter cell values separated by 1 space. Enter 0 for empty cells: ")
b = Sudoku([
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    ], get_cells)

b.newBoard()
if b.solve():
    b.printBoard()

Answer 2

@cdlane 给出的答案很有效。我刚刚注意到我将使用一些优化来提高 possible 函数的边际性能，结果是：

def possible(self, row, col, val):
    # Check row or column for value
    for i in range(9):
        if (self.board[row][i] == val) or (self.board[i][col] == val):
            return False

    # Checks 3x3 containing square for value
    coordX, coordY = 3 * (row // 3), 3 * (col // 3)

    for x in range(coordX, coordX + 3):
        for y in range(coordY, coordY + 3):
            if self.board[x][y] == val:
                return False
    return True

你可以看到我在同一个 for 循环中检查了行和列，我消除了一个不必要的单元格位置检查，因为候选单元格在该点包含零。

并且因为我希望在错误消息中包含更多信息，所以我将断言修改为：

    assert len(values) == 81, "Error: {} values {} != {}".format(("Not enough"if len(values)<81 else "Too many"),len(values),81)

python 中的数独求解器未打印板

Sudoku Solver in python not printing board

python

sudoku