求助：如何用Python实现简单回溯算法及规则化网格填充？

回溯算法的简单实现思路 #

回溯算法的核心是递归尝试+合法性校验+撤销选择：

• 递归遍历所有可能的选择路径
• 每一步先检查当前选择是否符合所有规则，合法则继续深入
• 若走到死路（无法继续满足规则），则撤销当前选择，回到上一步尝试其他可能

针对你的网格生成需求，现有代码存在规则处理错误和效率问题，以下是修正后的实现方案：

规则解析与代码修正 #

首先明确所有规则的准确处理方式：

• 每列仅1个"x"：维护已占用列的集合，确保新选列未被使用
• 每行4个"x"：每行固定生成4个符合间隔要求的位置
• 每行"x"间隔为1、2、3（顺序任意）：四个位置c1<c2<c3<c4需满足{c2-c1-1, c3-c2-1, c4-c3-1} = {1,2,3}，即三个间隔恰好覆盖1、2、3各一次
• 每12列范围内最多4个"x"：按你原代码逻辑，定义为每行的任意12列区块（如0-11、12-23...）内最多4个"x"（若实际为全局12列窗口限制，该规则与总x数存在矛盾，需重新确认规则表述）
• 30-40列禁止放"x"：排除列号29到39（Python索引从0开始）

修正后的完整代码 #

import numpy as np
import matplotlib.pyplot as plt
from itertools import permutations

class Board:
    def __init__(self, rows, cols, value='x'):
        self.rows = rows
        self.cols = cols
        self.value = value
        self.board = [['']*cols for _ in range(rows)]
        self.used_cols = set()  # 快速校验列是否被占用

    # 生成当前行所有符合规则3、5的x位置组合
    def generate_valid_row_positions(self):
        valid_positions = []
        # 生成间隔的所有排列组合
        spacing_perms = permutations([1,2,3])
        # 第一个x的起始位置需满足：后续能放下3个x（总跨度为9）
        for c1 in range(self.cols - 9):
            for s1, s2, s3 in spacing_perms:
                c2 = c1 + s1 + 1
                c3 = c2 + s2 + 1
                c4 = c3 + s3 + 1
                cols = [c1, c2, c3, c4]
                # 排除禁止放置的列
                if any(29 <= c <= 39 for c in cols):
                    continue
                valid_positions.append(cols)
        return valid_positions

    # 检查当前行的位置组合是否符合规则
    def is_row_valid(self, positions):
        # 校验列是否已被占用
        if any(c in self.used_cols for c in positions):
            return False
        return True

    # 回溯求解
    def solve(self, row=0):
        if row == self.rows:
            return True
        # 遍历当前行的所有合法位置组合
        valid_rows = self.generate_valid_row_positions()
        for positions in valid_rows:
            if self.is_row_valid(positions):
                # 放置x并标记列已占用
                for c in positions:
                    self.board[row][c] = self.value
                    self.used_cols.add(c)
                # 递归处理下一行
                if self.solve(row + 1):
                    return True
                # 回溯：撤销放置
                for c in positions:
                    self.board[row][c] = ''
                    self.used_cols.remove(c)
        return False

    # 可视化网格
    def plot_board(self):
        plt.figure(figsize=(16, 8))
        grid = np.array([[0 if cell == '' else 1 for cell in row] for row in self.board])
        plt.imshow(grid, cmap='binary', aspect='auto')
        plt.title('符合规则的网格可视化')
        plt.xlabel('列')
        plt.ylabel('行')
        # 标记禁止放置区域
        plt.axvspan(29.5, 39.5, color='red', alpha=0.3, label='禁止放置区域')
        plt.xticks(np.arange(0, self.cols, 12), np.arange(0, self.cols, 12))
        plt.yticks(np.arange(0, self.rows), np.arange(1, self.rows+1))
        plt.grid(True, color='gray', linestyle='--')
        plt.legend()
        plt.show()

def main():
    rows = 15
    cols = 100
    board = Board(rows, cols)
    if board.solve():
        print("找到符合规则的网格！")
        board.plot_board()
    else:
        print("不存在符合规则的解。")

if __name__ == "__main__":
    main()

代码说明 #

1. 高效生成合法行：通过permutations生成间隔的所有排列，直接计算每行的4个x位置，避免逐个单元格尝试，大幅提升效率
2. 规则校验优化：用used_cols集合快速检查列是否被占用，时间复杂度O(1)
3. 禁止区域处理：生成位置时直接排除29-39列
4. 回溯逻辑清晰：逐行尝试所有合法组合，成功则继续，失败则撤销选择

注意事项 #

若规则4的实际含义是全局任意连续12列内的x总数不超过4，则当前需求存在矛盾：15行每行4个x共60个，100列平均每12列有7.2个x，远超4个，此时无解，需确认规则表述是否准确。

内容的提问来源于stack exchange，提问作者Shawn