在带有禁止棋子的 NxM 棋盘中找到可能的 k 个非攻击车的数量？

Question

我有一个 NxM 不完整的棋盘（意味着一个 NxM 棋盘缺少一些棋子）和一个数字 k（这是我需要在棋盘上放置的非攻击车的数量）

该函数的输入是一个边列表（可以将其视为从索引 1 开始的矩阵，左上角是“第一个”图块）和数字 k。

我创建了一个绘制图板的函数，以便更好地直观地理解问题：

import matplotlib.pyplot as plt
import numpy as np
import math as m
from itertools import permutations, combinations

def plot_chessboard(edge_list):

    #finding the num of columns
    for edge in edge_list:
        if edge[1] != (edge[0] + 1):
            num_cols = edge[1] - edge[0] #this is the number of columns

    #finding the num of rows
    y_max = max(max(y for x, y in edge_list), max(x for x, _ in edge_list))
    num_rows = int(m.ceil(y_max/num_cols)) #this is the number of rows

    # Create a grid of ones (white squares)
    grid = np.zeros((num_rows, num_cols))

    # Create a set of all nodes in the edge list
    nodes = set()
    for edge in edge_list:
        nodes.add(edge[0])
        nodes.add(edge[1])

    #find the legal and forbidden positions
    universe = set(range(1, num_cols*num_rows + 1))
    forbidden_nodes = universe - nodes
    print(f"the nodes are {nodes}")
    print(f"the missing nodes are {forbidden_nodes}")

    # Shade missing nodes black
    for i in range(1, num_rows * num_cols + 1):
        if i not in nodes:
            row = (i - 1) // num_cols
            col = (i - 1) % num_cols
            grid[row, col] = 1  # Set to 0 for black

    print(grid)

    # Create the plot
    fig, ax = plt.subplots(figsize=(10, 10))
    ax.imshow(grid, cmap='binary')

    # Add grid lines
    ax.set_xticks(np.arange(-0.5, num_cols, 1), minor=True)
    ax.set_yticks(np.arange(-0.5, num_rows, 1), minor=True)
    ax.grid(which="minor", color="gray", linestyle='-', linewidth=2)

    # Remove axis ticks
    ax.set_xticks([])
    ax.set_yticks([])

    # Show the plot
    plt.show()


# Example usage
edge_list = [(1, 4), (3, 6), (4, 5), (5, 6)]
B = [[1, 2], [1, 8], [2, 3], [3, 4], [3, 10], [4, 5], [4, 11], [5, 12], [10, 11], [10, 17], [11, 12], [11, 18], [12, 13], [12, 19], [13, 20], [16, 17], [17, 18], [17, 24], [18, 19], [18, 25], [19, 20], [19, 26], [20, 21], [20, 27], [22, 29], [24, 25], [24, 31], [25, 26], [25, 32], [26, 27], [26, 33], [27, 34], [29, 30], [29, 36], [30, 31], [30, 37], [31, 32], [31, 38], [32, 33], [32, 39], [33, 34], [33, 40], [34, 35], [34, 41], [35, 42], [36, 37], [37, 38], [38, 39], [39, 40], [40, 41], [41, 42]]
k = 2
plot_chessboard(edge_list)

现在对于应该采用边列表和 k 的主函数， 并输出在该棋盘上排列 k 个车的可能方式的数量； 到目前为止，在这个函数中，我能够提取棋盘的尺寸（行和列）以及当前我存储在一组元组中的禁止位置的位置，其中元组的格式如下（行，列）（我还使索引从 0 开始，以与代表棋盘的矩阵对齐） 但从那时起，我要做的实际上就是计算在该板上排列 k 辆车的可能方法的数量，但我不知道该怎么做。

import numpy as np
from itertools import permutations, combinations

