0

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: enter image description here

and here's edge_list:

enter image description here

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

Improve this question
11
  • What's the meaning/effect of a "missing/forbidden" tile? And can you show an example plot? Commented Aug 27, 2024 at 21:12
  • @nocomment thanks for reminding me, I completely forgot. and their effect is that they act as a "barrier" to the rooks, in the edge_list case (the 2x3) a valid positioning for 2 rooks are the two top tiles even though it's in the same row, same is true for the second column in B (the 6x7) where you can have 3 rooks in the same column because of those forbidden tiles. Commented Aug 27, 2024 at 21:26
  • I still don't understand what the "edge_list" represents. Is that the attack space of each rook? Or is this a traditional rook, which can attack anywhere along a row or column, except for the blocks? Are B and edge_list just two different chessboards to be tested? Commented Aug 27, 2024 at 21:45
  • @TimRoberts, those are traditional rooks, edge_list is a graph of edges that after some fiddling around in the code you can just treat it as the board itself, B and edge_list are two different boards configurations which I posted their look in the question Commented Aug 27, 2024 at 22:01
  • @TimRoberts about the brute force solution, it seems too expensive, we're talking about around something close to O((MN)^(MN)) (just winging it in the O notation but I bet its an absurd growth rate) Commented Aug 27, 2024 at 22:06

1 Answer 1

Reset to default
0

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I think you may be over-counting. I've calculated in two different ways the (one naive brute force, one math-centric) the solutions for the 6x7 case to be {2: 455, 3: 2832, 4: 9107, 5: 15276, 6: 12886, 7: 4988, 8: 684}
I haven't found any issues. Perhaps me you could post a link to your list of spots for k=3, or to your solving code, and I'll compare it to mine.
I don't have my brute force solver anymore, and I'm not sure how helpful the purely math one would be since it just counts them without producing each. I was able to identify the incorrect solutions however, there are exactly 774 for k=3, which matches my count. Here's the first 5: ((2, 1), (3, 0), (3, 5)), ((2, 0), (2, 5), (5, 1)), ((2, 1), (2, 5), (3, 3)), ((3, 0), (3, 2), (4, 1)), ((3, 4), (5, 1), (6, 4)),]
I'll still probably share the pure-math one once I get it cleaned up a bit.
You're right, there's a bug. I see it now. I'll post a fix shortly.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.