# finding the number of possible k non-attacking rooks in an NxM chessboard with forbidden tiles?

## I have an NxM incomplete chessboard (meaning an NxM chessboard with some tiles missing) and a number k (which is the number of non-attacking rooks I need to place on the board) the inputs of this function are an edge list (which can be thought of as a matrix that starts at index 1 and the top left is the "first" tile) and the number k. I've created a function that plots the board to give a better visual understanding of the problem: 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) now for the main function that is supposed to take the edge list and k, and output the number of possible ways to arrange k rooks in that board; in this function so far I was able to extract the dimensions of the chessboard (rows and columns) and the positions of the forbidden positions which currently I store in a set of tuples where the tuples are formatted the following way (row, column) (I also made the index to start at 0 to align with a matrix that represents the board) but from after that point, where all is left for me to do is actually calculate the number of possible ways to arrange k rooks in that board and I don't know how to do so. 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_po

I have an NxM incomplete chessboard (meaning an NxM chessboard with some tiles missing) and a number k (which is the number of non-attacking rooks I need to place on the board)

the inputs of this function are an edge list (which can be thought of as a matrix that starts at index 1 and the top left is the "first" tile) and the number k.

I've created a function that plots the board to give a better visual understanding of the problem:

```
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)
```

now for the main function that is supposed to take the edge list and k, and output the number of possible ways to arrange k rooks in that board; in this function so far I was able to extract the dimensions of the chessboard (rows and columns) and the positions of the forbidden positions which currently I store in a set of tuples where the tuples are formatted the following way (row, column) (I also made the index to start at 0 to align with a matrix that represents the board) but from after that point, where all is left for me to do is actually calculate the number of possible ways to arrange k rooks in that board and I don't know how to do so.

```
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)}')
```

here I'm adding the pic of what these chessboard look like here's B:

and here's edge_list:

so the TL;DR is that I don't know how to calculate (in Python and in general) the number of possible ways to arrange k rooks on an NxM board with forbidden tiles, and I'm asking for help