Sliding rooks (and queens)

Introduction

Jacob Brazeal describes the following interesting puzzle in a recent MAA article (see reference below): starting with four rooks in the four corner squares of a chessboard, as shown in the figure below, move the rooks into the four center squares… where each single move is constrained to sliding a single rook, either horizontally along its rank or vertically along its file, as far as possible, “blocked” only by another rook or the edge of the board.

Starting configuration (left) and goal configuration (right) of sliding rooks puzzle.

Note that going in the other direction is easy– we can move the rooks from the center out to the corners in just 8 moves. But this problem is harder; it’s a nice programming exercise to determine the minimum number of moves required. The motivation for this post is to describe a slightly different approach to the problem than presented in the article, as well as a variant of the problem using queens instead of rooks that also has some interesting mathematical structure.

All of the code is available on GitHub.

Breadth-first search

We can view this problem as a directed graph, with a vertex for each possible state of the board, and a directed edge if we can move a single rook in state to obtain state . The goal is to find a minimum-length path from the starting vertex with the rooks at the corners to the goal vertex with the rooks in the center of the board.

It’s an interesting question whether there is a convenient admissible heuristic estimate of the number of moves required from a given board state, that would allow a more efficient informed search. I couldn’t come up with one; fortunately, simple breadth-first search turns out to be acceptably efficient for this problem:

from collections import deque

def bfs(neighbors, root):
    """Breadth-first search.

    Given a graph neighbors:V->V* and a root vertex, returns (p, d),
    where p[v] is the predecessor of v on the path from the root, and
    d[v] is the distance to v from the root.
    """
    queue = deque([root])
    parent = {root: None}
    distance = {root: 0}
    while queue:
        vertex = queue.popleft()
        for neighbor in neighbors(vertex):
            if neighbor not in parent:
                parent[neighbor] = vertex
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return (parent, distance)

It turns out that a minimum of 25 moves are required to solve the puzzle. That’s a lot– too many, really, so that this would probably not be very fun to explore by hand with an actual chess board (more on this shortly). And there are other configurations that are even more difficult to reach. The board that is “farthest” from the initial rooks-in-the-corners state is shown below, requiring 32 moves to reach:

The most difficult sliding rooks configuration, requiring 32 moves to reach.

Symmetry group action

How large is the directed graph that we need to explore? The referenced article describes a graph with =635,376 vertices, one for each possible subset of four squares in which to place the rooks. This graph has some interesting structure, with one really large strongly connected component explored by the above search algorithm, containing 218,412– over one-third– of all possible board states. The remainder is made up of a large number of much smaller unreachable components: the next largest component contains just 278 vertices!

However, these numbers count configurations of rooks that are not usefully distinct. For example, the figure above shows just one of eight “different” vertices, all of which require 32 moves to reach from the initial vertex… but the other seven board states are merely rotations and/or mirror reflections of the board shown in the figure, and thus are reachable by correspondingly rotated and/or reflected versions of the same sequence of 32 moves.

In other words, let’s consider the dihedral group of symmetries of the board acting on the set of possible board states, and construct the (smaller) directed graph with a vertex for each orbit of that group action.

A standard trick for implementing this approach is to represent each orbit by one of its elements, chosen in some natural and consistent way; and a standard trick for making that choice is to impose some convenient total order on the set, and choose the least element of each orbit as its representative. In the case of this problem, as we encounter each board state v during the search, we “rename” it as min(orbit(v)), the lexicographically least tuple of rotated and/or reflected coordinates of the rook positions:

def orbit(pieces):
    """Orbit of dihedral group action on rooks on a chess board."""
    for k in range(4):
        yield pieces
        yield tuple(sorted((n - 1 - x, y) for (x, y) in pieces))    # reflect
        pieces = tuple(sorted((n - 1 - y, x) for (x, y) in pieces)) # rotate

This search space is almost– but not quite– eight times smaller. From the initial rooks-in-the-corners board state, we can reach 27,467 configurations unique up to rotations and reflections, out of a total of 79,920 possible configurations. We can compute the latter number without actually enumerating all possible board states: the cycle index of the dihedral group acting on the squares of an board (assuming is even) is

and the number of possible board states with rooks is

Sliding queens instead of rooks

Finally, I think perhaps a more “fun” variant of this problem is to consider four queens in the corners, and try to move them to the four center squares as before, using the same “maximal” moves, but allowing diagonal moves as well as horizontal and vertical. This is more tractable to solve by hand, requiring only 12 moves to complete.

And the structure of the corresponding graph is also rather interesting: the large connected component is even larger, so that we can now reach 77,766 of the 79,920 possible configurations of four queens… but the remaining 2,154 configurations are all singleton components! That is, from any one of these 2,154 “lone” configurations, we can move into the large component with just a single move, and from there reach any of those 77,766 configurations… but we can’t get back, nor can we reach any of the other 2,153 lone unreachable configurations!

This was interesting enough that I wondered if it was true in general for other board sizes. It’s trivially true for 2×2 and 4×4 (since there are no unreachable board states), as well as 6×6, 8×8, and even 10×10… but unfortunately the pattern does not continue; the 12×12 board has larger-than-singleton connected components not reachable from the initial queens-in-the-corners state.

Reference:

1. Brazeal, J., Slides on a Chessboard, Math Horizons, 27(4) April 2020, p. 24-27 [link]