def k_rook_problem(edge_list, k):
    #finding the num of columns
    for edge in edge_list:
        if edge[1] != (edge[0] + 1):
            num_cols = edge[1] - edge[0] #this is the number of columns

    #finding the num of rows
    y_max = max(max(y for _, y in edge_list), max(x for x, _ in edge_list))
    num_rows = (y_max + num_cols - 1) // num_cols  # Calculate number of rows

    print(f'testing: num rows and num cols are: {num_rows}, {num_cols}')

    #set of all nodes in the edge list
    nodes = set()
    for edge in edge_list:
        nodes.add(edge[0])
        nodes.add(edge[1])

    #set of forbidden positions
    universe = set(range(1, num_cols * num_rows + 1))
    forbidden_nodes = universe - nodes
    
    #set of forbidden positions in tuple matrix form {(row, column),...}
    forbidden_positions = {((node - 1) // num_cols, (node - 1) % num_cols) for node in forbidden_nodes}
    
    #testing
    print(f"testing: the nodes are {nodes}")
    print(f"testing: the forbidden nodes are {forbidden_nodes}")
    print(f"testing: the forbidden position are {forbidden_positions}")


    ### from here i used the help of AI and haven't advanced much
    # Identify valid row and column segments
    valid_row_segments = {}
    valid_col_segments = {}

    for i in range(num_rows):
        row_positions = [j for j in range(num_cols) if (i, j) not in forbidden_positions]
        if row_positions:
            valid_row_segments[i] = row_positions

    for j in range(num_cols):
        col_positions = [i for i in range(num_rows) if (i, j) not in forbidden_positions]
        if col_positions:
            valid_col_segments[j] = col_positions

    print(f'testing: valid_rows are: {valid_row_segments}, and valid_cols are: {valid_col_segments}')
    print(f'testing: length of valid_rows is: {sum(len(value) for value in valid_row_segments.values())}, and valid_cols is: {sum(len(value) for value in valid_col_segments.values())}')


    #create a matrix representing the board where the ones represent valid tiles and zeros represent forbidden tiles
    matrix = np.ones((num_rows, num_cols))

    #set the forbidden position as zeros and the rest are ones
    for i in range(1, num_rows * num_cols + 1):
        if i not in nodes:
            row = (i - 1) // num_cols
            col = (i - 1) % num_cols
            matrix[row, col] = 0  # Set to 0 for black

    #create a submatrix
    sub_matrix = matrix[np.ix_([0,1],[0,1])]
    print(sub_matrix)

    # Count the number of valid k-rook configurations and store them
    configurations = []

    def place_rooks(remaining_k, rows_left, cols_left, current_config):
        if remaining_k == 0:
            configurations.append(current_config[:])
            return

        # Start with an empty dictionary to track already checked positions
        for row in rows_left:
            for col in cols_left:
                if (row, col) in forbidden_positions:
                    continue
                if all(row != r and col != c for r, c in current_config):
                    # Create new sets excluding the current row and column
                    new_rows_left = rows_left - {row}
                    new_cols_left = cols_left - {col}
                    place_rooks(remaining_k - 1, new_rows_left, new_cols_left, current_config + [(row, col)])

    # Reset configurations each time the function runs
    configurations = []
    place_rooks(k, set(range(num_rows)), set(range(num_cols)), [])

    return len(configurations)

# Example usage
edge_list = [(1, 4), (3, 6), (4, 5), (5, 6)]
B = [[1, 2], [1, 8], [2, 3], [3, 4], [3, 10], [4, 5], [4, 11], [5, 12], [10, 11], [10, 17], [11, 12], [11, 18], [12, 13], [12, 19], [13, 20], [16, 17], [17, 18], [17, 24], [18, 19], [18, 25], [19, 20], [19, 26], [20, 21], [20, 27], [22, 29], [24, 25], [24, 31], [25, 26], [25, 32], [26, 27], [26, 33], [27, 34], [29, 30], [29, 36], [30, 31], [30, 37], [31, 32], [31, 38], [32, 33], [32, 39], [33, 34], [33, 40], [34, 35], [34, 41], [35, 42], [36, 37], [37, 38], [38, 39], [39, 40], [40, 41], [41, 42]]
k = 2
print(f'The number of valid configurations is: {k_rook_problem(edge_list, k)}')

在这里我添加了这些棋盘的图片 这是B：

这是edge_list：

所以TL;DR是我不知道如何计算（在Python中和一般情况下）在带有禁止牌的NxM板上排列k个车的可能方法的数量，我正在寻求帮助

Answer 1

好吧，这可行，尽管这段代码中有很多不喜欢的地方。 我基本上按照上面描述的进行操作。 我创建了所有有效点的列表。 然后，对于列表中的每个点，我都会屏蔽行和列，并递归调用求解器。 我为 2x3 网格找到 5 组 2 块（这符合我的论文思路），为 6x7 网格找到 455 组 2 块。 6x7 网格有 3,606 个 3 组、18,660 个 4 组和 67,602 个 5 组。除此之外，计算量也很大

def block_out( valid, x, y ):
    newly = set( (x,y) )

    dx, dy = x, y
    while (dx,dy) in valid:
        newly.add( (dx,dy) )
        dx -= 1
    dx, dy = x, y
    while (dx,dy) in valid:
        newly.add( (dx,dy) )
        dx += 1
    dx, dy = x, y
    while (dx,dy) in valid:
        newly.add( (dx,dy) )
        dy -= 1
    dx, dy = x, y
    while (dx,dy) in valid:
        newly.add( (dx,dy) )
        dy += 1

    return [pt for pt in valid if pt not in newly]


def k_rook_problem(edge_list, k):
    #finding the num of columns
    for edge in edge_list:
        if edge[1] != (edge[0] + 1):
            num_cols = edge[1] - edge[0]
            break

    #finding the num of rows
    y_max = max(y for _, y in edge_list)
    num_rows = (y_max + num_cols - 1) // num_cols  # Calculate number of rows

    print(f'testing: num rows and num cols are: {num_rows}, {num_cols}')

    # Set of all nodes in the edge list
    nodes = set()
    for edge in edge_list:
        nodes.add(edge[0])
        nodes.add(edge[1])

    # Make a list of all valid x,y pairs.

    valid = []
    for i in range(num_rows*num_cols):
        if i+1 in nodes:
            valid.append( (i%num_cols, i//num_cols) )
    print( valid )

    # For each one:

    found = set()
    def solve_this_one( valid, k, path ):
        nonlocal found
        tsp = tuple(sorted(path))
        if tsp in found:
            return
        if not k:
            found.add( tsp )
            print(len(found), end='\r')
            return
        for x,y in valid:
            remain = block_out( valid, x, y )
            solve_this_one( remain, k-1, path+[(x,y)] )

    solve_this_one( valid, k, [])
    print(found)
    print(len(found))
    return 0