在Python中有没有简单的方法实现回溯算法？

Question

我需要帮助来制作一个Python算法。我想创建一个网格，并根据一些规则在单元格上放置一个“x”。这个网格有15行和100列。每一列只能有一个“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()

数据结构算法设计组合优化回溯算法网格算法约束满足问题

在Python中有没有简单的方法实现回溯算法？

1 个回答

撰写回答