Найти количество возможных k неатакующих ладей на шахматной доске NxM с запрещенными плитками? ⇐ Python

[Anonymous]

У меня есть неполная шахматная доска 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:
[img]https: //i.sstatic.net/82zuqIaT.png[/img]
а вот Edge_list:


так что TL;DR заключается в том, что я не знаю, как вычислять (в Python и в вообще) количество возможных способов расставить k ладей на доске NxM с запрещенными плитками, и я прошу помощи

Подробнее здесь: https://stackoverflow.com/questions/789 ... ard-with-f