有没有简单的方法用Python制作回溯算法？

Question

我需要帮助制作 python 算法。我想制作一个网格并根据某些规则在单元格上放置“x”。网格有 15 行和 100 列。每列只能有 1 个“x”。每行应该有 4 个“x”。每行中的“x”应间隔 1、2 和 3 个空格。每个“x”之间的空格数量可以是任意顺序，例如 3、2、1 或 1、3、2。每 12 列只能有 4 个“x”。第 30-40 列中不能放置“x”。

我还尝试用 Python 和 Excel 绘制结果。 这是我到目前为止所拥有的：

import numpy as np
import matplotlib.pyplot as plt

class Board:
    def __init__(self, rows, cols, value='x', num_values=4, spacings=None):
        self.rows = rows
        self.cols = cols
        self.value = value
        self.num_values = num_values
        self.spacings = spacings if spacings else {}
        self.board = [['']*cols for _ in range(rows)]

    def is_valid(self, row, col):
        # Check if value is already in the same column
        for r in range(self.rows):
            if self.board[r][col] == self.value:
                return False

        # Check if there are no more than num_values of the same value in the same row
        if sum(1 for v in self.board[row] if v == self.value) >= self.num_values:
            return False

        # Check if values are spaced apart based on row
        if row in self.spacings:
            spacing = self.spacings[row]
            for c in range(col - spacing, col + spacing + 1):
                if 0 <= c < self.cols:
                    if self.board[row][c] == self.value:
                        return False

        # Check if no more than num_values of the same value in each group of 12 columns
        group_start = (col // 12) * 12
        group_end = group_start + 12
        group_values = [self.board[row][c] for c in range(group_start, group_end) if self.board[row][c] == self.value]
        if len(group_values) >= self.num_values:
            return False

        return True

    def solve(self, row=0, col=0):
        if row == self.rows:
            return True

        next_row = row + (col + 1) // self.cols
        next_col = (col + 1) % self.cols

        for value in [self.value]:
            if self.is_valid(row, col):
                self.board[row][col] = self.value
                if self.solve(next_row, next_col):
                    return True
                self.board[row][col] = ''

        return False

    def plot_board(self):
        plt.figure(figsize=(12, 8))
        plt.imshow(np.array([[0 if cell == '' else 1 for cell in row] for row in self.board]), cmap='binary', aspect='auto')
        plt.title('Board Visualization')
        plt.xlabel('Columns')
        plt.ylabel('Rows')
        plt.xticks(np.arange(0, self.cols, 12), np.arange(0, self.cols, 12))
        plt.yticks(np.arange(0, self.rows), np.arange(0, self.rows))
        plt.grid(True, color='gray')
        plt.show()


def main():
    rows = 15
    cols = 100
    value = 'x'
    num_values = 4
    spacings = {1, 2, 3}


    board = Board(rows, cols, value, num_values, spacings)
    if board.solve():
        print("Solution:")
        board.plot_board()
    else:
        print("No solution exists.")

if __name__ == "__main__":
    main()

Answer 1

solve

的实现看起来有点像回溯，但实际上并不是回溯。 回溯意味着当递归搜索找不到解决方案时，您会在递归中尝试下一个可能的候选点，直到找到通用解决方案或用完候选点。在这里的实现中，如果使用

board[i][j] = 'x'

找不到解决方案（对于任何 i 和 j），那么您就不会尝试任何其他候选解决方案，因此您不会回溯并且永远不会找到任何解决方案。