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

Question

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

Answer 1

OK, this works, although there are plenty of things not to like in this code. I do basically what I describe above. I create a list of all valid points. Then, for every point in the list, I block out the row and column, and call the solver recursively. I find 5 sets of 2 for the 2x3 grid (which matches my paper thinking), and 455 sets of 2 for the 6x7 grid. There are 2,832 sets of 3 for the 6x7 grid; 9,107 sets of 4; 15,276 sets of 5; and 12,886 set of 6. It gets computationally intensive beyond that

def block_out( basis. valid, x, y ):
    newly = set([(x,y)])

    dx, dy = x, y
    while (dx,dy) in basis:
        if (dx,dy) in valid:
            newly.add( (dx,dy) )
        dx -= 1
    dx, dy = x, y
    while (dx,dy) in basis:
        if (dx,dy) in valid:
            newly.add( (dx,dy) )
        dx += 1
    dx, dy = x, y
    while (dx,dy) in basis:
        if (dx,dy) in valid:
            newly.add( (dx,dy) )
        dy -= 1
    dx, dy = x, y
    while (dx,dy) in basis:
        if (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 )
    basis = 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( basis, valid, x, y )
            solve_this_one( remain, k-1, path+[(x,y)] )

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

Followup

Thanks to Dillon Davis for pointing out the problem in my original code. Here's the bug, for those following along at home. Let's say I placed a rook at (2,1). I then removed column 2 and row 1 from the "valid" list. Next, I looked at (3,0). I went to eliminate column 3, but since (3,1) had been removed earlier, I stopped looking down that column. That left the remainder of column 3 as being "valid", when it was not. The answer was to compare against the ORIGINAL list of squares, not the currently remaining list of squares.