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.
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.
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.
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.
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.
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|.$$
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.
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.
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.
Gesucht ist die Anzahl aller verschiedenen Stellungen, die in einem festen Schiebeblock-Puzzle von der vorgegebenen Startstellung aus erreichbar sind. Das Brett hat die Groesse \(5\times 6\) und damit \(30\) Felder. Die Startkonfiguration besteht aus zwei roten L-Trominos, zwei grueneren L-Trominos in gespiegelter Orientierung, zwei vertikalen Dominos, sechs Einzelfeldern, einem \(2\times 2\)-Quadrat und einem horizontalen Domino. Diese Steine belegen zusammen \(28\) Felder, also bleiben in jeder legalen Stellung genau zwei Felder frei.
Ein legaler Zug waehlt genau einen Stein und verschiebt ihn horizontal oder vertikal um eine positive Anzahl von Feldern. Dabei darf der Stein nicht rotiert werden, das Brett nicht verlassen und keinen anderen Stein ueberdecken. Gezaehlt werden alle von der Startlage aus erreichbaren Positionen, nicht nur diejenigen in minimaler Zugzahl. Der Zustandsraum ist gross, aber endlich, daher kann man den erreichbaren Teil des Zustandsgraphen exakt konstruieren.
Sei \(\mathcal{S}\) die Menge aller legalen Brettstellungen dieses Puzzles, und sei \(s_0\in\mathcal{S}\) die Startstellung. Wenn ein legaler Schiebezug \(s\) in \(t\) ueberfuehrt, tragen wir eine gerichtete Kante \(s\to t\) ein. Gesucht ist also
$$A=\left|\operatorname{Reach}(s_0)\right|,$$
wobei \(\operatorname{Reach}(s_0)\) die Menge aller Zustaende bezeichnet, die man aus \(s_0\) durch null oder mehr legale Zuege erreicht.
Fuer jede Steinart wird eine Ankerzelle festgelegt und die Liste der relativ dazu belegten Offsets gespeichert. Liegt ein Stein der Familie \(F\) beim Anker \(a=(r,c)\), dann sind seine belegten Zellen
$$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j.$$
Eine Brettstellung ist genau dann legal, wenn alle gewaelten Masken paarweise disjunkt sind und innerhalb des \(5\times 6\)-Rechtecks bleiben. Enthalten die Anker eines Zustands \(s\) die Werte \(a_1,\dots,a_m\), dann ist die Gesamtbelegung
$$O(s)=\bigcup_{i=1}^{m} M_i(a_i).$$
Wenn nun Stein \(i\) von \(a_i\) nach \(a_i'\) bewegt werden soll, ist die neue Lage genau dann kollisionsfrei, wenn
$$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing.$$
Das ist der geometrische Kern des Verfahrens. In der Implementierung wird jede Belegung als Bitmaske ueber den \(30\) Brettfeldern gespeichert, sodass diese Bedingung auf einen einzigen Bit-Schnitt-Test reduziert wird.
Mehrere Steine sind innerhalb ihrer Familie ununterscheidbar: zwei rote L-Steine, zwei gruene L-Steine, zwei vertikale Dominos und sechs Einzelfelder. Wuerde man diese Steine kuenstlich beschriften, dann erschiene dieselbe geometrische Stellung unter vielen bedeutungslosen Permutationen. Um dieses Ueberzaehlen zu vermeiden, wird jede wiederholte Familie als sortierte Ankerliste gespeichert.
Dadurch wird jede Familie zu einer Kombination statt zu einem geordneten Tupel. Auf dem \(5\times 6\)-Brett ergeben sich fuer die moeglichen Ankerzahlen
$$20,\ 20,\ 24,\ 30,\ 20,\ 25,$$
und zwar in dieser Reihenfolge fuer die roten L-Steine, die gruenden L-Steine, die vertikalen Dominos, die sechs Einzelfelder, das \(2\times 2\)-Quadrat und den horizontalen Domino. Fuer die wiederholten Familien entstehen daher die Kombinationszahlen
$$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6},$$
waehrend die beiden eindeutigen Steine die Faktoren \(20\) und \(25\) liefern. Somit passt ein kollisionsfreier kanonischer Zustand natuerlich in einen endlichen Mixed-Radix-Schluesselraum der Groesse
$$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$$
Die meisten dieser Schluessel repraesentieren keine legalen erreichbaren Stellungen, aber die Rechnung zeigt, dass eine kompakte exakte Kodierung moeglich ist.
Verwendet eine wiederholte Familie die sortierten Anker
$$0\le a_0<a_1<\cdots<a_{k-1},$$
dann ist ihr Kombinationsrang
$$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}.$$
Das ist die Standardformel des kombinatorischen Zahlensystems. Sie ordnet jeder \(k\)-Teilmenge von \(\{0,\dots,n-1\}\) eindeutig eine Zahl von \(0\) bis \(\binom{n}{k}-1\) zu. Verwendet man diesen Rang fuer jede wiederholte Familie und den einfachen Ankerindex fuer jede eindeutige Figur, dann laesst sich der komplette Zustand per Mixed-Radix-Komposition in eine einzige kollisionsfreie Ganzzahl packen.
Der wesentliche mathematische Punkt ist, dass Kanonisierung und Ranking die Erreichbarkeit nicht veraendern: Zwei Zustaende sind genau dann gleich, wenn jede Familie dieselbe Ankermenge belegt. Die Kodierung verliert also keine fuer das Puzzle relevante Information.
Ausgehend von \(s_0\) wird eine Breitensuche ueber den Zustandsgraphen ausgefuehrt. Wenn ein Zustand aus der Warteschlange entnommen wird, rekonstruiert der Algorithmus zuerst seine komplette Belegungsmaske und untersucht danach jeden Stein in jeder der vier Richtungen.
In einer festen Richtung wird der Stein jeweils um genau einen Ankerschritt weitergeschoben, bis der Brettrand erreicht ist oder eine Kollision droht. Jede gueltige Zwischenlage repraesentiert eine eigene legale Schiebedistanz und damit eine eigene ausgehende Kante im Graphen. Nach dem erneuten Kanonisieren der bewegten Familie wird der neue Zustand kodiert und nur dann in die Besuchsmenge eingefuegt, wenn er noch nicht bekannt ist.
Da jeder kanonische Zustand genau einmal verarbeitet wird, ist die gesuchte Anzahl einfach die Zahl der besuchten Schluessel:
$$A=\left|\mathcal{V}\right|.$$
Die Implementierung enthaelt ausserdem ein kleineres Kontrollpuzzle auf einem \(3\times 4\)-Brett mit einem L-Tromino und sieben Einzelfeldern. Dieses Brett besitzt \(12\) Zellen, davon sind \(10\) belegt, also gibt es wieder genau zwei Leerfelder.
In diesem kleineren Puzzle hat das L-Teil \(6\) moegliche Anker, waehrend die sieben Einzelfelder eine sortierte \(7\)-Teilmenge der \(12\) Brettzellen bilden. Vor der Legalitaetspruefung ergibt sich also die natuerliche Zustandszahl
$$6\binom{12}{7}=6\cdot 792=4752.$$
Ein perfekter Schluessel entsteht, indem man den Kombinationsrang der sieben Einzelfelder nimmt und den L-Anker als letzte Ziffer in Basis \(6\) anhaengt:
$$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$$
Fuehrt man dieselbe Erreichbarkeitssuche auf diesem reduzierten Puzzle aus, erhaelt man genau \(208\) Zustaende. Dieses Kontrollbeispiel ist nuetzlich, weil es die gesamte Methode auf einem kleinen Brett zeigt, waehrend dieselbe kanonische Kodierung und dieselbe Zugerzeugung wie im eigentlichen Puzzle benutzt werden.
Die Implementierungen in C++, Python und Java folgen alle demselben mathematischen Modell des Zustandsraums. Zunaechst wird eine kleine Tabelle von Binomialkoeffizienten fuer das kombinatorische Ranking vorberechnet. Ausserdem werden fuer jede zulaessige Ankerposition jeder Figurenfamilie sowohl die Belegungsmaske als auch der Nachbaranker berechnet, der durch einen Einzelschritt in eine der vier Richtungen entsteht.
Die C++- und Python-Implementierungen fuehren anschliessend die eigentliche Graphtraversierung aus. Fuer jeden besuchten Zustand bauen sie die globale Belegungsmaske einmal auf, entfernen den bewegten Stein temporaer und pruefen Kandidatenlagen mit einem konstant schnellen Maskenschnitt. Wiederholte Familien werden unmittelbar nach jedem Zug sortiert, in eine eindeutige Ganzzahl kodiert und nur dann in die Besuchsstruktur aufgenommen, wenn der Zustand neu ist.
Die Java-Implementierung benutzt dieselbe mathematische Strategie, delegiert die aufwendige Enumeration aber an den optimierten C++-Solver und gibt danach das geparste numerische Resultat zurueck. Damit stimmen alle drei Sprachpfade in Zustandsdefinition, Zugregel und exakter Endzaehlung ueberein.
Sei \(V=\left|\operatorname{Reach}(s_0)\right|\) die Anzahl der erreichbaren Zustaende und \(E\) die Anzahl der legalen gerichteten Zuege zwischen ihnen. Die Vorberechnung von Masken, Nachbarankern und kleinen Binomialwerten kostet bei dieser festen Puzzlegroesse nur \(O(1)\). Die Traversierung verarbeitet jeden entdeckten Zustand genau einmal und betrachtet jede legale ausgehende Bewegung genau einmal, also ist die gesamte Laufzeit
$$O(V+E).$$
Besuchsmenge und Warteschlange speichern hoechstens einen Datensatz pro erreichbarem Zustand, daher betraegt der Speicherbedarf
$$O(V).$$
Weil Brettgroesse und Figurenmultimenge fest sind, ist die Arbeit pro Zustand durch eine puzzlespezifische Konstante beschraenkt. Praktisch verhaelt sich das Programm deshalb nahezu linear in der Anzahl der erreichbaren Zustaende.
Bu problem, sabit bir kaydirmali blok bulmacasinda verilen baslangic duzeninden ulasilabilen farkli konumlarin sayisini sorar. Tahta \(5\times 6\) boyutundadir; yani toplam \(30\) hucre vardir. Baslangic yerlesiminde iki kirmizi L-tromino, aynalanmis yonelimli iki yesil L-tromino, iki dikey domino, alti tek kare, bir \(2\times 2\) kare ve bir yatay domino bulunur. Bu parcalar toplam \(28\) hucre kapladigi icin her gecerli durumda tam olarak iki bos hucre vardir.
Gecerli bir hamle, tek bir parcayi secip onu yatay veya dikey dogrultuda pozitif bir mesafe kadar kaydirmaktir. Parca donemez, tahta disina cikamaz ve baska bir parcayla cakisamaz. Gorev, baslangic konumundan ulasilabilen tum durumlari saymaktir; sadece en kisa hamle uzakligindaki durumlar sayilmaz. Durum uzayi buyuktur ama sonludur; dolayisiyla erisilebilir durum grafigi tam olarak cikarilabilir.
\(\mathcal{S}\), bu bulmaca icin tum gecerli tahta durumlarinin kumesi olsun; \(s_0\in\mathcal{S}\) ise verilen baslangic durumudur. Bir gecerli kaydirma, \(s\) durumunu \(t\) durumuna donusturuyorsa araya yonlu bir \(s\to t\) kenari koyariz. O halde aranan nicelik
$$A=\left|\operatorname{Reach}(s_0)\right|,$$
olur. Burada \(\operatorname{Reach}(s_0)\), \(s_0\)'dan sifir veya daha fazla gecerli hamle ile ulasilabilen tum durumlarin kumesidir.
Her parca ailesi icin bir capa hucre secilir ve bu capaya gore dolu hucre ofsetleri saklanir. \(F\) ailesinden bir parca \(a=(r,c)\) capasinda duruyorsa kapladigi hucreler
$$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j$$
seklindedir. Bir tahta durumu ancak ve ancak secilen tum maskeler ciftler halinde ayrik ise ve \(5\times 6\) dikdortgeninin icinde kaliyorsa gecerlidir. \(s\) durumundaki capa konumlari \(a_1,\dots,a_m\) olsun. Toplam doluluk kumesi
$$O(s)=\bigcup_{i=1}^{m} M_i(a_i)$$
olarak yazilir. Simdi \(i\) numarali parcayi \(a_i\) capasindan \(a_i'\) capasina tasimak isteyelim. Yeni yerlesim ancak
$$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing$$
ise carpismaz. Algoritmanin geometrik cekirdegi budur. Gercek kodda bu kume, tahtanin \(30\) hucresi uzerinde bir bitmask olarak tutulur; boylece test tek bir bit kesisimine iner.
Bazi parcalar kendi aileleri icinde ayirt edilmez: iki kirmizi L parcasi, iki yesil L parcasi, iki dikey domino ve alti tek kare. Bu parcalara yapay etiketler verseydik ayni geometrik durum, anlamsiz permutasyonlar yuzunden birden fazla kez sayilirdi. Bunu onlemek icin her tekrarli aile sirali bir capa listesi olarak saklanir.
Bu sayede her aile sirali bir dizi degil, bir kombinasyon haline gelir. \(5\times 6\) tahtada mumkun capa sayilari sirasiyla
$$20,\ 20,\ 24,\ 30,\ 20,\ 25$$
degerleridir; bunlar kirmizi L'ler, yesil L'ler, dikey dominolar, alti tek kare, \(2\times 2\) kare ve yatay domino icindir. Dolayisiyla tekrarli ailelerin kombinasyon sayilari
$$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6}$$
olur; tekil parcalar ise \(20\) ve \(25\) carpanlarini getirir. Bu nedenle carpismaz bir kanonik durum su buyuklukte sonlu bir mixed-radix anahtar uzayina tam olarak yerlestirilebilir:
$$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$$
Bu anahtarlarin cogu ne gecerli ne de erisilebilir bir duruma karsilik gelir; ancak bu hesap kompakt ve kayipsiz bir kodlamanin mumkun oldugunu gosterir.
Tekrarli bir aile sirali su capalari kullansin:
$$0\le a_0<a_1<\cdots<a_{k-1}.$$
Bu durumda kombinasyon rutu
$$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}$$
olur. Bu, kombinadik sistemin standart siralama formuluudur. \(\{0,\dots,n-1\}\) icindeki her \(k\)-altkumesine \(0\) ile \(\binom{n}{k}-1\) arasinda benzersiz bir tam sayi verir. Her tekrarli aile icin bu rutbe, tekil parçalar icin de dogrudan capa indeksi kullanildiginda tum durum mixed-radix bilesimi ile tek bir benzersiz tamsayi anahtara donusturulebilir.
Buradaki temel matematiksel nokta sudur: kanoniklestirme ve siralama erisilebilirligi bozmaz. Iki durum, ancak her aile ayni capa kumesini kullaniyorsa aynidir; dolayisiyla kodlama bulmaca icin gerekli hicbir bilgiyi kaybetmez.
\(s_0\)'dan baslayarak durum grafigi uzerinde bir BFS uygulanir. Kuyruktan cikarilan her durum icin once toplam doluluk maskesi yeniden kurulur; sonra her parca ve dort yon tek tek incelenir.
Secilen bir yonde parca, tahta sinirina gelene veya bir carpisma olusana kadar birer capa adimi ilerletilir. Ortaya cikan her ara gecerli yerlesim, farkli bir kaydirma mesafesine ve dolayisiyla grafikte farkli bir cikis kenarina karsilik gelir. Tasinan aile yeniden siralanir, elde edilen durum kodlanir ve daha once gorulmediyse visited yapisina eklenir.
Her kanonik durum yalnizca bir kez islendigi icin son cevap, ziyaret edilen anahtar sayisidir:
$$A=\left|\mathcal{V}\right|.$$
Uygulamada ayrica bir \(3\times 4\) kontrol bulmacasi da vardir. Bu kucuk tahtada bir L-tromino ve yedi tek kare bulunur. Toplam \(12\) hucrenin \(10\) tanesi dolu oldugu icin yine tam iki bosluk vardir.
Bu ornekte L parcasi icin \(6\) farkli capa vardir; yedi tek kare ise \(12\) tahta hucresinden secilen sirali bir \(7\)-altkume olusturur. Dolayisiyla gecerlilik kontrolunden once dogal durum sayisi
$$6\binom{12}{7}=6\cdot 792=4752$$
olur. Mukemmel bir anahtar, yedi tek karenin kombinasyon rutbesini alip L parcasinin capasini son basamak olarak radix-\(6\) icinde ekleyerek elde edilir:
$$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$$
Ayni erisilebilirlik taramasi bu kucuk bulmaca uzerinde calistirildiginda tam olarak \(208\) durum elde edilir. Bu kontrol noktasi, ayni kanonik kodlama ve ayni hamle uretimi mantiginin daha kucuk bir tahtada nasil calistigini gosterdigi icin cok faydalidir.
C++, Python ve Java uygulamalari ayni durum uzayi modelini kullanir. Ilk olarak kombinadik siralama icin kucuk bir binom katsayisi tablosu onceden hesaplanir. Ardindan her parca ailesinin her gecerli capa konumu icin hem dolu hucre maskesi hem de dort yonun her biri icin tek adimlik komsu capa bilgisi uretilir.
C++ ve Python uygulamalari asil grafigi dogrudan tarar. Her ziyaret edilen durumda toplam doluluk maskesi bir kez kurulur, hareket eden parca gecici olarak cikarilir ve aday konumlar sabit zamanli maske kesisimi ile test edilir. Tekrarli aileler her hamleden hemen sonra siralanir, benzersiz bir tamsayi anahtara paketlenir ve sadece yeni iseler visited yapisina eklenir.
Java uygulamasi da ayni matematiksel stratejiye dayanir; ancak agir sayimi optimize edilmis C++ cozumune devreder ve sayisal sonucu ayriştirip dondurur. Boylece uc dilde de ayni durum tanimi, ayni gecerli hamle kurali ve ayni kesin sonuc korunmus olur.
\(V=\left|\operatorname{Reach}(s_0)\right|\) erisilebilir durum sayisi, \(E\) ise aralarindaki gecerli yonlu hamle sayisi olsun. Maske, komsu capa ve kucuk binom degerlerinin onhesaplamasi bu sabit bulmaca icin \(O(1)\) maliyetlidir. Grafigin taranmasi her bulunan durumu tam bir kez isler ve her gecerli cikis hamlesine tam bir kez bakar; dolayisiyla toplam zaman
$$O(V+E)$$
olur. Kuyruk ve visited yapisi en fazla her erisilebilir durum icin bir kayit tuttugundan bellek kullanimi
$$O(V)$$
duzeyindedir. Tahta boyutu ve parca coklusu sabit oldugu icin durum basi is miktari bulmacaya ozgu bir sabitle sinirlidir; pratikte program, erisilebilir durum sayisina gore neredeyse dogrusal davranir.
El problema pide contar cuantas posiciones distintas son alcanzables en un rompecabezas deslizante fijo. El tablero mide \(5\times 6\), asi que tiene \(30\) celdas. La configuracion inicial contiene dos trominos rojos en forma de L, dos trominos verdes en L con la orientacion reflejada, dos dominós verticales, seis cuadrados unitarios, un cuadrado de \(2\times 2\) y un dominó horizontal. En total esas piezas ocupan \(28\) celdas, de modo que en toda posicion legal quedan exactamente dos celdas vacias.
Un movimiento legal elige una pieza y la desliza horizontal o verticalmente una distancia positiva. La pieza no puede girar, salir del tablero ni superponerse con otra. Hay que contar todas las posiciones alcanzables desde la disposicion inicial, no solo las que aparecen a distancia minima. El espacio de estados es grande, pero finito, asi que puede recorrerse exactamente el subgrafo alcanzable.
Sea \(\mathcal{S}\) el conjunto de todas las posiciones legales del tablero para este rompecabezas, y sea \(s_0\in\mathcal{S}\) la posicion inicial dada. Si un deslizamiento legal transforma \(s\) en \(t\), añadimos una arista dirigida \(s\to t\). Por tanto, la cantidad buscada es
$$A=\left|\operatorname{Reach}(s_0)\right|,$$
donde \(\operatorname{Reach}(s_0)\) denota el conjunto de estados alcanzables desde \(s_0\) mediante cero o mas movimientos legales.
Para cada familia de piezas se fija una celda ancla y se guarda la lista de offsets ocupados respecto de ella. Si una pieza de la familia \(F\) esta colocada en el ancla \(a=(r,c)\), entonces las celdas ocupadas son
$$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j.$$
Una posicion del tablero es legal exactamente cuando todas las mascaras elegidas son disjuntas dos a dos y permanecen dentro del rectangulo \(5\times 6\). Si el estado \(s\) tiene anclas \(a_1,\dots,a_m\), la ocupacion total es
$$O(s)=\bigcup_{i=1}^{m} M_i(a_i).$$
Si ahora la pieza \(i\) se mueve de \(a_i\) a un nuevo ancla \(a_i'\), esa colocacion es valida precisamente cuando
$$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing.$$
Ese es el nucleo geometrico del algoritmo. En la implementacion real, cada ocupacion se guarda como una mascara de bits sobre las \(30\) celdas del tablero, de modo que esta condicion se comprueba con una sola interseccion de bits.
Varias piezas son indistinguibles dentro de su propia familia: dos L rojas, dos L verdes, dos dominós verticales y seis cuadrados unitarios. Si se etiquetaran artificialmente, la misma posicion geometrica apareceria muchas veces por simples permutaciones. Para evitar ese sobreconteo, cada familia repetida se almacena como una lista ordenada de anclas.
Eso convierte cada familia en una combinacion, no en una tupla ordenada. En el tablero \(5\times 6\), los numeros de anclas posibles son
$$20,\ 20,\ 24,\ 30,\ 20,\ 25,$$
correspondientes, en ese orden, a las dos L rojas, las dos L verdes, los dos dominós verticales, los seis cuadrados unitarios, el cuadrado \(2\times 2\) y el dominó horizontal. Por tanto, las familias repetidas aportan los conteos combinatorios
$$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6},$$
mientras que las dos piezas unicas aportan los factores \(20\) y \(25\). Asi, un estado canonico sin colisiones cabe naturalmente en un espacio finito de claves de radix mixto de tamaño
$$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$$
La mayoria de esas claves no representan estados legales ni alcanzables, pero el calculo muestra que una codificacion compacta y exacta es posible.
Si una familia repetida usa anclas ordenadas
$$0\le a_0<a_1<\cdots<a_{k-1},$$
su rango combinatorio es
$$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}.$$
Esta es la formula estandar del sistema combinadico. Asigna a cada \(k\)-subconjunto de \(\{0,\dots,n-1\}\) un entero unico entre \(0\) y \(\binom{n}{k}-1\). Usando ese rango para cada familia repetida, y el indice ordinario del ancla para cada pieza unica, todo el estado puede empaquetarse en un solo entero sin colisiones mediante composicion de radix mixto.
El punto matematico importante es que la canonicalizacion y el ranking preservan completamente la nocion de estado. Dos posiciones son iguales si y solo si cada familia ocupa el mismo conjunto de anclas, de modo que la codificacion no pierde informacion relevante para la alcanzabilidad.
Desde \(s_0\) se realiza un recorrido en anchura del grafo de estados. Cuando se extrae un estado de la cola, el algoritmo reconstruye su mascara total de ocupacion y luego examina cada pieza en cada una de las cuatro direcciones.
En una direccion fija, la pieza avanza un paso de ancla cada vez hasta tocar el borde del tablero o producir una colision. Cada posicion intermedia valida corresponde a una distancia legal distinta de deslizamiento y, por tanto, a una arista saliente distinta. Despues de volver a canonicalizar la familia movida, el nuevo estado se codifica y se inserta en el conjunto de visitados solo si aun no habia aparecido.
Como cada estado canonico se procesa una sola vez, la respuesta final es simplemente el numero de claves visitadas:
$$A=\left|\mathcal{V}\right|.$$
La implementacion tambien incluye un rompecabezas mas pequeño de control sobre un tablero \(3\times 4\), con un tromino en L y siete cuadrados unitarios. Ese tablero tiene \(12\) celdas, de las cuales \(10\) estan ocupadas, asi que otra vez hay exactamente dos huecos.
En ese caso la pieza en L tiene \(6\) anclas posibles, mientras que los siete cuadrados unitarios forman un \(7\)-subconjunto ordenado de las \(12\) celdas. Antes de imponer legalidad, el numero natural de estados es
$$6\binom{12}{7}=6\cdot 792=4752.$$
Una clave perfecta se obtiene tomando el rango combinatorio de las siete anclas unitarias y añadiendo la ancla de la L como ultimo digito en base \(6\):
$$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$$
Al ejecutar el mismo recorrido de alcanzabilidad sobre ese rompecabezas reducido se obtienen exactamente \(208\) estados. Este ejemplo es util porque muestra todo el metodo en un tablero pequeño, pero reutiliza la misma codificacion canonica y la misma logica de generacion de movimientos que el problema principal.
Las implementaciones en C++, Python y Java siguen el mismo modelo matematico del espacio de estados. Primero precalculan una pequeña tabla de coeficientes binomiales para el ranking combinadico y, para cada ancla admisible de cada familia de piezas, la mascara de celdas ocupadas junto con el ancla vecina que se obtiene al mover un paso en cada una de las cuatro direcciones.
Las implementaciones en C++ y Python realizan despues el recorrido real del grafo. Para cada estado visitado construyen una vez la mascara global de ocupacion, retiran temporalmente la pieza que se mueve y comprueban las posiciones candidatas con una interseccion de mascaras en tiempo constante. Las familias repetidas se reordenan inmediatamente tras cada movimiento, se empaquetan en una clave entera unica y solo se insertan en la estructura de visitados si son nuevas.
La implementacion en Java usa la misma estrategia matematica, pero delega la enumeracion pesada al solucionador optimizado en C++ y devuelve el resultado numerico ya interpretado. Asi, las tres rutas de lenguaje comparten la misma definicion de estado, la misma regla de movimiento legal y la misma respuesta exacta.
Sea \(V=\left|\operatorname{Reach}(s_0)\right|\) el numero de estados alcanzables y \(E\) el numero de movimientos dirigidos legales entre ellos. El precalculo de mascaras, anclas vecinas y pequeños valores binomiales cuesta \(O(1)\) para este tamaño fijo del puzzle. El recorrido procesa cada estado descubierto una sola vez y examina cada movimiento saliente legal una sola vez, por lo que el tiempo total es
$$O(V+E).$$
El conjunto de visitados y la cola almacenan como maximo un registro por estado alcanzable, asi que la memoria total es
$$O(V).$$
Como las dimensiones del tablero y el multiconjunto de piezas son fijos, el trabajo por estado esta acotado por una constante propia del puzzle. En la practica, el programa se comporta casi linealmente con respecto al numero de estados alcanzables.
这道题要求计算一个固定滑块拼图从给定初始局面出发一共能到达多少个不同局面。棋盘大小是 \(5\times 6\)，因此共有 \(30\) 个格子。初始布局包含两个红色 L 形三格块、两个镜像方向的绿色 L 形三格块、两个竖直骨牌、六个单格小块、一个 \(2\times 2\) 方块以及一个水平骨牌。所有这些拼块总共占据 \(28\) 个格子，所以任何合法局面里都恰好有两个空格。
一次合法移动是选定一块拼块，将它沿水平或竖直方向滑动一个正整数距离。拼块不能旋转，不能越出边界，也不能与其他拼块重叠。题目要求统计从初始布局可以达到的全部状态，而不是只关心最短步数层上的状态。虽然状态空间很大，但它是有限的，因此可以把可达部分的状态图完整枚举出来。
设 \(\mathcal{S}\) 为这个拼图的全部合法棋盘状态集合，\(s_0\in\mathcal{S}\) 为题目给定的起始状态。如果一次合法滑动能把状态 \(s\) 变成状态 \(t\)，就在图中加入一条有向边 \(s\to t\)。因此最终要求的数量就是
$$A=\left|\operatorname{Reach}(s_0)\right|,$$
其中 \(\operatorname{Reach}(s_0)\) 表示从 \(s_0\) 出发经过零次或多次合法移动能够到达的所有状态。
对每一种拼块形状，先固定一个锚点格子，再记录该拼块相对于锚点所占据的偏移集合。如果某个家族 \(F\) 的一块拼块放在锚点 \(a=(r,c)\)，那么它占据的格子集合写成
$$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j.$$
一个棋盘状态合法，当且仅当所有被选中的掩码两两不相交，并且都位于 \(5\times 6\) 的棋盘范围内。若某个状态 \(s\) 中各块拼块的锚点为 \(a_1,\dots,a_m\)，则总占用集合为
$$O(s)=\bigcup_{i=1}^{m} M_i(a_i).$$
现在设第 \(i\) 块拼块要从 \(a_i\) 移到新的锚点 \(a_i'\)。新位置合法且不碰撞，当且仅当
$$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing.$$
这就是算法的几何核心。实际实现中，棋盘的 \(30\) 个格子被压成一个整数位掩码，因此上面的集合相交判定会退化成一次常数时间的按位与测试。
有些拼块在各自家族内部是不可区分的，例如两块红色 L 形块、两块绿色 L 形块、两块竖直骨牌，以及六个单格小块。如果给这些拼块强行加上标签，那么同一个几何局面会因为无意义的排列交换而被重复计数。为了避免这种过计数，所有重复家族都用排好序的锚点列表表示。
这样一来，这些家族不再是有序元组，而是组合。对 \(5\times 6\) 棋盘而言，不同家族可用的锚点数量依次是
$$20,\ 20,\ 24,\ 30,\ 20,\ 25,$$
分别对应两块红色 L 形块、两块绿色 L 形块、两块竖直骨牌、六个单格小块、一个 \(2\times 2\) 方块和一个水平骨牌。因此，重复家族对应的组合数是
$$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6},$$
而两个唯一拼块再额外贡献 \(20\) 和 \(25\) 这两个因子。于是，一个无碰撞的规范状态自然可以嵌入到如下大小的有限混合进位键空间中：
$$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$$
当然，这个键空间中的大多数编码既不是合法状态，也不是可达状态，但这个估计说明可以构造一个紧凑而且完全无冲突的精确编码。
如果某个重复家族使用的锚点已经排好序：
$$0\le a_0<a_1<\cdots<a_{k-1},$$
那么它的组合编号可以写成
$$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}.$$
这正是标准的 combinadic 编码公式。它把 \(\{0,\dots,n-1\}\) 的每一个 \(k\) 元子集唯一映射到区间 \(0\) 到 \(\binom{n}{k}-1\) 中的一个整数。对每个重复家族都取这样的组合编号，对唯一拼块则直接使用其锚点编号，然后按混合进位方式逐层打包，就能得到整个状态的唯一整数键。
这里最关键的数学事实是：规范化和编号都不会改变“状态相同”的含义。两个状态当且仅当每个家族占据了完全相同的锚点集合时才视为相同，因此这种编码不会丢失任何与可达性有关的信息。
从初始状态 \(s_0\) 出发，对状态图做广度优先遍历。每当从队列中取出一个状态，算法就先重建该状态的整体占用掩码，然后依次枚举每一块拼块和四个移动方向。
在固定方向上，拼块会沿着锚点图一次前进一步，直到碰到边界或即将发生碰撞为止。沿途每一个合法的中间锚点都对应一种合法滑动距离，因此也对应状态图中的一条不同出边。新状态产生后，先把被移动家族重新排序，再编码成唯一整数，如果此前没有访问过，就加入已访问集合和队列。
由于每个规范状态只会被处理一次，所以最后答案就是访问到的编码总数：
$$A=\left|\mathcal{V}\right|.$$
实现里还包含一个更小的 \(3\times 4\) 校验拼图，其中只有一个 L 形三格块和七个单格小块。这个小棋盘共有 \(12\) 个格子，其中 \(10\) 个被占据，因此同样始终有两个空格。
在这个小例子里，L 形块有 \(6\) 个可能锚点，七个单格块则构成 \(12\) 个格子中的一个有序 \(7\) 元子集。因此在尚未检查合法性的情况下，自然的状态上界是
$$6\binom{12}{7}=6\cdot 792=4752.$$
如果把七个单格块锚点的组合编号记为 \(\operatorname{rank}(S)\)，再把 L 形块的锚点 \(\ell\) 当作最后一位六进制数字附加上去，就得到一个完美无冲突的键：
$$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$$
对这个更小的拼图运行同样的可达性搜索，最终会得到恰好 \(208\) 个状态。这个例子很有价值，因为它在一个更容易人工理解的小棋盘上完整展示了同一套思想，而所使用的规范编码和移动生成逻辑与正式题目完全一致。
C++、Python 和 Java 三种实现都遵循同一个状态空间模型。它们首先预计算一个很小的二项式系数表，用于组合编号；同时，对每种拼块家族的每个合法锚点，预先算出该拼块对应的占用掩码，以及向四个方向各移动一步时能到达的相邻锚点。
C++ 和 Python 实现随后直接执行状态图遍历。对每个访问到的状态，它们只构造一次全局占用掩码，然后临时移除当前要移动的那块拼块，并用常数时间的掩码相交测试来判断候选位置是否可行。任何重复家族在移动后都会立刻重新排序，再被打包成唯一整数键，只有此前未出现过的状态才会进入访问结构。
Java 实现沿用同样的数学策略，但把真正的大规模枚举工作委托给优化过的 C++ 求解器，然后返回解析后的数值结果。因此三种语言路径在状态定义、合法移动规则和最终精确答案上是完全一致的。
记 \(V=\left|\operatorname{Reach}(s_0)\right|\) 为可达状态数，\(E\) 为这些状态之间合法有向移动的总数。由于棋盘大小和拼块集合都是固定的，掩码、相邻锚点以及小规模二项式表的预计算都只需要 \(O(1)\) 时间。真正的图遍历阶段中，每个状态只处理一次，每条合法出边也只检查一次，因此总时间复杂度为
$$O(V+E).$$
访问集合和队列最多各自存储每个可达状态的一份记录，所以空间复杂度为
$$O(V).$$
再因为棋盘尺寸和拼块多重集合固定，单个状态上的工作量被一个与题目实例有关的常数所控制。换句话说，对这个具体问题而言，程序的实际表现基本上可以视为对可达状态数的线性复杂度。
Здесь требуется посчитать количество различных позиций, достижимых в фиксированной головоломке со скользящими блоками из заданной стартовой конфигурации. Размер доски равен \(5\times 6\), то есть всего имеется \(30\) клеток. Начальная расстановка содержит два красных L-тромино, два зеленых L-тромино зеркальной ориентации, два вертикальных домино, шесть одиночных квадратов, один квадрат \(2\times 2\) и одно горизонтальное домино. Все эти фигуры вместе занимают \(28\) клеток, поэтому в любой допустимой позиции остаются ровно две пустые клетки.
Допустимый ход выбирает одну фигуру и сдвигает ее по горизонтали или вертикали на положительное число клеток. Поворачивать фигуру нельзя, выходить за границу доски нельзя, накладываться на другие фигуры тоже нельзя. Нужно посчитать все позиции, достижимые из начальной, а не только позиции на минимальном расстоянии по ходам. Пространство состояний велико, но конечно, поэтому достижимую часть графа можно перебрать точно.
Пусть \(\mathcal{S}\) обозначает множество всех допустимых позиций этой головоломки, а \(s_0\in\mathcal{S}\) - заданное начальное состояние. Если один допустимый сдвиг переводит состояние \(s\) в состояние \(t\), то мы добавляем ориентированное ребро \(s\to t\). Тогда искомая величина равна
$$A=\left|\operatorname{Reach}(s_0)\right|,$$
где \(\operatorname{Reach}(s_0)\) - множество всех состояний, достижимых из \(s_0\) за ноль или более допустимых ходов.
Для каждого семейства фигур фиксируется одна якорная клетка и список смещений занятых клеток относительно этого якоря. Если фигура семейства \(F\) стоит в якоре \(a=(r,c)\), то множество занятых ею клеток равно
$$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j.$$
Позиция доски допустима тогда и только тогда, когда все выбранные маски попарно не пересекаются и лежат внутри прямоугольника \(5\times 6\). Если в состоянии \(s\) фигуры имеют якори \(a_1,\dots,a_m\), то полная занятость равна
$$O(s)=\bigcup_{i=1}^{m} M_i(a_i).$$
Теперь предположим, что \(i\)-я фигура перемещается из \(a_i\) в новый якорь \(a_i'\). Новая позиция допустима тогда и только тогда, когда
$$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing.$$
Это и есть геометрическое ядро метода. В реализации каждое множество занятости хранится как битовая маска по \(30\) клеткам доски, поэтому проверка сводится к одной операции пересечения масок.
Некоторые фигуры неразличимы внутри своего семейства: две красные L-образные фигуры, две зеленые L-образные фигуры, два вертикальных домино и шесть одиночных квадратов. Если бы таким фигурам искусственно назначались метки, одна и та же геометрическая позиция появлялась бы много раз из-за бессмысленных перестановок. Чтобы избежать такого переучета, каждое повторяющееся семейство хранится как отсортированный список якорей.
Это превращает семейство из упорядоченного кортежа в комбинацию. На доске \(5\times 6\) количества возможных якорей равны
$$20,\ 20,\ 24,\ 30,\ 20,\ 25,$$
что соответствует двум красным L-фигурам, двум зеленым L-фигурам, двум вертикальным домино, шести одиночным квадратам, квадрату \(2\times 2\) и горизонтальному домино. Поэтому повторяющиеся семейства дают комбинационные числа
$$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6},$$
а две уникальные фигуры дают множители \(20\) и \(25\). Следовательно, любой бесколлизионный канонический статус естественно укладывается в конечное пространство смешанно-разрядных ключей размера
$$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$$
Большинство таких ключей не соответствуют ни допустимым, ни достижимым позициям, но этот подсчет показывает, что компактное точное кодирование возможно.
Если некоторое повторяющееся семейство использует отсортированные якори
$$0\le a_0<a_1<\cdots<a_{k-1},$$
то его комбинационный ранг задается формулой
$$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}.$$
Это стандартная формула комбинаторной системы нумерации. Она сопоставляет каждому \(k\)-подмножеству множества \(\{0,\dots,n-1\}\) уникальное число от \(0\) до \(\binom{n}{k}-1\). Используя такой ранг для каждого повторяющегося семейства и обычный индекс якоря для каждой уникальной фигуры, все состояние можно упаковать в одно целое число без коллизий с помощью смешанного основания.
Ключевой математический факт состоит в том, что канонизация и ранжирование не меняют смысл равенства состояний. Два состояния совпадают тогда и только тогда, когда каждое семейство занимает тот же самый набор якорей, поэтому кодирование не теряет никакой информации, важной для достижимости.
Начиная с \(s_0\), выполняется обход графа состояний в ширину. Когда состояние извлекается из очереди, алгоритм сначала восстанавливает его полную маску занятости, а затем рассматривает каждую фигуру и каждое из четырех направлений.
В фиксированном направлении фигура сдвигается по одному якорному шагу, пока не будет достигнута граница доски или не возникнет столкновение. Каждое промежуточное допустимое положение соответствует собственной допустимой длине скольжения и, следовательно, собственной исходящей дуге графа. После повторной канонизации перемещенного семейства новый статус кодируется и добавляется в множество посещенных только в том случае, если его там еще не было.
Поскольку каждое каноническое состояние обрабатывается ровно один раз, окончательный ответ равен просто числу посещенных ключей:
$$A=\left|\mathcal{V}\right|.$$
В реализации также есть более маленькая контрольная головоломка на доске \(3\times 4\), содержащая одну L-фигуру и семь одиночных квадратов. Такая доска имеет \(12\) клеток, из которых заняты \(10\), поэтому снова остаются ровно две пустые клетки.
В этом примере для L-фигуры существует \(6\) возможных якорей, а семь одиночных квадратов образуют отсортированное \(7\)-подмножество из \(12\) клеток. Поэтому естественная верхняя граница числа кодируемых состояний до проверки допустимости равна
$$6\binom{12}{7}=6\cdot 792=4752.$$
Совершенный ключ получается так: берется комбинационный ранг множества якорей одиночных квадратов, после чего якорь L-фигуры добавляется как последняя цифра по основанию \(6\):
$$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$$
Если выполнить тот же самый поиск достижимости на этой уменьшенной головоломке, получится ровно \(208\) состояний. Этот контрольный пример полезен тем, что на небольшой доске наглядно демонстрирует весь метод, сохраняя ту же каноническую кодировку и ту же логику генерации ходов, что и в основной задаче.
Реализации на C++, Python и Java используют одну и ту же математическую модель пространства состояний. Сначала они предварительно вычисляют небольшую таблицу биномиальных коэффициентов для combinadic-нумерации, а также для каждого допустимого якоря каждой семьи фигур строят маску занятых клеток и соседний якорь, получаемый одним шагом в каждом из четырех направлений.
Далее реализации на C++ и Python выполняют сам обход графа. Для каждого посещенного состояния они один раз собирают глобальную маску занятости, временно исключают движущуюся фигуру и проверяют кандидаты с помощью константного пересечения масок. Повторяющиеся семейства сразу после хода сортируются, упаковываются в уникальный целочисленный ключ и добавляются в структуру посещенных только тогда, когда состояние действительно новое.
Реализация на Java использует ту же математическую схему, но передает тяжелое перечисление оптимизированному решателю на C++ и возвращает уже разобранный числовой результат. Поэтому все три языковых пути совпадают по определению состояния, по правилу допустимого хода и по точному итоговому ответу.
Пусть \(V=\left|\operatorname{Reach}(s_0)\right|\) - число достижимых состояний, а \(E\) - число допустимых ориентированных ходов между ними. Предварительное вычисление масок, соседних якорей и небольшой биномиальной таблицы для этой фиксированной головоломки имеет стоимость \(O(1)\). Сам обход обрабатывает каждое найденное состояние ровно один раз и рассматривает каждый допустимый исходящий ход ровно один раз, так что полное время работы равно
$$O(V+E).$$
Множество посещенных и очередь хранят не более одной записи на каждое достижимое состояние, поэтому объем памяти равен
$$O(V).$$
Так как размеры доски и набор фигур фиксированы, работа на одно состояние ограничена константой, зависящей только от этой конкретной головоломки. На практике программа ведет себя почти линейно по числу достижимых состояний.
تطلب هذه المسألة حساب عدد الأوضاع المختلفة التي يمكن الوصول إليها في لغز انزلاق ثابت انطلاقا من وضع ابتدائي معلوم. اللوحة بحجم \(5\times 6\)، أي أنها تحتوي على \(30\) خلية. الترتيب الابتدائي يضم قطعتين حمراوين على شكل حرف L من ثلاث خلايا، وقطعتين خضراوين على الشكل نفسه لكن باتجاه مرآتي، وقطعتين دومينو عموديتين، وست قطع مفردة من خلية واحدة، ومربعا بحجم \(2\times 2\)، ودومينو أفقيا واحدا. هذه القطع تشغل معا \(28\) خلية، ولذلك يبقى في كل وضع قانوني خليتان فارغتان بالضبط.
الحركة القانونية تختار قطعة واحدة ثم تزلقها أفقيا أو عموديا مسافة موجبة. لا يسمح بتدوير القطعة، ولا بخروجها خارج اللوحة، ولا بتداخلها مع قطعة أخرى. المطلوب هو عد جميع الأوضاع التي يمكن الوصول إليها من الوضع الابتدائي، وليس فقط الأوضاع الواقعة على أقل عدد من الحركات. فضاء الحالات كبير، لكنه منته، ولذلك يمكن تعداد الجزء القابل للوصول من رسم الحالات بدقة تامة.
لتكن \(\mathcal{S}\) مجموعة جميع أوضاع اللوحة القانونية في هذا اللغز، وليكن \(s_0\in\mathcal{S}\) هو الوضع الابتدائي. إذا كانت حركة انزلاق قانونية تحول الحالة \(s\) إلى الحالة \(t\)، فإننا نضيف حافة موجهة \(s\to t\). وعندئذ تصبح الكمية المطلوبة هي
$$A=\left|\operatorname{Reach}(s_0)\right|,$$
حيث تمثل \(\operatorname{Reach}(s_0)\) مجموعة جميع الحالات التي يمكن الوصول إليها من \(s_0\) عبر صفر أو أكثر من الحركات القانونية.
لكل عائلة من القطع نثبت خلية مرساة، ثم نحفظ قائمة الإزاحات التي تحدد الخلايا المشغولة بالنسبة إلى هذه المرساة. فإذا وُضعت قطعة من العائلة \(F\) عند المرساة \(a=(r,c)\)، فإن الخلايا التي تشغلها هي
$$M_F(a)=\{(r+\Delta r_j,\ c+\Delta c_j)\}_j.$$
ويكون وضع اللوحة قانونيا إذا وفقط إذا كانت جميع الأقنعة المختارة متباينة زوجيا وتقع كلها داخل مستطيل \(5\times 6\). وإذا كانت مراسي القطع في الحالة \(s\) هي \(a_1,\dots,a_m\)، فإن مجموعة الإشغال الكلية تساوي
$$O(s)=\bigcup_{i=1}^{m} M_i(a_i).$$
والآن إذا أردنا نقل القطعة رقم \(i\) من المرساة \(a_i\) إلى المرساة الجديدة \(a_i'\)، فإن الوضع الجديد يكون خاليا من التصادم إذا وفقط إذا تحقق
$$M_i(a_i')\cap\left(O(s)\setminus M_i(a_i)\right)=\varnothing.$$
هذا هو القلب الهندسي للخوارزمية. وفي التطبيق الفعلي تُمثل مجموعة الإشغال بقناع بتات فوق خلايا اللوحة الثلاثين، ولذلك تتحول هذه الصيغة إلى اختبار تقاطع بتّي واحد بزمن ثابت.
بعض القطع غير مميزة داخل عائلتها: هناك قطعتان حمراوان على شكل L، وقطعتان خضراوان على شكل L، وقطعتان دومينو عموديتان، وست قطع مفردة. ولو أعطينا هذه القطع أسماء مصطنعة، لظهر الوضع الهندسي نفسه مرات كثيرة بسبب تبديلات لا معنى لها. لتجنب هذا التكرار، تمثل كل عائلة مكررة بقائمة مراسٍ مرتبة ترتيبا تصاعديا.
بهذا يتحول تمثيل العائلة من ترتيب مرتب إلى تركيب توافقي. وعلى لوحة \(5\times 6\)، تكون أعداد المراسي الممكنة على الترتيب
$$20,\ 20,\ 24,\ 30,\ 20,\ 25,$$
وهي خاصة بالقطعتين الحمراوين على شكل L، والقطعتين الخضراوين على شكل L، والدومينوين العموديين، والقطع الست المفردة، والمربع \(2\times 2\)، والدومينو الأفقي. ولذلك تسهم العائلات المكررة بعوامل التوافيق
$$\binom{20}{2},\qquad \binom{20}{2},\qquad \binom{24}{2},\qquad \binom{30}{6},$$
في حين تسهم القطعتان الوحيدتان بالعاملين \(20\) و\(25\). ومن ثم فإن كل حالة قانونية موحدة يمكن وضعها داخل فضاء مفاتيح منته ذي أساسات مختلطة حجمه
$$\binom{20}{2}\binom{20}{2}\binom{24}{2}\binom{30}{6}\cdot 20\cdot 25.$$
معظم هذه المفاتيح لا تمثل حالات قانونية قابلة للوصول، ولكن هذا الحساب يبين أن الترميز المضغوط والدقيق ممكن تماما.
إذا كانت عائلة مكررة تستعمل مراسي مرتبة كما يلي
$$0\le a_0<a_1<\cdots<a_{k-1},$$
فإن رتبتها التوافقية تعطى بالصيغة
$$\operatorname{rank}(a_0,\dots,a_{k-1})=\sum_{i=0}^{k-1}\binom{a_i}{i+1}.$$
هذه هي الصيغة القياسية للنظام التوافقي combinadic. فهي تعطي لكل \(k\)-مجموعة جزئية من \(\{0,\dots,n-1\}\) عددا صحيحا وحيدا بين \(0\) و\(\binom{n}{k}-1\). وعندما نستخدم هذه الرتبة لكل عائلة مكررة، ونستخدم فهرس المرساة العادي لكل قطعة وحيدة، يمكننا ضغط الحالة كلها في عدد صحيح واحد بلا أي تصادم باستعمال تركيب ذي أساسات مختلطة.
النقطة الرياضية الجوهرية هنا هي أن التوحيد والترتيب لا يغيران معنى الحالة. فحالتان متطابقتان إذا وفقط إذا احتلت كل عائلة مجموعة المراسي نفسها، لذلك لا يضيع أي قدر من المعلومات ذات الصلة بقابلية الوصول.
انطلاقا من \(s_0\) ننفذ اجتيازا بعرض الرسم البياني للحالات. وعند سحب حالة من الطابور، تعيد الخوارزمية بناء قناع الإشغال الكلي لها، ثم تفحص كل قطعة وكل اتجاه من الاتجاهات الأربعة.
وفي اتجاه ثابت، تدفع القطعة خطوة مرساة واحدة في كل مرة حتى تصل إلى حد اللوحة أو يصبح التصادم وشيكا. وكل موضع وسيط قانوني يمثل مسافة انزلاق قانونية مختلفة، وبالتالي يمثل حافة صادرة مختلفة في الرسم. وبعد إعادة توحيد العائلة التي تحركت، ترمز الحالة الجديدة وتضاف إلى مجموعة الزيارات فقط إذا لم تكن قد ظهرت من قبل.
وبما أن كل حالة موحدة تعالج مرة واحدة فقط، فإن الجواب النهائي ليس إلا عدد المفاتيح التي زارها الاجتياز:
$$A=\left|\mathcal{V}\right|.$$
يتضمن التطبيق أيضا لغزا أصغر للتحقق على لوحة \(3\times 4\)، وفيه قطعة واحدة على شكل L وسبع قطع مفردة. هذه اللوحة تحتوي على \(12\) خلية، منها \(10\) مشغولة، ولذلك يبقى فيها أيضا فراغان فقط.
في هذا المثال الصغير، توجد \(6\) مراسٍ ممكنة لقطعة L، بينما تشكل القطع المفردة السبع مجموعة مرتبة من \(7\) خلايا مختارة من أصل \(12\) خلية. لذلك يكون الحد الطبيعي لعدد الحالات قبل فحص القانونية هو
$$6\binom{12}{7}=6\cdot 792=4752.$$
ويمكن الحصول على مفتاح كامل الدقة بأخذ الرتبة التوافقية لمجموعة مراسي القطع المفردة ثم إلحاق مرساة قطعة L باعتبارها الخانة الأخيرة في أساس \(6\):
$$K_{\text{sample}}=6\,\operatorname{rank}(S)+\ell.$$
وعند تشغيل اجتياز الوصول نفسه على هذا اللغز المصغر نحصل على \(208\) حالة بالضبط. وهذا المثال مهم لأنه يعرض الفكرة كاملة على لوحة يسهل تصورها، مع الاحتفاظ بالترميز الموحد نفسه ومنطق توليد الحركات نفسه المستخدمين في اللغز الكامل.
تتبع تطبيقات ++C وPython وJava النموذج الرياضي نفسه لفضاء الحالات. فهي تبدأ ببناء جدول صغير للمعاملات الثنائية من أجل ترميز combinadic، كما تسبق فتحسب لكل مرساة ممكنة في كل عائلة من القطع قناع الخلايا المشغولة والمرساة المجاورة الناتجة عن خطوة واحدة في كل اتجاه من الاتجاهات الأربعة.
بعد ذلك تنفذ نسختا ++C وPython اجتياز الرسم فعليا. ففي كل حالة مزارة، تبنيان قناع الإشغال العام مرة واحدة، ثم تزيلان القطعة المتحركة مؤقتا، وتفحصان المواضع المرشحة باختبار تقاطع أقنعة بزمن ثابت. والعائلات المكررة يعاد ترتيبها مباشرة بعد كل حركة، ثم تضغط في مفتاح صحيح وحيد، ولا تدخل بنية الزيارات إلا إذا كانت الحالة جديدة فعلا.
أما نسخة Java فتستخدم الاستراتيجية الرياضية نفسها، لكنها تفوض عملية التعداد الثقيلة إلى الحل ++C المحسن ثم تعيد النتيجة الرقمية بعد تحليلها. ولهذا تتفق المسارات الثلاثة في تعريف الحالة، وفي قاعدة الحركة القانونية، وفي الجواب الدقيق النهائي.
إذا رمزنا إلى عدد الحالات القابلة للوصول بالرمز \(V=\left|\operatorname{Reach}(s_0)\right|\)، وإلى عدد الحركات القانونية الموجهة بينها بالرمز \(E\)، فإن الحسابات المسبقة للأقنعة والمراسي المجاورة وقيم ثنائية الحد الصغيرة تكلف \(O(1)\) في هذا اللغز ذي الحجم الثابت. وأثناء الاجتياز تعالج كل حالة مكتشفة مرة واحدة، ويفحص كل انتقال قانوني صادر مرة واحدة، ولذلك يكون الزمن الكلي
$$O(V+E).$$
أما مجموعة الزيارات والطابور فلا يخزنان أكثر من سجل واحد لكل حالة قابلة للوصول، ولذلك يكون استهلاك الذاكرة
$$O(V).$$
ولأن أبعاد اللوحة وتعدد القطع ثابتة، فإن العمل المطلوب لكل حالة محكوم بثابت خاص بهذه المسألة. ومن هذه الزاوية يكون سلوك البرنامج عمليا شبه خطي في عدد الحالات القابلة للوصول.