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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Das Puzzle verwendet ein \(4\times4\)-Brett mit genau einem weißen Feld \(W\), sieben roten Feldern \(R\) und acht blauen Feldern \(B\). Der Startzustand lautet
W R B B R R B B R R B B R R B B
und der Zielzustand lautet
W B R B B R B R R B R B B R B R
Ein legaler Zug schiebt ein benachbartes farbiges Feld in das weiße Feld. Die Buchstaben \(L,R,U,D\) sind genau die Buchstaben, die in die Prüfsumme eingehen; sie bezeichnen also die Bewegungsrichtung des geschobenen Steins und nicht die Bewegung des weißen Feldes. Unter allen Zugfolgen, die den Start in das Ziel überführen, interessieren nur die mit minimaler Länge.
Für eine Zugfolge \(m_1m_2\cdots m_\ell\) ist die Prüfsumme durch
$$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}$$
definiert. Gesucht ist die Summe der Endprüfsummen über alle kürzesten Zugfolgen.
Der Kern der Aufgabe ist ein Graphproblem. Man muss den richtigen Zustandsgraphen formulieren, daraus den kürzesten-Untergraphen isolieren und anschließend die Prüfsummen nur über dessen Wege aufsummieren.
Jede Brettbelegung ist ein Zustand. Weil alle blauen Steine untereinander ununterscheidbar sind und ebenso alle roten, wird ein Zustand vollständig durch die Position des weißen Feldes und die Menge der sieben roten Positionen bestimmt; die acht blauen Felder belegen automatisch den Rest. Damit gibt es höchstens
$$16\binom{15}{7}=102960$$
verschiedene Einfärbungen, und eine vollständige Graphsuche ist realistisch.
Verbinde zwei Zustände durch eine Kante, wenn ein legaler Schiebezug den einen in den anderen überführt. So entsteht ein endlicher ungewichteter Graph \(G\). Jeder Zug ist umkehrbar, also ist der Graph auf Zustandsniveau ungerichtet. Genau diese Umkehrbarkeit erlaubt es, mit zwei Breitensuchen alle kürzesten Wege zu charakterisieren.
Sei \(s\) der Startzustand und \(t\) der Zielzustand. Bezeichne mit \(d_s(v)\) den Graphabstand von \(s\) zu einem Zustand \(v\) und mit \(d_t(v)\) den Abstand von \(v\) nach \(t\). Mit
$$D=d_s(t)$$
ist \(D\) die minimale Zugzahl der Aufgabe.
Ein Zustand \(v\) liegt genau dann auf mindestens einem kürzesten Weg von \(s\) nach \(t\), wenn
$$d_s(v)+d_t(v)=D.$$
Liegt \(v\) auf einem kürzesten Weg, zerfällt dieser Weg in einen kürzesten Präfix \(s\to v\) und einen kürzesten Suffix \(v\to t\), also addieren sich die Distanzen zu \(D\). Umgekehrt liefert die Verkettung eines kürzesten Wegs von \(s\) nach \(v\) mit einem kürzesten Weg von \(v\) nach \(t\) wieder einen kürzesten Gesamtweg.
Eine gerichtete Kante \(v\to w\) behalten wir genau dann, wenn sie eine BFS-Ebene voranschreitet und trotzdem auf einem kürzesten Weg bleibt:
$$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$$
Das sind genau die Übergänge, die in einer kürzesten Lösung vorkommen können. Weil \(d_s\) entlang jeder behaltenen Kante strikt wächst, entsteht ein gerichteter azyklischer Graph.
Setze \(\chi(L)=76\), \(\chi(R)=82\), \(\chi(U)=85\) und \(\chi(D)=68\). Für einen kürzesten Weg mit Zugwort \(m_1m_2\cdots m_\ell\) lässt sich die Rekursion zu
$$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}$$
ausrollen. Die Prüfsumme ist also ein polynomialer Hash des Zugworts zur Basis \(243\).
Aus derselben Linearität folgt eine nützliche Aggregationsformel. Ist \(N(v)\) die Anzahl kürzester Präfixe bis \(v\) und \(S(v)\) die Summe ihrer Prüfsummen, dann gilt für jede kürzeste-Kante \(v\to w\) mit Buchstabe \(a\):
$$N(w)\mathrel{+}=N(v),$$
$$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}.$$
Die vorliegenden Implementierungen speichern diese Tabellen nicht explizit, sondern tragen die laufende Prüfsumme in einer Tiefensuche mit. Mathematisch erklärt diese Formel jedoch direkt, warum das Verfahren korrekt ist.
Das Beispielwort \(LULUR\) fixiert die Bewegungsrichtung eindeutig. Vom Startbrett aus erhält man nach diesen fünf Zügen
R R B B R B B B R W R B R R B B
und die Rekursion liefert
$$\operatorname{chk}(LULUR)=19761398.$$
Damit sieht man zugleich zwei problemspezifische Punkte: Die Buchstaben beschreiben die Richtung des geschobenen Steins, und die Prüfsumme hängt vom exakten Zugwort ab, nicht nur vom erreichten Zustand.
Bezeichnet \(\mathcal{P}_{\min}\) die Menge aller kürzesten Wege von \(s\) nach \(t\), so lautet die gesuchte Größe
$$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$$
Das ursprüngliche Puzzleproblem wird also zu einer endlichen Summation über einen DAG. Längere Wege spielen keine Rolle mehr, weil sie durch die Distanzbedingungen vollständig ausgeschlossen werden.
Die C++-, Python- und Java-Implementierungen codieren jede der 16 Zellen mit 2 Bits: ein Wert für Weiß, einer für Rot und einer für Blau. Damit passt das gesamte Brett in ein 32-Bit-Wort. Von einem codierten Zustand aus wird das weiße Feld lokalisiert, bis zu vier Nachbarn werden geprüft, und für jeden legalen Zug werden sowohl der Folgezustand als auch der zugehörige ASCII-Wert gespeichert.
Eine erste Breitensuche startet im Anfangsbrett. Sie entdeckt alle erreichbaren Zustände, vergibt ihnen laufende Kennungen und speichert die Distanz vom Start. Danach wird eine Adjazenzliste für diese gesamte erreichbare Komponente aufgebaut. Eine zweite Breitensuche beginnt im Zielzustand und läuft auf demselben reversiblen Graphen, um die Distanz-zum-Ziel für jeden Zustand zu bestimmen. Die Länge einer kürzesten Lösung ist dann einfach die Startdistanz des Zielzustands.
Die abschließende Traversierung führt drei Informationen mit: aktuellen Zustand, aktuelle Tiefe und Prüfsumme des bisherigen Präfixes. Ein Übergang wird nur dann verfolgt, wenn er genau eine Ebene voranschreitet und der Zielzustand weiterhin auf einem kürzesten Weg liegt. Erreicht die Traversierung die Tiefe \(D\), trägt sie nur dann zur Summe bei, wenn zugleich der Zielzustand erreicht wurde. Da jede behaltene Kante die Tiefe um genau 1 erhöht, kann kein Zyklus auftreten.
Die C++- und Java-Implementierungen teilen den DAG zusätzlich nach kurzen Präfixen auf und lassen mehrere Arbeiter disjunkte Teilbäume durchsuchen, bevor die lokalen Summen zusammengeführt werden. Die Python-Implementierung führt dieselbe Traversierung seriell aus.
Seien \(V\) die Anzahl erreichbarer Zustände und \(E\) die Anzahl legaler Übergänge zwischen ihnen. Da jedes Brett höchstens 4 Nachbarn hat, gilt \(E=O(V)\). Zustandsaufbau, Adjazenzkonstruktion und beide Breitensuchen kosten daher \(O(V+E)\) Zeit und \(O(V+E)\) Speicher.
Die abschließende Traversierung der kürzesten Wege ist ausgabeabhängig. Ihre Laufzeit ist linear in der Größe des kürzesten-Wege-DAGs plus der Anzahl der tatsächlich besuchten Präfixe. Genau diesen Preis zahlen die Implementierungen, weil sie die kürzesten Lösungen explizit traversieren statt sie in einer separaten DP zu komprimieren. Die entscheidende Einsparung ist, dass nie in nicht-kürzeste Fortsetzungen verzweigt wird.
Bulmaca, bir adet beyaz kare \(W\), yedi adet kırmızı kare \(R\) ve sekiz adet mavi kare \(B\) içeren \(4\times4\)'lük bir tahtada geçer. Başlangıç durumu
W R B B R R B B R R B B R R B B
ve hedef durum
W B R B B R B R R B R B B R B R
şeklindedir. Geçerli bir hamlede komşu bir renkli kare beyaz karenin yerine kaydırılır. Checksum tanımında kullanılan \(L,R,U,D\) harfleri de tam olarak bu kayan karenin yönünü anlatır; yani beyaz karenin gittiği yönü değil, renkli karenin kaydığı yönü kaydeder.
Bir hamle dizisi \(m_1m_2\cdots m_\ell\) için checksum
$$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}$$
bağıntısıyla tanımlanır. Sorulan şey, başlangıcı hedefe götüren tüm en kısa dizilerin son checksum değerlerinin toplamıdır.
Bu problem özünde bir durum grafı problemidir. Doğru durum uzayını kurup en kısa yol altgrafını ayırdıktan sonra, checksum'ları yalnızca bu yapı üzerinde toplamak yeterlidir.
Her tahta yerleşimi bir durumdur. Mavi kareler kendi aralarında ayırt edilmez, kırmızı kareler de kendi aralarında ayırt edilmez. Bu yüzden bir durum, beyaz karenin konumu ile yedi kırmızı karenin bulunduğu hücre kümesi tarafından tamamen belirlenir; kalan sekiz hücre zaten mavidir. Dolayısıyla dikkate alınabilecek farklı renklendirme sayısı en fazla
$$16\binom{15}{7}=102960$$
kadardır ve tam arama yapılabilir.
Bir geçerli kaydırma ile birbirine dönüşebilen iki durumu komşu sayarsak sonlu ve ağırlıksız bir grafik \(G\) elde ederiz. Her hamlenin tersi vardır; dolayısıyla durum düzeyinde bu grafik yönsüzdür. En kısa yolları tanımlamak için iki BFS'nin yeterli olmasının nedeni tam olarak bu tersinirliktir.
\(s\) başlangıç durumunu, \(t\) hedef durumu göstersin. \(d_s(v)\), \(s\)'den \(v\)'ye olan grafik mesafesi; \(d_t(v)\) ise \(v\)'den \(t\)'ye olan mesafe olsun. O zaman
$$D=d_s(t)$$
istenen en kısa çözüm uzunluğudur.
Bir \(v\) durumunun en az bir en kısa \(s\to t\) yolu üzerinde bulunması için ve ancak bunun için
$$d_s(v)+d_t(v)=D$$
eşitliği gerekir. Eğer \(v\) en kısa yol üzerindeyse, yol \(s\to v\) ve \(v\to t\) biçiminde iki kısa parçaya ayrılır. Tersine, bu iki mesafe \(D\)'yi veriyorsa o iki kısa yol birleştirilerek \(v\)'den geçen en kısa tam yol elde edilir.
Şimdi bir kenarı yalnızca başlangıçtan bir katman ilerliyor ve hâlâ en kısa yolda kalıyorsa yönlendirelim:
$$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$$
Bu koşulu sağlayan \(v\to w\) geçişleri, en kısa çözüm dizilerinde görünebilecek tam geçişlerdir. Her tutulmuş kenarda \(d_s\) değeri 1 arttığı için ortaya çıkan altgraf bir DAG'dir.
\(\chi(L)=76\), \(\chi(R)=82\), \(\chi(U)=85\), \(\chi(D)=68\) olsun. En kısa bir yolun hamle sözcüğü \(m_1m_2\cdots m_\ell\) ise checksum kapalı biçimde
$$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}$$
şeklinde yazılır. Yani checksum, tabanı \(243\) olan bir polinom-hash'tir.
Bu doğrusallık yol toplama için de kullanışlıdır. \(N(v)\) en kısa yol ön eklerinin sayısı, \(S(v)\) ise bu ön eklerin checksum toplamı olsun. Etiketi \(a\) olan her en kısa yol kenarı \(v\to w\) için
$$N(w)\mathrel{+}=N(v),$$
$$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}$$
elde edilir. Mevcut uygulamalar bu iki tabloyu açıkça tutmak yerine DFS sırasında anlık checksum taşır; ama bunun neden doğru olduğunu açıklayan matematik tam olarak bu bağıntıdır.
Resmî örnek olan \(LULUR\) dizisi yön konvansiyonunu netleştirir. Başlangıç tahtasından bu beş hamle uygulandığında
R R B B R B B B R W R B R R B B
durumu elde edilir ve checksum bağıntısı
$$\operatorname{chk}(LULUR)=19761398$$
sonucunu verir. Böylece hem harflerin kayan taş yönünü anlattığı hem de checksum'ın yalnızca son duruma değil, tam hamle dizisine bağlı olduğu görülür.
\(\mathcal{P}_{\min}\) başlangıçtan hedefe giden tüm en kısa yollar kümesi olsun. Aranan değer
$$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$$
Dolayısıyla problem, sonlu bir DAG üzerinde yapılan bir toplamaya indirgenir. Daha uzun bütün yollar mesafe koşulları nedeniyle baştan elenir.
C++, Python ve Java uygulamaları 16 hücrenin her birini 2 bit ile kodlar; bir kod beyazı, biri kırmızıyı, biri maviyi temsil eder. Böylece tüm tahta tek bir 32 bit tamsayıya sığar. Herhangi bir kodlu durumdan beyaz karenin yeri bulunur, en çok dört komşu denenir, ve her geçerli hamle için hem sonraki durum hem de ilgili ASCII değeri kaydedilir.
İlk BFS başlangıç tahtasından başlar. Erişilebilen bütün durumları keşfeder, her birine bir kimlik atar ve başlangıçtan olan uzaklığı saklar. Bu durumlar belli olduktan sonra bütün erişilebilir bileşen için komşuluk listesi kurulur. İkinci BFS hedef durumdan başlar ve aynı tersinir grafik üzerinde çalışarak her durum için hedefe uzaklığı hesaplar. En kısa çözüm uzunluğu da hedefin başlangıçtan uzaklığıdır.
Son geçişte üç bilgi taşınır: mevcut durum, mevcut derinlik ve bu noktaya kadar gelen hamlelerin checksum'ı. Bir komşuya ancak başlangıçtan tam bir seviye ilerliyorsa ve komşu hâlâ bir en kısa yol üzerinde kalıyorsa gidilir. Derinlik \(D\)'ye ulaşıldığında katkı yalnızca hedef duruma varılmışsa eklenir. Her tutulmuş kenar derinliği tam 1 artırdığı için dolaşım yapacak bir çevrim oluşmaz.
C++ ve Java uygulamaları ayrıca kısa ön ekleri ayrı görevlere ayırıp farklı işçilere dağıtır; sonra yerel toplamlar birleştirilir. Python uygulaması aynı aramayı tek iş parçacığında yapar.
\(V\) erişilebilir durum sayısı, \(E\) de bu durumlar arasındaki geçerli geçiş sayısı olsun. Her tahtanın derece değeri en çok 4 olduğundan \(E=O(V)\) olur. Durumları keşfetme, komşuluk listesini kurma ve iki BFS aşaması toplam \(O(V+E)\) zamanda ve \(O(V+E)\) bellekte çalışır.
Son en kısa yol gezintisi çıktı duyarlıdır. Çalışma süresi, en kısa yol DAG'inin boyutu ile gerçekten ziyaret edilen en kısa yol ön eki sayısının toplamı kadardır. Uygulamalar çözümleri açıkça dolaştığı için ödenen maliyet tam olarak budur. Asıl kazanç, en kısa olmayan hiçbir devam yoluna girilmemesidir.
El tablero es de \(4\times4\) y contiene una casilla blanca \(W\), siete casillas rojas \(R\) y ocho casillas azules \(B\). El estado inicial es
W R B B R R B B R R B B R R B B
y el estado objetivo es
W B R B B R B R R B R B B R B R
Un movimiento legal desliza una casilla coloreada adyacente hacia la casilla blanca. Las letras \(L,R,U,D\) son exactamente las que intervienen en el checksum, así que describen la dirección de la ficha que se desplaza, no la dirección de la casilla blanca. Entre todas las secuencias que llevan del inicio al objetivo, solo cuentan las de longitud mínima.
Para una secuencia \(m_1m_2\cdots m_\ell\), el checksum viene dado por
$$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}.$$
La respuesta pedida es la suma de los checksums finales de todas las secuencias mínimas.
La dificultad real del problema está en la estructura del grafo de estados. Primero se modela el rompecabezas como un grafo finito, luego se filtra el subgrafo de caminos mínimos y finalmente se acumula el checksum solo sobre esos caminos.
Cada configuración del tablero es un estado. Como todas las fichas azules son indistinguibles entre sí y todas las rojas también lo son, un estado queda determinado por la posición de la casilla blanca y por el conjunto de posiciones ocupadas por las siete fichas rojas; las ocho azules llenan automáticamente las casillas restantes. Por tanto, hay como mucho
$$16\binom{15}{7}=102960$$
coloraciones distintas.
Unimos dos estados con una arista si un deslizamiento legal transforma uno en el otro. Así obtenemos un grafo finito no ponderado \(G\). Cada movimiento puede deshacerse con el movimiento inverso, de modo que el grafo es reversible a nivel de estados. Esa reversibilidad es lo que permite caracterizar todos los caminos mínimos con dos búsquedas en anchura.
Sea \(s\) el estado inicial y \(t\) el objetivo. Denotemos por \(d_s(v)\) la distancia desde \(s\) hasta un estado \(v\), y por \(d_t(v)\) la distancia desde \(v\) hasta \(t\). Si
$$D=d_s(t),$$
entonces \(D\) es la longitud mínima buscada.
Un estado \(v\) pertenece a algún camino mínimo de \(s\) a \(t\) si y solo si
$$d_s(v)+d_t(v)=D.$$
Si \(v\) está en un camino mínimo, ese camino se parte en un prefijo mínimo \(s\to v\) y un sufijo mínimo \(v\to t\), así que las dos distancias suman \(D\). Recíprocamente, si la suma vale \(D\), concatenar un camino mínimo \(s\to v\) con uno mínimo \(v\to t\) produce un camino mínimo completo que pasa por \(v\).
Ahora orientamos una arista \(v\to w\) solo cuando avanza exactamente una capa desde el origen y todavía permanece dentro de un camino mínimo:
$$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$$
Estas son precisamente las transiciones que pueden aparecer en una solución mínima. Como \(d_s\) aumenta estrictamente en cada arista retenida, el subgrafo resultante es un DAG.
Tomemos \(\chi(L)=76\), \(\chi(R)=82\), \(\chi(U)=85\) y \(\chi(D)=68\). Para una palabra de movimientos \(m_1m_2\cdots m_\ell\), la recurrencia se desarrolla como
$$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}.$$
Así, el checksum es un hash polinómico en base \(243\) aplicado a la secuencia de movimientos.
Esa linealidad también da una recurrencia de agregación. Si \(N(v)\) es el número de prefijos mínimos que terminan en \(v\) y \(S(v)\) es la suma de sus checksums, entonces para cada arista mínima \(v\to w\) etiquetada por \(a\),
$$N(w)\mathrel{+}=N(v),$$
$$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}.$$
Las implementaciones presentes no almacenan explícitamente estas tablas; llevan el checksum acumulado durante un recorrido en profundidad del DAG. Pero esta fórmula es la explicación matemática de por qué ese recorrido suma exactamente lo correcto.
La palabra de ejemplo \(LULUR\) fija la convención de direcciones. Si se aplica al tablero inicial, el resultado es
R R B B R B B B R W R B R R B B
y la recurrencia produce
$$\operatorname{chk}(LULUR)=19761398.$$
Este ejemplo deja claras dos ideas: las letras describen la dirección de la ficha movida y el checksum depende de la palabra completa, no solo del estado final.
Si \(\mathcal{P}_{\min}\) es el conjunto de todos los caminos mínimos desde \(s\) hasta \(t\), la cantidad pedida es
$$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$$
En consecuencia, el problema se convierte en una suma finita sobre un DAG. Ningún camino más largo necesita explorarse, porque las identidades de distancia los excluyen por completo.
Las implementaciones en C++, Python y Java codifican cada una de las 16 celdas con 2 bits, usando un valor para blanco, otro para rojo y otro para azul. Así todo el tablero cabe en un entero de 32 bits. A partir de un estado codificado, la implementación localiza la casilla blanca, prueba hasta cuatro vecinos y, para cada movimiento legal, guarda tanto el estado siguiente como el código ASCII asociado a la letra del movimiento.
Una primera búsqueda en anchura parte del tablero inicial. Descubre todos los estados alcanzables, les asigna identificadores enteros y registra su distancia desde el origen. Con ese conjunto ya conocido, la implementación construye la lista de adyacencia de toda la componente alcanzable. Después ejecuta una segunda búsqueda en anchura desde el objetivo sobre el mismo grafo reversible para obtener la distancia a la meta de cada estado. La longitud mínima es simplemente la distancia del objetivo al origen.
El recorrido final mantiene tres datos: estado actual, profundidad actual y checksum del prefijo recorrido. Solo se sigue una transición si avanza exactamente un nivel desde el origen y el estado de destino sigue estando dentro de un camino mínimo. Cuando la profundidad alcanza \(D\), solo se añade contribución si el estado actual coincide con el objetivo. Como cada arista conservada incrementa la profundidad en 1, el recorrido no puede formar ciclos.
Las versiones en C++ y Java además reparten prefijos cortos entre varios trabajadores para explorar subárboles disjuntos y luego sumar sus resultados. La versión en Python hace el mismo recorrido de manera serial.
Sean \(V\) el número de estados alcanzables y \(E\) el número de transiciones legales entre ellos. Como cada tablero tiene grado a lo sumo 4, se cumple \(E=O(V)\). La construcción de estados, la lista de adyacencia y las dos BFS cuestan \(O(V+E)\) tiempo y \(O(V+E)\) memoria.
El recorrido final es sensible a la salida. Su coste es lineal en el tamaño del DAG de caminos mínimos más el número de prefijos mínimos realmente visitados. Ese es exactamente el precio pagado por las implementaciones, porque enumeran las soluciones mínimas en lugar de comprimirlas en una DP separada. La ganancia esencial es no entrar nunca en continuaciones que ya no pueden ser óptimas.
题目讨论的是一个 \(4\times4\) 的滑块棋盘。棋盘上有 1 个白色方块 \(W\)、7 个红色方块 \(R\) 和 8 个蓝色方块 \(B\)。初始状态为
W R B B R R B B R R B B R R B B
目标状态为
W B R B B R B R R B R B B R B R
一次合法操作是把某个与白格相邻的有色方块滑入白格。题目中的 \(L,R,U,D\) 不是白格移动的方向，而是滑入白格的那块方块的移动方向；这也是计算校验和时使用的字符。我们只考虑把初始棋盘变成目标棋盘的所有最短操作序列。
如果操作序列是 \(m_1m_2\cdots m_\ell\)，那么校验和按下面的递推定义：
$$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}.$$
要求的答案，就是所有最短序列最终校验和的总和。
这道题真正的核心不是某个单独的公式，而是三个对象如何配合：棋盘状态图、最短路分层结构，以及沿路径滚动更新的校验和。把这三个部分拼起来，问题就会从“枚举大量移动字符串”转化为“在一个有限 DAG 上求和”。
每一种棋盘排布都对应图中的一个顶点。由于所有蓝色方块彼此不可区分，所有红色方块也彼此不可区分，所以一个状态实际上只需要记录两类信息：白格在什么位置，以及 7 个红格分别在哪些位置。其余 8 个位置自然就是蓝格。因此，可能出现的不同着色状态最多只有
$$16\binom{15}{7}=102960$$
种，这说明完整搜索并不夸张。
如果一个合法滑动可以把状态 \(v\) 变成状态 \(w\)，就在图中连接一条边。这样得到的是一个有限、无权的状态图 \(G\)。更重要的是，每一步滑动都可以被反向滑回去，因此在忽略字母标签以后，这个状态图在本质上是可逆的。这一点意味着：从起点做一次 BFS，再从终点做一次 BFS，就足以把所有最短路径完整地筛出来。
记起点为 \(s\)，终点为 \(t\)。设 \(d_s(v)\) 表示从 \(s\) 到状态 \(v\) 的最短距离，\(d_t(v)\) 表示从状态 \(v\) 到 \(t\) 的最短距离。于是
$$D=d_s(t)$$
就是题目所求的最短步数。
一个状态 \(v\) 位于某条最短 \(s\to t\) 路径上，当且仅当
$$d_s(v)+d_t(v)=D.$$
理由很直接。如果 \(v\) 在一条最短路上，那么这条最短路可以在 \(v\) 处分成两段：从 \(s\) 到 \(v\) 的最短前缀，以及从 \(v\) 到 \(t\) 的最短后缀，所以两段长度之和必然等于 \(D\)。反过来，如果这两个距离之和等于 \(D\)，把一条最短的 \(s\to v\) 路与一条最短的 \(v\to t\) 路连接起来，就得到一条经过 \(v\) 的最短 \(s\to t\) 路。
进一步地，一条有向边 \(v\to w\) 会出现在某条最短解中，当且仅当它满足
$$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$$
第一条要求这一步确实把从起点出发的层数推进 1；第二条要求到达 \(w\) 之后仍然能以最短方式走到终点。所有满足这个条件的边组成一个有向无环图，因为沿着这些边走时 \(d_s\) 会严格递增，不可能回到旧层。
把四个字母映射成对应的 ASCII 值：
$$\chi(L)=76,\qquad \chi(R)=82,\qquad \chi(U)=85,\qquad \chi(D)=68.$$
对于移动串 \(m_1m_2\cdots m_\ell\)，递推
$$c_{i+1}\equiv 243c_i+\chi(m_{i+1})\pmod{100000007}$$
可以展开成闭式
$$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}.$$
这说明校验和其实就是以 \(243\) 为底、以移动字母 ASCII 值为系数的多项式哈希。因为不同位置的字符会乘上不同次幂，所以同样长度但顺序不同的路径，校验和通常完全不同。
线性结构还带来一个很自然的路径聚合递推。设 \(N(v)\) 是到达状态 \(v\) 的最短前缀条数，\(S(v)\) 是这些前缀校验和的总和。若最短路 DAG 中有一条标记为 \(a\) 的边 \(v\to w\)，则
$$N(w)\mathrel{+}=N(v),$$
$$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}.$$
含义很清楚：每一条到达 \(v\) 的前缀都可以延伸到 \(w\)，所以路径条数直接累加；而每条旧校验和都会先乘 \(243\)，再加上当前字母的 ASCII 值。现有实现并没有把这个 DP 表显式写出来，而是沿 DFS 路径直接维护当前校验和，但两种做法在数学上是完全一致的。
题目给出的样例串 \(LULUR\) 非常重要，因为它验证了方向约定。把它作用在初始棋盘上，会得到
R R B B R B B B R W R B R R B B
并且递推计算得到
$$\operatorname{chk}(LULUR)=19761398.$$
这个例子说明了两件事。第一，\(L\) 表示某块相邻方块向左滑入白格，因此白格本身实际上向右移动。第二，校验和绑定的是整条移动字符串，而不是单独的终点状态。
设 \(\mathcal{P}_{\min}\) 表示从 \(s\) 到 \(t\) 的所有最短路径集合，那么最终答案就是
$$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$$
因此，原题被精确地化简为：在最短路 DAG 上枚举所有根到终点的路径，并把各自的滚动校验和值加起来。所有非最短分支都会被距离条件自动剔除，不需要进入搜索。
C++、Python 和 Java 实现都把 16 个格子分别编码成 2 位：一个值表示白色，一个值表示红色，一个值表示蓝色。这样整块棋盘可以压缩进一个 32 位整数里。给定一个编码状态后，程序先找出白格位置，再检查最多四个相邻格，并通过交换白格与相邻有色格来生成后继状态，同时把对应的 ASCII 字符值一起记录下来。
第一遍 BFS 从初始棋盘开始，发现所有可达状态，为它们分配整数编号，并保存从起点出发的最短距离。随后，实现为整个可达连通块建立邻接表。第二遍 BFS 从目标棋盘出发，在同一个可逆状态图上计算每个状态到目标的最短距离。目标状态在第一遍 BFS 中的距离，就是最短解长度 \(D\)。
最后一次遍历维护三个量：当前状态、当前深度、以及到达这里时移动前缀的校验和。只有当某条边恰好把深度推进 1，并且目标状态仍满足最短路条件时，程序才会继续沿这条边走下去。当深度达到 \(D\) 时，只有当前状态正好是目标状态，当前校验和才会计入总和。由于保留下来的每条边都会让深度严格增加，因此遍历过程中不会出现环。
C++ 与 Java 版本还会先按短前缀把最短路 DAG 拆成若干互不重叠的子任务，再交给多个工作线程分别搜索并汇总局部结果。Python 版本执行的是同样的逻辑，只是串行完成。
记可达状态数为 \(V\)，合法状态转移数为 \(E\)。由于每个棋盘位置最多只有 4 个邻居，所以 \(E=O(V)\)。建立可达状态、构造邻接表以及两次 BFS 的总时间复杂度为 \(O(V+E)\)，空间复杂度也是 \(O(V+E)\)。
最终的最短路遍历是输出敏感的。它的代价与最短路 DAG 的规模以及实际访问到的最短路径前缀数量成正比。现有实现就是显式枚举这些最短解，所以这正是它们真正支付的复杂度。关键优化点在于：任何已经不可能属于最短解的分支，都会在距离判定处立刻被剪掉。
Рассматривается поле \(4\times4\) с одной белой клеткой \(W\), семью красными клетками \(R\) и восемью синими клетками \(B\). Начальное расположение равно
W R B B R R B B R R B B R R B B
а целевое расположение равно
W B R B B R B R R B R B B R B R
Допустимый ход состоит в том, что соседняя цветная клетка сдвигается на место белой. Буквы \(L,R,U,D\), входящие в определение контрольной суммы, обозначают именно направление движения этой цветной клетки, а не направление движения белой клетки. Среди всех последовательностей ходов нас интересуют только кратчайшие, переводящие старт в цель.
Для последовательности \(m_1m_2\cdots m_\ell\) контрольная сумма задается рекуррентно:
$$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}.$$
Нужно просуммировать конечные значения этой величины по всем кратчайшим решениям.
Здесь важно не столько само вычисление по модулю, сколько правильная геометрия пространства состояний. После этого задача сводится к суммированию по конечному DAG кратчайших путей.
Каждое расположение клеток рассматривается как вершина графа. Поскольку все синие клетки неразличимы между собой и все красные тоже неразличимы, состояние полностью задается положением белой клетки и множеством позиций семи красных клеток; остальные восемь позиций автоматически заняты синими. Значит, число различных раскрасок не превосходит
$$16\binom{15}{7}=102960.$$
Соединяем два состояния ребром, если один легальный сдвиг превращает одно в другое. Получается конечный невзвешенный граф \(G\). Каждый ход обратим, поэтому на уровне состояний граф фактически неориентированный. Именно эта обратимость позволяет полностью описать кратчайшие решения с помощью двух обходов в ширину.
Обозначим через \(s\) стартовое состояние, через \(t\) целевое. Пусть \(d_s(v)\) — длина кратчайшего пути от \(s\) до состояния \(v\), а \(d_t(v)\) — длина кратчайшего пути от \(v\) до \(t\). Тогда
$$D=d_s(t)$$
есть длина кратчайшего решения задачи.
Состояние \(v\) лежит хотя бы на одном кратчайшем пути из \(s\) в \(t\) тогда и только тогда, когда
$$d_s(v)+d_t(v)=D.$$
Если \(v\) находится на кратчайшем пути, то этот путь разбивается в \(v\) на кратчайший префикс \(s\to v\) и кратчайший суффикс \(v\to t\), поэтому длины складываются в \(D\). Обратно, если сумма двух расстояний равна \(D\), то соединение кратчайшего пути \(s\to v\) с кратчайшим путем \(v\to t\) дает кратчайший путь \(s\to t\), проходящий через \(v\).
Оставим ориентированное ребро \(v\to w\) только в том случае, если оно продвигает нас ровно на один слой BFS от старта и при этом не выводит из множества кратчайших решений:
$$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$$
Именно такие переходы могут встречаться в кратчайшем решении. Поскольку вдоль каждого оставленного ребра величина \(d_s\) строго возрастает, полученный подграф является DAG.
Положим \(\chi(L)=76\), \(\chi(R)=82\), \(\chi(U)=85\), \(\chi(D)=68\). Тогда для слова ходов \(m_1m_2\cdots m_\ell\) рекурсия разворачивается в форму
$$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}.$$
То есть контрольная сумма представляет собой полиномиальный хеш по основанию \(243\), где коэффициентами служат ASCII-коды букв ходов.
Из этой линейности следует и удобная формула агрегации. Пусть \(N(v)\) — число кратчайших префиксов, оканчивающихся в \(v\), а \(S(v)\) — сумма их контрольных сумм. Тогда для каждого ребра кратчайшего DAG \(v\to w\) с буквой \(a\) имеем
$$N(w)\mathrel{+}=N(v),$$
$$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}.$$
Текущие реализации не строят эти таблицы явно, а просто переносят текущее значение хеша вдоль DFS. Но именно эта формула показывает, почему такой обход суммирует нужную величину без потерь и без двойного счета.
Официальная строка \(LULUR\) удобна тем, что фиксирует соглашение о направлениях. Если применить ее к стартовой доске, получится состояние
R R B B R B B B R W R B R R B B
а рекурсия дает значение
$$\operatorname{chk}(LULUR)=19761398.$$
Этот пример одновременно показывает две вещи: буквы описывают движение цветной плитки, а контрольная сумма зависит от всей строки ходов, а не только от конечной позиции.
Если \(\mathcal{P}_{\min}\) обозначает множество всех кратчайших путей из \(s\) в \(t\), то искомая величина равна
$$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$$
Тем самым задача полностью сводится к конечной сумме по DAG кратчайших путей. Любые более длинные маршруты можно не рассматривать: они автоматически отсекаются условиями на расстояния.
Реализации на C++, Python и Java кодируют каждую из 16 клеток двумя битами: одно значение для белой, одно для красной и одно для синей клетки. В результате вся доска помещается в 32-битное целое. Для данного состояния программа находит позицию белой клетки, проверяет до четырех соседей и для каждого допустимого сдвига формирует следующее состояние вместе с ASCII-кодом соответствующей буквы.
Первый BFS стартует из начальной конфигурации. Он находит все достижимые состояния, присваивает им идентификаторы и сохраняет расстояния от старта. После этого строится список смежности всей достижимой компоненты. Второй BFS запускается из целевого состояния на том же обратимом графе и вычисляет расстояния до цели. Длина кратчайшего решения — это просто расстояние от старта до цели, уже полученное первым BFS.
В заключительном обходе хранятся текущая вершина, текущая глубина и контрольная сумма префикса. Переход разрешается только тогда, когда он увеличивает глубину ровно на 1 и состояние назначения по-прежнему удовлетворяет условию кратчайшего пути. Когда глубина достигает \(D\), вклад добавляется только в случае попадания в целевую вершину. Поскольку вдоль всех сохраненных ребер глубина строго растет, циклы невозможны.
В версиях на C++ и Java кратчайший DAG дополнительно разбивается по коротким префиксам, после чего разные рабочие потоки обходят непересекающиеся поддеревья и суммируют локальные результаты. В Python используется тот же алгоритм, но без распараллеливания.
Обозначим через \(V\) число достижимых состояний, а через \(E\) — число допустимых переходов между ними. Поскольку у каждой конфигурации не более 4 соседей, имеем \(E=O(V)\). Построение множества состояний, списка смежности и две BFS дают суммарно \(O(V+E)\) времени и \(O(V+E)\) памяти.
Финальный обход кратчайших путей является output-sensitive. Его стоимость линейна по размеру DAG кратчайших путей плюс по числу реально посещенных кратчайших префиксов. Именно эту цену и платят реализации, поскольку они перечисляют кратчайшие решения явно, а не сжимают их в отдельную динамику. Главное преимущество в том, что ни одна ветвь, уже вышедшая за пределы кратчайших путей, не исследуется.
لدينا لوحة منزلقات بحجم \(4\times4\) تحتوي على مربع أبيض واحد \(W\)، وسبعة مربعات حمراء \(R\)، وثمانية مربعات زرقاء \(B\). الحالة الابتدائية هي
W R B B R R B B R R B B R R B B
والحالة الهدف هي
W B R B B R B R R B R B B R B R
الحركة القانونية تعني أن مربعًا ملوّنًا مجاورًا ينزلق إلى مكان المربع الأبيض. الحروف \(L,R,U,D\) المستعملة في checksum تصف اتجاه حركة المربع الملوّن المنزلق، لا اتجاه حركة المربع الأبيض نفسه. ومن بين جميع السلاسل التي تنقل اللوحة من البداية إلى الهدف، نهتم فقط بالسلاسل الأقصر طولًا.
إذا كانت سلسلة الحركات هي \(m_1m_2\cdots m_\ell\)، فإن قيمة checksum تُعرَّف بالعلاقة
$$c_0=0,\qquad c_{i+1}\equiv 243c_i+\mathrm{ASCII}(m_{i+1}) \pmod{100000007}.$$
والمطلوب هو مجموع القيم النهائية لهذه العلاقة على جميع السلاسل الأقصر.
جوهر المسألة هو وصف فضاء الحالات بدقة، ثم استخراج البنية الخاصة بالمسارات الأقصر فقط، ثم جمع قيم checksum على تلك البنية دون الالتفات إلى أي التفاف أو مسار أطول.
كل ترتيب للوحة يمثل حالة واحدة. وبما أن جميع المربعات الزرقاء متماثلة فيما بينها، وجميع المربعات الحمراء متماثلة أيضًا، فإن الحالة تتحدد بالكامل من خلال موضع المربع الأبيض ومجموعة المواضع التي تشغلها المربعات الحمراء السبعة؛ أما المواضع الثمانية الباقية فستكون زرقاء تلقائيًا. لذلك لا يزيد عدد التلوينات الممكنة على
$$16\binom{15}{7}=102960.$$
نصل بين حالتين بحافة إذا كانت حركة انزلاق قانونية واحدة تنقل الأولى إلى الثانية. فنحصل على رسم بياني منتهٍ وغير موزون \(G\). وكل حركة يمكن عكسها مباشرة، لذلك يكون الرسم على مستوى الحالات قابلاً للعكس. وهذه الحقيقة هي التي تجعل إجراء بحثين بعرض الشجرة كافيًا لوصف جميع المسارات الأقصر.
لنرمز إلى الحالة الابتدائية بـ \(s\) وإلى الحالة الهدف بـ \(t\). ولتكن \(d_s(v)\) هي أقصر مسافة من \(s\) إلى الحالة \(v\)، ولتكن \(d_t(v)\) هي أقصر مسافة من \(v\) إلى \(t\). عندئذٍ
$$D=d_s(t)$$
هو طول الحل الأقصر المطلوب.
تقع الحالة \(v\) على مسار أقصر من \(s\) إلى \(t\) إذا وفقط إذا تحقق الشرط
$$d_s(v)+d_t(v)=D.$$
فإذا كانت \(v\) على مسار أقصر، فإن هذا المسار ينقسم عند \(v\) إلى بادئة أقصر من \(s\) إلى \(v\) ولاحقة أقصر من \(v\) إلى \(t\)، فيكون مجموع الطولين مساويًا لـ \(D\). والعكس صحيح أيضًا: إذا كان مجموع المسافتين يساوي \(D\)، فإن وصل مسار أقصر من \(s\) إلى \(v\) مع مسار أقصر من \(v\) إلى \(t\) يعطي مسارًا أقصر كاملًا يمر عبر \(v\).
أما الحافة الموجَّهة \(v\to w\) فإنها تنتمي إلى DAG الخاص بالمسارات الأقصر إذا وفقط إذا حققت
$$d_s(w)=d_s(v)+1,\qquad d_t(w)=D-d_s(w).$$
الشرط الأول يعني أننا تقدمنا طبقة واحدة من جهة البداية، والشرط الثاني يعني أن الوصول إلى \(w\) لم يخرجنا من طبقات الحل الأقصر. وبما أن \(d_s\) يزداد زيادة صارمة على كل حافة محتفظ بها، فإن البنية الناتجة تكون رسمًا موجهًا لا دوريًا.
لنكتب \(\chi(L)=76\)، و\(\chi(R)=82\)، و\(\chi(U)=85\)، و\(\chi(D)=68\). عندئذٍ يمكن فك العلاقة التكرارية لسلسلة الحركات \(m_1m_2\cdots m_\ell\) إلى الصيغة
$$\operatorname{chk}(m_1\cdots m_\ell)\equiv \sum_{i=1}^{\ell}\chi(m_i)\,243^{\ell-i}\pmod{100000007}.$$
أي أن checksum هو في الحقيقة hash كثير حدود أساسه \(243\) ومعاملاته هي قيم ASCII لحروف الحركات. ولهذا يختلف الناتج عادة عند تبديل ترتيب الحروف حتى لو كان الطول نفسه.
ومن الخطية نفسها نحصل على علاقة تجميع طبيعية على DAG. إذا رمزنا بـ \(N(v)\) إلى عدد البوادئ الأقصر التي تنتهي في \(v\)، وبـ \(S(v)\) إلى مجموع قيم checksum لهذه البوادئ، فعلى كل حافة أقصر \(v\to w\) تحمل الحرف \(a\) يكون
$$N(w)\mathrel{+}=N(v),$$
$$S(w)\mathrel{+}=243\,S(v)+\chi(a)\,N(v)\pmod{100000007}.$$
التنفيذات الحالية لا تبني هاتين الجدولتين صراحة، بل تحمل قيمة checksum الجارية أثناء DFS. لكن هذه العلاقة هي التفسير الرياضي المباشر لصحة ذلك الأسلوب.
السلسلة التجريبية \(LULUR\) مفيدة لأنها تثبت اتفاقية الاتجاه. عند تطبيقها على اللوحة الابتدائية نحصل على
R R B B R B B B R W R B R R B B
وتعطي العلاقة التكرارية القيمة
$$\operatorname{chk}(LULUR)=19761398.$$
وهذا يوضح حقيقتين خاصتين بالمسألة: الحروف تصف اتجاه البلاطة المنزَلِقة، وchecksum يعتمد على سلسلة الحركات كاملة لا على الحالة النهائية وحدها.
إذا كانت \(\mathcal{P}_{\min}\) هي مجموعة جميع المسارات الأقصر من \(s\) إلى \(t\)، فإن الكمية المطلوبة تساوي
$$\boxed{\sum_{P\in\mathcal{P}_{\min}}\operatorname{chk}(P).}$$
وبذلك تتحول المسألة إلى جمع منتهٍ على DAG للمسارات الأقصر. أما المسارات الأطول فتُستبعد كليًا بواسطة شروط المسافة، فلا حاجة إلى استكشافها أصلًا.
تنفّذ نسخ C++ وPython وJava ترميزًا لكل خلية من الخلايا الست عشرة باستعمال بتّين: قيمة للأبيض وقيمة للأحمر وقيمة للأزرق. وهكذا تُضغط اللوحة كلها في عدد صحيح من 32 بت. انطلاقًا من حالة مرمّزة، يحدد التنفيذ موضع المربع الأبيض، ويفحص حتى أربعة جيران، ويولّد لكل حركة قانونية الحالة التالية مع قيمة ASCII المرتبطة بالحرف الموافق.
يبدأ البحث الأول بعرض الشجرة من اللوحة الابتدائية. فيكتشف جميع الحالات القابلة للوصول، ويمنح كل حالة معرّفًا عدديًا، ويسجل بعدها عن البداية. وبعد معرفة هذه المجموعة، تُبنى قائمة تجاور للمركبة كلها. ثم يبدأ بحث ثانٍ بعرض الشجرة من الحالة الهدف على الرسم نفسه القابل للعكس، فيحسب المسافة إلى الهدف لكل حالة. وطول الحل الأقصر هو ببساطة مسافة الهدف عن البداية.
يحمل الاجتياز الأخير ثلاث معلومات: الحالة الحالية، والعمق الحالي، وchecksum لبادئة الحركات التي أوصلت إليها. ولا تُتبع أي حافة إلا إذا كانت تنقلنا طبقة واحدة إلى الأمام من جهة البداية، وإذا كانت الحالة الناتجة ما تزال ضمن طبقات الحل الأقصر. وعندما يصل العمق إلى \(D\)، لا تُضاف مساهمة إلى المجموع إلا إذا كانت الحالة الحالية هي الهدف نفسه. وبما أن كل حافة محتفظ بها تزيد العمق بمقدار 1، فلا يمكن أن تظهر دورات أثناء الاجتياز.
كما أن نسختي C++ وJava تقسمان DAG إلى مهام أصغر بحسب بوادئ قصيرة، ثم توزعان تلك المهام على عدة عمّال قبل جمع المجاميع المحلية. أما نسخة Python فتطبق المنطق نفسه بصورة تسلسلية.
إذا رمزنا بعدد الحالات القابلة للوصول بـ \(V\)، وبعدد الانتقالات القانونية بينها بـ \(E\)، فإن \(E=O(V)\) لأن درجة أي حالة لا تتجاوز 4. لذلك فإن بناء الحالات وقائمة التجاور وإجراء بحثي BFS يكلّف \(O(V+E)\) زمنًا و\(O(V+E)\) ذاكرة.
أما الاجتياز النهائي للمسارات الأقصر فهو حساس للمخرجات. فزمنه يتناسب مع حجم DAG للمسارات الأقصر ومع عدد البوادئ الأقصر التي تُزار فعليًا. وهذا هو التعقيد الحقيقي الذي تدفعه التنفيذات لأنها تعدّد الحلول الأقصر بدل ضغطها في برمجة ديناميكية منفصلة. والميزة الحاسمة هي أن أي امتداد لم يعد صالحًا كحل أقصر يُقصى فورًا.