Detailed mathematical approach

Problem Summary

This problem asks for the number of distinct positions reachable in a fixed sliding block puzzle. The board has size \(5\times 6\), so it contains \(30\) cells. The given starting arrangement uses two red L-trominoes, two green L-trominoes of the mirrored orientation, two vertical dominoes, six single squares, one \(2\times 2\) square, and one horizontal domino. Altogether these pieces occupy \(28\) cells, so exactly two cells are empty in every legal position.

A legal move chooses one piece and slides it horizontally or vertically by a positive number of cells. The piece may not rotate, leave the board, or overlap another piece. The task is to count every position reachable from the initial one, not just the positions at minimum distance. The state space is large, but it is still finite, so the problem can be solved by building the reachable part of the state graph exactly.

Mathematical Approach

Let \(\mathcal{S}\) be the set of all legal board positions for this puzzle, and let \(s_0\in\mathcal{S}\) be the given start. If one legal slide transforms \(s\) into \(t\), we place a directed edge \(s\to t\). The required quantity is therefore

$A=\left|\operatorname{Reach}(s_0)\right|,$

where \(\operatorname{Reach}(s_0)\) is the set of states reachable from \(s_0\) by zero or more legal moves.

Step 1: Model Every Piece by an Anchor and an Occupancy Mask

For each piece family, fix an anchor cell and list the occupied offsets relative to that anchor. If a piece of family \(F\) is placed at anchor \(a=(r,c)\), its occupied cells are

$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j.$

A board position is legal exactly when all chosen masks are pairwise disjoint and remain inside the \(5\times 6\) rectangle. If state \(s\) contains piece anchors \(a_1,\dots,a_m\), its total occupancy set is

$O(s)=\bigcup_{i=1}^{m} M_i(a_i).$

Now suppose piece \(i\) moves from anchor \(a_i\) to a new anchor \(a_i'\). That new placement is collision free precisely when

$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing.$

This is the geometric core of the algorithm. In the implementation each occupancy set is stored as a bitmask over the \(30\) board cells, so this condition becomes a single bit-intersection test.

Step 2: Canonicalize Identical Pieces

Several pieces are indistinguishable within their own family: there are two red L-pieces, two green L-pieces, two vertical dominoes, and six single-square pieces. If we assigned labels to those pieces, the same geometric board position would appear many times under harmless permutations. To avoid overcounting, each repeated family is stored as a sorted list of anchors.

That turns each family into a combination rather than an ordered tuple. On the \(5\times 6\) board, the available anchor counts are:

$20,\ 20,\ 24,\ 30,\ 20,\ 25,$

corresponding respectively to the two red L-pieces, the two green L-pieces, the two vertical dominoes, the six single squares, the \(2\times 2\) square, and the horizontal domino. Therefore the repeated families contribute the combination counts

$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6},$

while the two unique pieces contribute factors \(20\) and \(25\). So a collision-free canonical state fits naturally into a finite mixed-radix key space of size

$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$

Most keys do not correspond to legal reachable positions, but this count tells us that a compact exact encoding is possible.

Step 3: Rank Each Sorted Anchor Set with the Combinatorial Number System

If a repeated family uses sorted anchors

$0\le a_0<a_1<\cdots<a_{k-1},$

its combination rank is

$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}.$

This is the standard combinadic ranking formula. It assigns a unique integer in the range \(0\) to \(\binom{n}{k}-1\) to every \(k\)-subset of \(\{0,\dots,n-1\}\). Using that rank for each repeated family, and the plain anchor index for each unique piece, we can pack the whole state into one collision-free integer by mixed radix composition.

The important mathematical point is that canonicalization and ranking commute with reachability: two states are considered equal exactly when every family occupies the same anchor set, so the encoding loses no information relevant to the puzzle.

Step 4: Generate the Entire Reachable State Graph

Starting from \(s_0\), we perform a breadth-first traversal of the state graph. When a state is removed from the queue, the algorithm reconstructs its full occupancy mask, then examines every piece and every direction.

For a chosen direction, the piece is advanced one anchor step at a time until either the board boundary is reached or a collision would occur. Every intermediate legal anchor gives a distinct legal slide distance, hence a distinct outgoing edge of the graph. After the moved family is canonicalized again, the resulting state is encoded and inserted into the visited set if it has not been seen before.

Because each canonical state is processed once, the final answer is simply the number of visited keys:

$A=\left|\mathcal{V}\right|.$

Worked Example: The Smaller Checkpoint Puzzle

The implementation also contains a smaller \(3\times 4\) checkpoint puzzle with one L-tromino and seven single squares. This board has \(12\) cells, of which \(10\) are occupied, so again there are exactly two empty cells.

For that smaller puzzle the L-piece has \(6\) possible anchors, while the seven single squares form a sorted \(7\)-subset of the \(12\) board cells. Hence the natural state count before legality checks is

$6\binom{12}{7}=6\cdot 792=4752.$

A perfect key is obtained by taking the combination rank of the seven single-square anchors and then appending the L-anchor as the final radix-\(6\) digit:

$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$

Running the same reachability traversal on that reduced puzzle produces exactly \(208\) states. This checkpoint is useful because it shows the whole method on a board small enough to reason about directly, while using the same canonical encoding and move-generation logic as the full puzzle.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical model of the state space. They begin by precomputing a small binomial table for combinadic ranking and, for every admissible anchor of every piece family, the occupied-cell mask together with the neighboring anchor reached by moving one step in each of the four directions.

The C++ and Python implementations then perform the actual graph traversal. For each visited state they assemble the global occupancy mask once, remove the moved piece temporarily, and test candidate placements with a constant-time mask intersection. Repeated families are sorted immediately after a move, encoded into a unique integer key, and inserted into the visited structure only if they are new.

The Java implementation uses the same underlying mathematical strategy but delegates the heavy enumeration to the optimized C++ solver and returns the parsed numeric result. So all three language paths agree on the same state definition, the same legal-move rule, and the same exact answer.

Complexity Analysis

Let \(V=\left|\operatorname{Reach}(s_0)\right|\) be the number of reachable states and let \(E\) be the number of legal directed moves between them. The precomputation of masks, neighbor anchors, and small binomial values is \(O(1)\) for this fixed puzzle size. The graph traversal itself processes each discovered state once and examines each legal outgoing move once, so the overall running time is

$O(V+E).$

The visited set and queue store at most one record per reachable state, so the memory usage is

$O(V).$

Since the board dimensions and the multiset of pieces are fixed, the per-state work is bounded by a puzzle-specific constant. In that sense the actual program behaves essentially linearly in the number of reachable states.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=766
2. Sliding puzzle background: Wikipedia - Sliding puzzle
3. Breadth-first search: Wikipedia - Breadth-first search
4. Combinatorial number system: Wikipedia - Combinatorial number system
5. Bitwise operations: Wikipedia - Bitwise operation