Detailed mathematical approach

Problem Summary

The puzzle uses a \(4\times4\) board containing one white square \(W\), seven red squares \(R\), and eight blue squares \(B\). The initial board is

W R B B
R R B B
R R B B
R R B B

and the target board is

W B R B
B R B R
R B R B
B R B R

A legal move slides one colored square into the white square. The move letters \(L,R,U,D\) are the letters used in the checksum rule, so they describe the direction of the tile that moves, not the direction of the white square. Among all legal move sequences that transform the start board into the target board, we consider only those with minimum length.

For a move sequence \(m_1m_2\cdots m_\ell\), the checksum is defined by

$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}.$

The required answer is the sum of the final checksum over every shortest sequence.

Mathematical Approach

The heart of the problem is not numerical optimization but graph structure. We must identify the right state graph, isolate the shortest-path subgraph, and then accumulate the checksum over that restricted set of paths.

The State Graph of Colored Boards

Each board position is a state. Because the blue squares are indistinguishable from each other and the red squares are indistinguishable from each other, a state is determined completely by the position of the white square together with the set of positions occupied by the seven red squares; the eight blue squares fill the remaining cells automatically. So there are at most

$16\binom{15}{7}=102960$

different colorings to worry about, which makes a full graph search feasible.

Connect two states by an edge when one legal slide transforms one board into the other. This produces a finite unweighted graph \(G\). Every legal move is reversible, so if \(v\) is adjacent to \(w\), then \(w\) is also adjacent to \(v\). That reversibility is what makes two breadth-first searches enough to describe every shortest path.

Distances Pick Out Exactly the Shortest States

Let \(s\) be the start state and \(t\) the target state. Write \(d_s(v)\) for the graph distance from \(s\) to a state \(v\), and \(d_t(v)\) for the graph distance from \(v\) to \(t\). If

$D=d_s(t),$

then \(D\) is the minimum number of moves required by the problem.

A state \(v\) lies on at least one shortest path from \(s\) to \(t\) exactly when

$d_s(v)+d_t(v)=D.$

The proof is standard and important. If \(v\) lies on a shortest path, then the path splits into a shortest prefix from \(s\) to \(v\) and a shortest suffix from \(v\) to \(t\), so the two distances add to \(D\). Conversely, if the two distances add to \(D\), concatenating a shortest \(s\to v\) path with a shortest \(v\to t\) path gives a shortest \(s\to t\) path passing through \(v\).

Now orient an edge \(v\to w\) only when it advances one BFS layer from the start and still stays on a shortest route:

$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$

These are exactly the directed edges that can appear in a shortest solution. Since \(d_s\) strictly increases along every retained edge, the retained subgraph is a directed acyclic graph.

The Checksum Is a Linear Recurrence

Let \(\chi(L)=76\), \(\chi(R)=82\), \(\chi(U)=85\), and \(\chi(D)=68\). For a shortest path with move string \(m_1m_2\cdots m_\ell\), the checksum recurrence can be unrolled as

$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}.$

So the checksum is a polynomial hash of the move letters in base \(243\). The implementations update it one step at a time, but mathematically this closed form makes clear why the order of moves matters so strongly.

This linearity also gives a useful path-aggregation recurrence. If \(N(v)\) is the number of shortest-path prefixes ending at \(v\), and \(S(v)\) is the sum of their checksums, then for every shortest-path edge \(v\to w\) labeled by letter \(a\),

$N(w)\mathrel{+}=N(v),$

$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}.$

The current implementations do not materialize these two tables explicitly; instead they carry the running checksum during a depth-first traversal of the shortest-path DAG. But this recurrence is the mathematical reason that the traversal is correct.

Worked Example: The Sample Word \(LULUR\)

The sample move string \(LULUR\) is useful because it fixes the direction convention. Starting from the initial board and applying those five moves gives

R R B B
R B B B
R W R B
R R B B

and the checksum recurrence produces

$\operatorname{chk}(LULUR)=19761398.$

That example shows two problem-specific facts at once: the letters record tile directions, and the checksum is attached to the exact move string rather than to the destination state alone.

The Final Reduction

If \(\mathcal{P}_{\min}\) denotes the set of all shortest paths from \(s\) to \(t\), then the required quantity is simply

$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$

The search problem is therefore reduced to a finite DAG sum: find every shortest path and accumulate its rolling checksum. No longer paths need to be explored, because the distance identities above exclude them completely.

How the Code Works

Board Representation and Neighbor Generation

The C++, Python, and Java implementations encode each of the 16 cells with 2 bits, using one code for white, one for red, and one for blue. That packs the whole board into a 32-bit integer. From any encoded state, the implementation locates the white square, checks the at most four neighboring cells, swaps white with a legal neighbor, and records both the next state and the ASCII code associated with the move letter.

Building the Reachable Component and the Distance Arrays

A first breadth-first search starts from the initial board. It discovers every reachable state, assigns it an integer identifier, and stores its distance from the start. Once those states are known, the implementation builds an adjacency list for the entire reachable component. A second breadth-first search starts from the target and runs on the same reversible graph, producing the distance-to-target array. The shortest solution length is the target's distance from the start.

Traversing Only Shortest Solutions

The final traversal carries three pieces of information: the current state, the current depth, and the checksum of the move prefix used to get there. A transition is followed only if it advances one level from the start and still satisfies the shortest-path condition for the destination. When the traversal reaches depth \(D\), it contributes to the total only if the current state is the target. Because every retained edge increases depth by exactly one, the traversal never cycles.

The C++ and Java implementations additionally split the shortest-path DAG by short prefixes and let several workers explore disjoint subtrees before adding their local totals together. The Python implementation performs the same traversal serially.

Complexity Analysis

Let \(V\) be the number of reachable board states and \(E\) the number of legal transitions among them. Since every board position has degree at most 4, we have \(E=O(V)\). The state-discovery BFS, adjacency construction, and reverse BFS therefore take \(O(V+E)\) time and \(O(V+E)\) memory.

The final shortest-path traversal is output-sensitive. It is linear in the size of the shortest-path DAG plus the number of shortest-path prefixes actually explored. That is exactly the cost paid by the implementations, because they enumerate shortest solutions rather than compressing them into a separate dynamic program. The crucial saving is that the search never touches non-shortest continuations.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=244
2. Breadth-first search: Wikipedia - Breadth-first search
3. Shortest path problem: Wikipedia - Shortest path problem
4. 15 puzzle and sliding puzzles: Wikipedia - 15 puzzle
5. Directed acyclic graph: Wikipedia - Directed acyclic graph
6. ASCII: Wikipedia - ASCII