Let \(F(n)\) denote the number of valid migrations on an \(n \times n\) grid. Every cell initially contains one ant, every ant must move to a neighboring cell, every cell must receive exactly one ant, and two ants are not allowed to traverse the same undirected edge in opposite directions. In graph terms, each vertex has out-degree \(1\) and in-degree \(1\), so a valid migration is a disjoint union of directed cycles, with 2-cycles forbidden.
Color the grid as a checkerboard, with black and white cells. Every legal move goes from one color to the other, because adjacent cells always have opposite parity. Split the directed edges of a migration into two sets:
$$M_1=\{\text{moves from black to white}\},\qquad M_2=\{\text{moves from white to black}\}.$$
Now inspect \(M_1\). Every black vertex has exactly one outgoing move, so every black cell is incident to exactly one edge of \(M_1\). Every white vertex has exactly one incoming move, and the only possible source is a black neighbor, so every white cell is also incident to exactly one edge of \(M_1\). Therefore \(M_1\) is a perfect matching of the bipartite grid graph. By the same argument, \(M_2\) is another perfect matching.
The forbidden “swap positions across one edge” condition says that the two matchings may not use the same undirected edge. Hence valid migrations are in bijection with ordered pairs \((M_1,M_2)\) of edge-disjoint perfect matchings. This is the central reformulation used by all three solution files.
If \(n\) is odd, the checkerboard coloring contains different numbers of black and white cells, namely
$$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$$
A perfect matching in a bipartite graph requires both color classes to have equal size, so for odd \(n\) no perfect matching exists at all. Therefore
$$F(n)=0\qquad\text{for odd }n.$$
This matches the checkpoint logic in the C++ program, where the brute-force verification for \(n=3\) agrees with the DP result \(F(3)=0\).
The implementations process the board row by row. For one matching layer, consider a fixed row \(r\). Some cells in that row may already be matched vertically to row \(r-1\); the code records those columns by a bitmask \(in\). If bit \(c\) is set, then cell \((r,c)\) is already occupied in that matching layer and needs no new decision inside the current row.
For Problem 393 we must track two matching layers simultaneously, so the state is a pair \((in_1,in_2)\). The code packs it into one integer:
$$state = in_1 + (in_2 \ll n).$$
Here \(in_1\) belongs to the black-to-white matching and \(in_2\) to the white-to-black matching. At the end of the row we obtain two new masks \((out_1,out_2)\), representing vertical edges that continue downward into row \(r+1\).
Inside one matching layer, an unoccupied cell has only two possible ways to be matched while scanning left to right:
$$\text{horizontal to }(r,c+1)\qquad\text{or}\qquad \text{vertical to }(r+1,c).$$
If the cell is already covered by an incoming vertical edge from above, the only option is “filled”. On the last row, vertical placement is impossible because there is no row below.
This is exactly what the helper options_for_cell returns in C++, Python, and Java: Filled, Horizontal, or Vertical, together with the bit updates needed for the current occupancy mask and for the outgoing mask.
Within one matching layer, the occupancy mask already guarantees that each cell is used exactly once. Across the two layers, the only forbidden situation is reusing the same undirected edge, because that would mean the two directed matchings traverse it in opposite directions. For the current column \(c\), that can happen in exactly two ways:
$$\text{both layers choose the same horizontal edge }(r,c)\text{--}(r,c+1),$$
$$\text{both layers choose the same vertical edge }(r,c)\text{--}(r+1,c).$$
That is why the DFS rejects only the pairs (Horizontal, Horizontal) and (Vertical, Vertical) at the same column. No other cross-layer test is necessary.
For fixed input masks \((in_1,in_2)\) and a flag telling us whether we are on the last row, the depth-first search enumerates every legal filling of that row and counts how many of them lead to each output pair \((out_1,out_2)\). Let
$$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2))$$
be that multiplicity. Then the row DP is
$$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2)).$$
The initial condition is
$$\mathrm{DP}_0(0,0)=1,$$
because before the first row there are no pending vertical edges. The final answer is
$$F(n)=\mathrm{DP}_n(0,0),$$
because after the last row there must again be no unfinished vertical edges.
The \(2 \times 2\) grid has exactly two perfect matchings: the two horizontal edges, or the two vertical edges. Since the two layers must be edge-disjoint, one layer must choose the horizontal matching and the other must choose the vertical matching. The pair is ordered, so we get two possibilities:
$$F(2)=2.$$
These are precisely the clockwise and counterclockwise 4-cycles around the square, and they match the checkpoint f(2)=2 in the repository code.
The C++ solution keeps dp as unordered_map<int, BigInt>, where the key is the packed profile state and the value is the number of ways to reach it. The cache transition_cache_ stores the previously computed transition list for a triple \((in_1,in_2,last\_row)\). The Python version uses ordinary dictionaries and Python's arbitrary-precision integers, while the Java version mirrors the same structure with HashMap, explicit Transition objects, and BigInteger.
The C++ file also contains internal validation: it checks \(F(2)=2\), \(F(4)=88\), and compares the DP against brute force for \(n=3\). For the actual Project Euler input \(n=10\), the implementations return
$$112398351350823112.$$
The profile space is a subset
$$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n,$$
so there are at most \(2^{2n}\) combined masks. Building one uncached transition map is itself exponential in \(n\), because the DFS explores all legal row fillings for the two coupled matching layers. However, each profile \((in_1,in_2,last\_row)\) is solved only once and then reused whenever it reappears in the outer DP. Thus the algorithm is exponential in the board width, but only linear in the number of rows after transition reuse. Memory usage is also exponential in \(n\), dominated by the DP frontier and the cached transition tables. That is still practical for \(n=10\), while direct enumeration over all neighbor choices would be completely infeasible.
solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java.Sei \(F(n)\) die Anzahl gültiger Wanderungen auf einem \(n \times n\)-Gitter. Jede Zelle enthält anfangs genau eine Ameise, jede Ameise muss in eine benachbarte Zelle ziehen, jede Zelle muss genau eine Ameise empfangen, und dieselbe ungerichtete Kante darf nicht gleichzeitig in beide Richtungen benutzt werden. Graphentheoretisch hat also jeder Knoten Ausgrad \(1\) und Eingrad \(1\); die Konfiguration zerfällt in disjunkte gerichtete Zyklen, wobei 2-Zyklen verboten sind.
Färbt man das Gitter schachbrettartig schwarz-weiß, dann verbindet jede zulässige Bewegung stets zwei verschiedenfarbige Zellen. Zerlege die gerichteten Kanten in
$$M_1=\{\text{Züge von schwarz nach weiß}\},\qquad M_2=\{\text{Züge von weiß nach schwarz}\}.$$
In \(M_1\) besitzt jede schwarze Zelle genau eine ausgehende Kante, und jede weiße Zelle genau eine eingehende Kante von einem schwarzen Nachbarn. Also ist \(M_1\) ein perfektes Matching des bipartiten Gittergraphen. Dasselbe gilt symmetrisch für \(M_2\).
Die verbotene Situation „zwei Ameisen tauschen über dieselbe Kante ihre Plätze“ bedeutet genau, dass \(M_1\) und \(M_2\) keine ungerichtete Kante gemeinsam benutzen dürfen. Gültige Wanderungen stehen daher in Bijektion zu geordneten Paaren \((M_1,M_2)\) von kanten-disjunkten perfekten Matchings. Genau diese Sichtweise implementieren die lokalen Lösungsdateien.
Für ungerades \(n\) enthält die Schachbrettfärbung unterschiedlich viele schwarze und weiße Felder, nämlich
$$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$$
Ein perfektes Matching in einem bipartiten Graphen ist dann unmöglich. Also gilt
$$F(n)=0\qquad\text{für ungerades }n.$$
Das passt zur Validierung im C++-Programm: Für \(n=3\) stimmt das Profil-DP mit der Brute-Force-Prüfung überein und liefert \(F(3)=0\).
Die Programme verarbeiten das Gitter zeilenweise. Für eine Matching-Ebene beschreibt eine Bitmaske \(in\), welche Spalten der aktuellen Zeile bereits durch eine vertikale Kante aus der Vorzeile belegt sind. Ist Bit \(c\) gesetzt, so ist die Zelle \((r,c)\) in dieser Ebene schon versorgt und braucht innerhalb der aktuellen Zeile keine neue Entscheidung.
Da Problem 393 zwei Matching-Ebenen gleichzeitig verfolgt, besteht der Zustand aus \((in_1,in_2)\). Im Code wird daraus ein Integer gepackt:
$$state = in_1 + (in_2 \ll n).$$
Am Ende der Zeile entstehen neue Masken \((out_1,out_2)\), die vertikale Kanten zur nächsten Zeile \(r+1\) markieren.
Innerhalb einer Matching-Ebene hat eine noch unbelegte Zelle beim Links-nach-rechts-Scan nur zwei mögliche Partner:
$$\text{horizontal zu }(r,c+1)\qquad\text{oder}\qquad \text{vertikal zu }(r+1,c).$$
Ist die Zelle bereits durch eine eingehende vertikale Kante von oben belegt, bleibt nur die Option „filled“. In der letzten Zeile ist eine vertikale Fortsetzung nach unten nicht mehr erlaubt.
Genau das kapselt die Hilfsfunktion options_for_cell in C++, Python und Java: Filled, Horizontal oder Vertical, zusammen mit den Bitänderungen für die aktuelle Belegungsmaske und die ausgehende Maske.
Innerhalb einer Matching-Ebene erzwingt die Belegungsmaske bereits, dass jede Zelle genau einmal benutzt wird. Zwischen den beiden Ebenen ist nur das Wiederverwenden derselben ungerichteten Kante verboten, weil dies den verbotenen Gegenverkehr entlang derselben Kante erzeugen würde. Für die aktuelle Spalte \(c\) kann das nur in zwei Fällen passieren:
$$\text{beide Ebenen wählen dieselbe horizontale Kante }(r,c)\text{--}(r,c+1),$$
$$\text{beide Ebenen wählen dieselbe vertikale Kante }(r,c)\text{--}(r+1,c).$$
Darum verwirft die DFS im Code genau die Paare (Horizontal, Horizontal) und (Vertical, Vertical) an derselben Spalte. Weitere Kreuztests sind nicht nötig.
Für feste Eingangsmasken \((in_1,in_2)\) und ein Flag, ob wir uns in der letzten Zeile befinden, zählt die Tiefensuche alle legalen Füllungen dieser Zeile und sammelt, mit welcher Multiplizität jede Ausgangsmaske \((out_1,out_2)\) entsteht. Bezeichne diese Zahl mit
$$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2)).$$
Dann lautet die DP-Rekurrenz
$$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2)).$$
Der Startzustand ist
$$\mathrm{DP}_0(0,0)=1,$$
denn vor der ersten Zeile existieren keine offenen vertikalen Kanten. Gesucht ist
$$F(n)=\mathrm{DP}_n(0,0),$$
weil nach der letzten Zeile ebenfalls keine offenen Verbindungen übrig bleiben dürfen.
Das \(2 \times 2\)-Gitter besitzt genau zwei perfekte Matchings: entweder die beiden horizontalen Kanten oder die beiden vertikalen. Da die beiden Ebenen kanten-disjunkt sein müssen, wählt eine Ebene das horizontale und die andere das vertikale Matching. Weil das Paar geordnet ist, entstehen zwei Möglichkeiten:
$$F(2)=2.$$
Das sind genau die beiden gerichteten 4-Zyklen im Uhrzeigersinn bzw. gegen den Uhrzeigersinn, passend zum Checkpoint f(2)=2 im Repository.
Die C++-Lösung speichert dp als unordered_map<int, BigInt>; der Schlüssel ist der gepackte Profilzustand, der Wert die Zahl der Wege dorthin. In transition_cache_ liegen die bereits berechneten Übergangslisten für Tripel \((in_1,in_2,last\_row)\). Die Python-Version verwendet gewöhnliche Dictionaries und eingebaute Ganzzahlen mit beliebiger Präzision, während Java dieselbe Struktur mit HashMap, expliziten Transition-Objekten und BigInteger nachbildet.
Zusätzlich enthält die C++-Datei interne Tests: \(F(2)=2\), \(F(4)=88\) und ein Vergleich mit Brute Force für \(n=3\). Für den eigentlichen Euler-Wert \(n=10\) liefern die Implementierungen
$$112398351350823112.$$
Der Profilraum ist eine Teilmenge von
$$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n,$$
also gibt es höchstens \(2^{2n}\) kombinierte Masken. Das Erzeugen einer noch nicht gecachten Übergangstabelle ist selbst exponentiell in \(n\), weil die DFS alle legalen Zeilenfüllungen der beiden gekoppelten Matching-Ebenen durchsucht. Jede Konfiguration \((in_1,in_2,last\_row)\) wird jedoch nur einmal gelöst und anschließend wiederverwendet. Damit ist das Verfahren exponentiell in der Gitterbreite, aber nach dem Caching nur linear in der Zeilenzahl. Der Speicherbedarf ist ebenfalls exponentiell in \(n\) und wird von der DP-Frontier sowie den Übergangscaches dominiert. Für \(n=10\) ist das noch praktikabel; eine naive Enumeration aller Nachbarentscheidungen wäre astronomisch groß.
solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java.\(F(n)\), \(n \times n\) ızgaradaki geçerli göç düzenlerinin sayısı olsun. Her hücre başlangıçta bir karınca içerir; her karınca komşu bir hücreye gitmek zorundadır; her hücre tam olarak bir karınca almalıdır; ayrıca aynı yönsüz kenar iki karınca tarafından ters yönlerde aynı anda kullanılamaz. Grafik kuramı diliyle her düğümün çıkış derecesi \(1\), giriş derecesi \(1\) olur; dolayısıyla yapı, 2-çevrimler hariç, ayrık yönlü çevrimlerin birleşimidir.
Izgarayı dama tahtası gibi siyah-beyaz boyayalım. Komşu hücreler zıt renkte olduğundan, her hareket bir renkten diğerine geçer. Yönlü kenarları iki kümeye ayıralım:
$$M_1=\{\text{siyahdan beyaza giden hareketler}\},\qquad M_2=\{\text{beyazdan siyaha giden hareketler}\}.$$
\(M_1\)'de her siyah hücrenin tam bir çıkışı vardır; her beyaz hücre de tam bir giriş alır ve bu giriş yalnızca siyah bir komşudan gelebilir. Bu yüzden \(M_1\), iki parçalı ızgara grafının bir perfect matching'idir. Aynı argümanla \(M_2\) de bir perfect matching olur.
Yasak olan “iki karıncanın aynı kenar üzerinden yer değiştirmesi” durumu, \(M_1\) ile \(M_2\)'nin aynı yönsüz kenarı paylaşmaması gerektiği anlamına gelir. Dolayısıyla geçerli göçler ile kenar-ayrık sıralı perfect matching çiftleri \((M_1,M_2)\) arasında bire bir eşleme vardır. Üç çözüm dosyasının dayandığı ana fikir budur.
\(n\) tek ise dama boyamasında siyah ve beyaz hücre sayıları farklı olur:
$$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$$
İki parçalı bir grafikte perfect matching olabilmesi için iki parçanın boyutu eşit olmalıdır. O halde
$$F(n)=0\qquad\text{tek }n\text{ için.}$$
Bu, C++ kodundaki doğrulamayla uyumludur: \(n=3\) için brute force ile DP aynı sonucu verir ve \(F(3)=0\) bulunur.
Programlar tahtayı satır satır işler. Tek bir matching katmanı için, o anki satırın bazı hücreleri bir üst satırdan gelen dikey kenarla zaten eşleşmiş olabilir. Kod, bu sütunları bir \(in\) bit maskesiyle tutar. Bit \(c\) açıksa \((r,c)\) hücresi o katmanda zaten doludur ve bu satır içinde yeni karar gerektirmez.
Problem 393'te iki katman birden izlendiği için durum \((in_1,in_2)\) çiftidir. Kod bunu tek bir tamsayıda paketler:
$$state = in_1 + (in_2 \ll n).$$
Satır tamamlandığında \((out_1,out_2)\) maskeleri oluşur; bunlar bir alt satıra devam eden dikey kenarları gösterir.
Tek bir matching katmanında, soldan sağa tararken henüz kullanılmamış bir hücrenin yalnızca iki eşleşme seçeneği vardır:
$$\text{yatay olarak }(r,c+1)\text{ ile}\qquad\text{veya}\qquad \text{dikey olarak }(r+1,c)\text{ ile.}$$
Eğer hücre yukarıdan gelen bir dikey kenarla zaten kaplandıysa tek seçenek “filled” olur. Son satırda aşağı doğru dikey seçim yapılamaz.
C++, Python ve Java içindeki options_for_cell yardımcı fonksiyonu tam olarak bunu döndürür: Filled, Horizontal veya Vertical; ayrıca mevcut doluluk maskesine ve çıkış maskesine hangi bitlerin ekleneceğini de verir.
Bir katmanın kendi içinde her hücrenin yalnızca bir kez kullanılmasını doluluk maskesi zaten garanti eder. İki katman arasında yasak olan tek şey aynı yönsüz kenarın yeniden kullanılmasıdır; çünkü bu, aynı kenar üzerinde ters yönlü geçiş demektir. Bu durum sütun \(c\) için yalnızca iki şekilde ortaya çıkar:
$$\text{iki katman da aynı yatay kenarı }(r,c)\text{--}(r,c+1)\text{ seçerse},$$
$$\text{iki katman da aynı dikey kenarı }(r,c)\text{--}(r+1,c)\text{ seçerse}.$$
Bu yüzden DFS yalnızca aynı sütundaki (Horizontal, Horizontal) ve (Vertical, Vertical) çiftlerini reddeder. Başka bir katmanlar arası test gerekmez.
Sabit giriş maskeleri \((in_1,in_2)\) ve “son satır mı?” bilgisi verildiğinde, derinlik öncelikli arama o satırı doldurmanın tüm geçerli yollarını sayar ve her \((out_1,out_2)\) çıkış çifti için çokluğu toplar. Bu sayıya
$$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2))$$
diyelim. O zaman satır DP bağıntısı
$$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2))$$
şeklindedir. Başlangıç koşulu
$$\mathrm{DP}_0(0,0)=1$$
olur; çünkü ilk satırdan önce bekleyen dikey kenar yoktur. Sonuç ise
$$F(n)=\mathrm{DP}_n(0,0)$$
olmalıdır; çünkü son satırdan sonra da açık dikey bağlantı kalamaz.
\(2 \times 2\) ızgaranın yalnızca iki perfect matching'i vardır: iki yatay kenar ya da iki dikey kenar. Katmanlar kenar-ayrık olmak zorunda olduğundan, biri yatay matching'i, diğeri dikey matching'i seçer. Çift sıralı olduğundan iki olasılık vardır:
$$F(2)=2.$$
Bunlar kare etrafındaki saat yönü ve saat yönünün tersi 4-çevrimlerdir; depodaki f(2)=2 kontrolüyle tam uyuşur.
C++ çözümü dp yapısını unordered_map<int, BigInt> olarak tutar; anahtar paketlenmiş profil durumudur, değer ise o duruma ulaşan yol sayısıdır. transition_cache_ içinde \((in_1,in_2,last\_row)\) üçlüsü için daha önce hesaplanmış geçiş listeleri saklanır. Python sürümü normal sözlükler ve sınırsız büyüklükte tamsayılar kullanır. Java sürümü aynı fikri HashMap, açık Transition nesneleri ve BigInteger ile tekrarlar.
C++ dosyasında ek doğrulamalar da vardır: \(F(2)=2\), \(F(4)=88\) ve \(n=3\) için brute force karşılaştırması. Gerçek Project Euler girdisi olan \(n=10\) için tüm uygulamalar
$$112398351350823112$$
sonucunu üretir.
Profil uzayı
$$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n$$
şeklinde olduğundan en fazla \(2^{2n}\) birleşik maske vardır. Önbellekte olmayan tek bir geçiş haritasını üretmek bile \(n\)'e göre üstel maliyetlidir; çünkü DFS, birbirine bağlı iki matching katmanının satır üzerindeki tüm geçerli doldurmalarını dolaşır. Ancak her \((in_1,in_2,last\_row)\) profili yalnızca bir kez çözülür ve daha sonra tekrar kullanılır. Böylece algoritma tahta genişliğinde üstel, satır sayısında ise geçişler üretildikten sonra doğrusaldır. Bellek kullanımı da DP sınırı ve geçiş önbelleği nedeniyle üstel davranır. Buna rağmen \(n=10\) için uygulanabilirdir; her karıncanın tüm komşu seçimlerini doğrudan denemek ise pratikte imkansız olurdu.
solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java.Sea \(F(n)\) el número de migraciones válidas en una cuadrícula \(n \times n\). Cada celda contiene inicialmente una hormiga, cada hormiga debe moverse a una celda vecina, cada celda debe recibir exactamente una hormiga y no se permite que dos hormigas usen la misma arista no dirigida en sentidos opuestos. En términos de grafos, cada vértice tiene grado de salida \(1\) y grado de entrada \(1\), así que una migración válida es una unión disjunta de ciclos dirigidos, con los ciclos de longitud \(2\) prohibidos.
Coloreemos la cuadrícula como un tablero de ajedrez. Toda arista de la cuadrícula conecta colores opuestos, así que cada movimiento va de negro a blanco o de blanco a negro. Separamos las aristas dirigidas en
$$M_1=\{\text{movimientos de negro a blanco}\},\qquad M_2=\{\text{movimientos de blanco a negro}\}.$$
En \(M_1\), cada celda negra tiene exactamente una salida, y cada celda blanca recibe exactamente una entrada desde algún vecino negro. Por tanto, \(M_1\) es un emparejamiento perfecto del grafo bipartito de la cuadrícula. El mismo razonamiento vale para \(M_2\).
La prohibición de “intercambiar posiciones a través de la misma arista” significa exactamente que \(M_1\) y \(M_2\) no pueden compartir una arista no dirigida. Así, las migraciones válidas están en biyección con pares ordenados \((M_1,M_2)\) de emparejamientos perfectos disjuntos por aristas. Esa es la reformulación central usada por los tres programas del repositorio.
Si \(n\) es impar, el coloreado bipartito contiene cantidades distintas de celdas negras y blancas:
$$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$$
Un emparejamiento perfecto en un grafo bipartito requiere que ambos lados tengan el mismo tamaño. Luego
$$F(n)=0\qquad\text{cuando }n\text{ es impar.}$$
Esto coincide con la comprobación del código C++, donde la validación por fuerza bruta para \(n=3\) confirma que \(F(3)=0\).
Las implementaciones procesan el tablero fila por fila. Para una capa de matching, una máscara \(in\) indica qué columnas de la fila actual ya están ocupadas por una arista vertical proveniente de la fila anterior. Si el bit \(c\) está activo, entonces la celda \((r,c)\) ya está resuelta en esa capa y no necesita una nueva decisión dentro de la fila.
Como en el problema debemos seguir dos matchings a la vez, el estado es el par \((in_1,in_2)\). El código lo empaqueta como
$$state = in_1 + (in_2 \ll n).$$
Al terminar la fila obtenemos otro par \((out_1,out_2)\), que representa las aristas verticales que continúan hacia la fila siguiente.
Dentro de una capa de matching, una celda libre tiene solo dos maneras de quedar emparejada al avanzar de izquierda a derecha:
$$\text{horizontal con }(r,c+1)\qquad\text{o}\qquad \text{vertical con }(r+1,c).$$
Si la celda ya estaba cubierta por una arista vertical que venía desde arriba, la única opción es “filled”. En la última fila no se permite la opción vertical porque no existe fila inferior.
Eso es exactamente lo que devuelve options_for_cell en C++, Python y Java: Filled, Horizontal o Vertical, junto con las actualizaciones de bits para la ocupación de la fila y para la máscara de salida.
Dentro de una misma capa, la máscara de ocupación ya impide reutilizar una celda. Entre capas, el único conflicto posible es reutilizar la misma arista no dirigida, porque eso correspondería a dos direcciones opuestas sobre esa arista. En la columna actual \(c\), eso solo puede ocurrir de dos formas:
$$\text{las dos capas eligen la misma arista horizontal }(r,c)\text{--}(r,c+1),$$
$$\text{las dos capas eligen la misma arista vertical }(r,c)\text{--}(r+1,c).$$
Por eso la DFS del código rechaza únicamente los pares (Horizontal, Horizontal) y (Vertical, Vertical) en la misma columna. No hace falta ninguna otra prueba cruzada.
Para máscaras de entrada fijas \((in_1,in_2)\) y un indicador de si estamos en la última fila, la búsqueda en profundidad enumera todos los rellenados legales de esa fila y cuenta cuántos producen cada salida \((out_1,out_2)\). Denotemos esa multiplicidad por
$$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2)).$$
Entonces la recurrencia es
$$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2)).$$
La condición inicial es
$$\mathrm{DP}_0(0,0)=1,$$
porque antes de la primera fila no hay aristas verticales pendientes. La respuesta final es
$$F(n)=\mathrm{DP}_n(0,0),$$
ya que después de la última fila tampoco pueden quedar conexiones abiertas hacia abajo.
La cuadrícula \(2 \times 2\) tiene exactamente dos emparejamientos perfectos: las dos aristas horizontales o las dos verticales. Como las dos capas deben ser disjuntas por aristas, una capa debe elegir el matching horizontal y la otra el vertical. El par es ordenado, así que obtenemos dos configuraciones:
$$F(2)=2.$$
Son precisamente los dos ciclos dirigidos de longitud \(4\), uno horario y otro antihorario, en acuerdo con el checkpoint f(2)=2.
La versión en C++ mantiene dp como unordered_map<int, BigInt>, donde la clave es el perfil empaquetado y el valor es el número de maneras de llegar a él. La estructura transition_cache_ memoriza la lista de transiciones ya calculada para cada triple \((in_1,in_2,last\_row)\). La versión en Python usa diccionarios normales y enteros de precisión arbitraria. La versión en Java replica el mismo diseño con HashMap, objetos Transition y BigInteger.
Además, el archivo C++ contiene validaciones internas: comprueba \(F(2)=2\), \(F(4)=88\) y compara con fuerza bruta para \(n=3\). Para la entrada real de Project Euler, \(n=10\), las implementaciones producen
$$112398351350823112.$$
El espacio de perfiles es un subconjunto de
$$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n,$$
por lo que hay a lo sumo \(2^{2n}\) máscaras combinadas. Construir una tabla de transición no cacheada sigue siendo exponencial en \(n\), porque la DFS explora todos los rellenados legales de una fila para las dos capas acopladas. Sin embargo, cada perfil \((in_1,in_2,last\_row)\) se resuelve una sola vez y luego se reutiliza en la DP exterior. En consecuencia, el algoritmo es exponencial en el ancho del tablero, pero solo lineal en el número de filas una vez memorizadas las transiciones. La memoria también es exponencial en \(n\), dominada por los estados activos y por la caché de transiciones. Aun así, para \(n=10\) resulta viable, mientras que enumerar directamente todas las elecciones de vecino sería completamente inviable.
solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java.设 \(F(n)\) 表示 \(n \times n\) 网格上的合法迁移方案数。每个格子最初有一只蚂蚁，每只蚂蚁必须移动到一个相邻格子，每个格子最终也必须恰好接收一只蚂蚁，并且同一条无向边不能被两只蚂蚁以相反方向同时使用。用图论语言说，每个顶点的出度与入度都等于 \(1\)，因此合法方案是若干个有向环的并，而且长度为 \(2\) 的环被禁止。
把网格按棋盘方式染成黑白两色。任意相邻格子颜色相反，所以每一步移动一定是黑到白或白到黑。把所有有向边拆成两层：
$$M_1=\{\text{从黑格到白格的移动}\},\qquad M_2=\{\text{从白格到黑格的移动}\}.$$
观察 \(M_1\)。每个黑格恰好送出一只蚂蚁，因此每个黑格在 \(M_1\) 中恰好关联一条边；每个白格恰好接收一只蚂蚁，而来源只能是相邻黑格，因此每个白格在 \(M_1\) 中也恰好关联一条边。于是 \(M_1\) 是该二分图上的一个完美匹配。同理，\(M_2\) 也是一个完美匹配。
题目禁止“两只蚂蚁沿同一条边交换位置”，这正好等价于 \(M_1\) 与 \(M_2\) 不能共享同一条无向边。因此，合法迁移与有序的边不相交完美匹配对 \((M_1,M_2)\) 一一对应。这就是三个本地实现共同使用的核心重述。
如果 \(n\) 为奇数，那么棋盘染色后黑格与白格的数量不同：
$$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$$
二分图要存在完美匹配，两侧大小必须相同，所以奇数阶时根本不存在完美匹配，从而
$$F(n)=0\qquad\text{当 }n\text{ 为奇数时。}$$
这与代码中的校验一致：C++ 程序对 \(n=3\) 做了暴力对照，结果确实为 \(F(3)=0\)。
程序按行处理整个棋盘。对于某一层 matching，当前行中有些格子可能已经通过来自上一行的竖边被占用，代码用一个位掩码 \(in\) 记录这些列。如果第 \(c\) 位为 \(1\)，就表示 \((r,c)\) 这个格子在该层里已经被匹配，不需要在本行再做决定。
由于本题要同时处理两层 matching，状态是 \((in_1,in_2)\) 这一对掩码。代码把它们打包成一个整数：
$$state = in_1 + (in_2 \ll n).$$
处理完这一行后，会得到新的 \((out_1,out_2)\)，表示哪些列通过竖边继续连到下一行。
在单层 matching 中，若一个格子当前还未被占用，那么从左到右扫描时它只有两种匹配方式：
$$\text{与 }(r,c+1)\text{ 做水平匹配}\qquad\text{或}\qquad \text{与 }(r+1,c)\text{ 做竖直匹配}.$$
如果该格子已经被上方来的竖边覆盖，那么唯一选项就是 “filled”。到了最后一行，由于下面没有格子，竖直匹配不再允许。
这正是三个实现中 options_for_cell 的作用：返回 Filled、Horizontal、Vertical 三种类型之一，并附带当前占用掩码和输出掩码需要增加的位。
在同一层内部，占用掩码已经保证每个格子只会被使用一次。两层之间真正需要禁止的，只有“重复使用同一条无向边”，因为那对应的正是题目不允许的反向对冲。对当前列 \(c\) 而言，这只会以两种方式出现：
$$\text{两层同时选择同一条水平边 }(r,c)\text{--}(r,c+1),$$
$$\text{两层同时选择同一条竖直边 }(r,c)\text{--}(r+1,c).$$
所以代码中的 DFS 只需要排除同列上的 (Horizontal, Horizontal) 和 (Vertical, Vertical) 这两种组合，不需要别的跨层冲突判断。
对于固定的输入掩码 \((in_1,in_2)\) 和是否为最后一行的标志，深度优先搜索会枚举当前行的所有合法填法，并统计每个输出 \((out_1,out_2)\) 出现多少次。记这个重数为
$$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2)).$$
那么行 DP 的递推式就是
$$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2)).$$
初始条件为
$$\mathrm{DP}_0(0,0)=1,$$
因为处理第一行之前没有任何悬空的竖边。最终答案是
$$F(n)=\mathrm{DP}_n(0,0),$$
因为最后一行结束后也不能留下未闭合的竖向连接。
\(2 \times 2\) 网格只有两个完美匹配：要么选两条水平边，要么选两条竖直边。由于两层必须边不相交，一层必须取水平 matching，另一层必须取竖直 matching。又因为这是有序对，所以共有两种方案：
$$F(2)=2.$$
它们正对应正方形上的顺时针与逆时针两个 4-环，与代码中的检查点 f(2)=2 完全一致。
C++ 版本把 dp 存为 unordered_map<int, BigInt>，键是打包后的轮廓状态，值是到达该状态的方案数。transition_cache_ 负责缓存三元组 \((in_1,in_2,last\_row)\) 已经算出的转移列表。Python 版本使用普通字典和任意精度整数；Java 版本则用 HashMap、显式的 Transition 对象以及 BigInteger 实现同样的逻辑。
C++ 文件还内置了若干校验：\(F(2)=2\)、\(F(4)=88\)，以及 \(n=3\) 时与暴力枚举对照。对于 Project Euler 真正要求的 \(n=10\)，这些实现输出
$$112398351350823112.$$
轮廓状态空间是
$$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n,$$
因此组合掩码最多有 \(2^{2n}\) 个。对某个尚未缓存的状态生成完整转移表，本身就对 \(n\) 呈指数级，因为 DFS 要枚举两层耦合 matching 在一整行上的所有合法填法。不过每个 \((in_1,in_2,last\_row)\) 只会被求解一次，之后在外层 DP 中反复复用。于是总体算法对棋盘宽度是指数级，对行数则在转移缓存后近似线性。内存同样是指数级，主要由活动 DP 状态和转移缓存占据。对于 \(n=10\) 这仍然可行，而直接枚举每只蚂蚁的邻居选择则完全不可计算。
solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java。Обозначим через \(F(n)\) число корректных миграций на решетке \(n \times n\). В каждой клетке изначально стоит одна муравьиная особь; каждая должна перейти в соседнюю клетку; каждая клетка в конце должна получить ровно одну муравьиную особь; и одна и та же неориентированная грань не может использоваться одновременно в противоположных направлениях. На языке графов это означает, что у каждой вершины исходящая степень равна \(1\), входящая степень тоже равна \(1\), так что конфигурация распадается на непересекающиеся ориентированные циклы, причем 2-циклы запрещены.
Раскрасим клетки в шахматном порядке в черный и белый цвета. Любой допустимый ход соединяет клетки разных цветов. Разобьем все ориентированные ребра на два множества:
$$M_1=\{\text{переходы из черной клетки в белую}\},\qquad M_2=\{\text{переходы из белой клетки в черную}\}.$$
В \(M_1\) каждая черная вершина имеет ровно одно исходящее ребро, а каждая белая вершина получает ровно одно входящее ребро от черного соседа. Следовательно, \(M_1\) является совершенным паросочетанием двудольного графа решетки. Тот же аргумент дает, что \(M_2\) тоже является совершенным паросочетанием.
Запрет на обмен местами по одной и той же грани означает ровно то, что \(M_1\) и \(M_2\) не должны делить одну и ту же неориентированную грань. Значит, допустимые миграции находятся в биекции с упорядоченными парами \((M_1,M_2)\) реберно-непересекающихся совершенных паросочетаний. Именно эта эквивалентность лежит в основе всех локальных реализаций.
Если \(n\) нечетно, то при шахматной раскраске числа черных и белых клеток различаются:
$$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$$
В двудольном графе совершенное паросочетание возможно только при равенстве размеров долей. Поэтому
$$F(n)=0\qquad\text{для нечетных }n.$$
Это согласуется с проверкой в C++-файле: для \(n=3\) профильное DP совпадает с полным перебором и дает \(F(3)=0\).
Программы обрабатывают доску построчно. Для одного слоя matching маска \(in\) показывает, какие столбцы текущей строки уже заняты вертикальными ребрами из предыдущей строки. Если бит \(c\) установлен, то клетка \((r,c)\) в этом слое уже покрыта и не требует нового решения внутри текущей строки.
Поскольку в задаче одновременно учитываются два слоя, состояние равно паре \((in_1,in_2)\). В коде она упакована в одно число:
$$state = in_1 + (in_2 \ll n).$$
После обработки строки получается новая пара \((out_1,out_2)\), описывающая вертикальные ребра, уходящие вниз в следующую строку.
Внутри одного слоя matching незанятая клетка при проходе слева направо может быть покрыта только двумя способами:
$$\text{горизонтально с }(r,c+1)\qquad\text{или}\qquad \text{вертикально с }(r+1,c).$$
Если клетка уже покрыта вертикальным ребром сверху, остается только вариант Filled. В последней строке вертикальный выбор вниз запрещен, потому что строки ниже нет.
Именно это возвращает вспомогательная функция options_for_cell в C++, Python и Java: тип Filled, Horizontal или Vertical вместе с тем, какие биты нужно добавить к маске занятости и к исходящей маске.
Внутри одного слоя маска занятости уже гарантирует, что каждая клетка используется ровно один раз. Между слоями запрещено только повторное использование одной и той же неориентированной грани, потому что это и есть встречное движение по одной грани. Для текущего столбца \(c\) это возможно только в двух случаях:
$$\text{оба слоя выбирают одну и ту же горизонтальную грань }(r,c)\text{--}(r,c+1),$$
$$\text{оба слоя выбирают одну и ту же вертикальную грань }(r,c)\text{--}(r+1,c).$$
Поэтому DFS в программе отбрасывает только пары (Horizontal, Horizontal) и (Vertical, Vertical) в одном и том же столбце. Других межслоевых тестов не требуется.
Для фиксированных входных масок \((in_1,in_2)\) и признака последней строки поиск в глубину перечисляет все допустимые заполнения строки и подсчитывает, сколько из них приводят к каждому выходу \((out_1,out_2)\). Обозначим эту кратность через
$$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2)).$$
Тогда рекуррентное соотношение имеет вид
$$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2)).$$
Начальное условие равно
$$\mathrm{DP}_0(0,0)=1,$$
так как перед первой строкой нет незавершенных вертикальных ребер. Искомое значение равно
$$F(n)=\mathrm{DP}_n(0,0),$$
поскольку после последней строки тоже не должно остаться открытых вертикальных продолжений.
У решетки \(2 \times 2\) есть ровно два совершенных паросочетания: две горизонтальные грани или две вертикальные. Так как слои должны быть реберно-непересекающимися, один слой обязан взять горизонтальное паросочетание, а другой вертикальное. Пара упорядочена, поэтому получаем два варианта:
$$F(2)=2.$$
Это как раз два ориентированных 4-цикла вокруг квадрата, по и против часовой стрелки. Именно это и проверяет checkpoint f(2)=2.
В C++ решение хранит dp как unordered_map<int, BigInt>, где ключом служит упакованный профиль, а значением число способов попасть в него. Кэш transition_cache_ запоминает уже вычисленные переходы для тройки \((in_1,in_2,last\_row)\). Версия на Python использует обычные словари и встроенные целые произвольной длины. Версия на Java повторяет ту же идею через HashMap, объекты Transition и BigInteger.
Кроме того, C++-файл содержит внутренние проверки: \(F(2)=2\), \(F(4)=88\) и сравнение с полным перебором для \(n=3\). Для настоящего входа задачи Project Euler, то есть \(n=10\), программы выдают
$$112398351350823112.$$
Пространство профилей является подмножеством
$$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n,$$
поэтому всего существует не более \(2^{2n}\) объединенных масок. Построение одной еще не закэшированной таблицы переходов уже экспоненциально по \(n\), потому что DFS перебирает все допустимые заполнения строки для двух связанных слоев matching. Однако каждый профиль \((in_1,in_2,last\_row)\) вычисляется только один раз и затем многократно переиспользуется во внешнем DP. Следовательно, алгоритм экспоненциален по ширине доски, но после кэширования переходов лишь линеен по числу строк. Память тоже растет экспоненциально по \(n\), поскольку основными потребителями являются фронт DP и кэш переходов. Для \(n=10\) это еще выполнимо, тогда как наивный перебор всех соседних переходов для каждой муравьиной особи был бы практически невозможен.
solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java.لنرمز بـ \(F(n)\) إلى عدد أنماط الهجرة الصحيحة على شبكة \(n \times n\). كل خلية تحتوي في البداية على نملة واحدة، وكل نملة يجب أن تنتقل إلى خلية مجاورة، وكل خلية يجب أن تستقبل نملة واحدة بالضبط، كما لا يجوز لنملتين أن تستعملا الحافة غير الموجهة نفسها في اتجاهين متعاكسين. بلغة الرسوم البيانية هذا يعني أن لكل رأس درجة خروج \(1\) ودرجة دخول \(1\)، ولذلك تتفكك أي هجرة صحيحة إلى اتحاد من دورات موجهة منفصلة، مع منع الدورات ذات الطول \(2\).
نلوّن الشبكة بتلوين رقعة الشطرنج إلى خلايا سوداء وبيضاء. كل حركة قانونية تصل بين لونين مختلفين، لذا نرمز إلى الحركات من الأسود إلى الأبيض بـ \(M_1\)، وإلى الحركات من الأبيض إلى الأسود بـ \(M_2\).
في \(M_1\) تملك كل خلية سوداء حركة خروج واحدة بالضبط، وكل خلية بيضاء تستقبل حركة دخول واحدة بالضبط من جار أسود. إذن \(M_1\) مطابقة كاملة في الرسم البياني الثنائي للشبكة. وبالحجة نفسها تكون \(M_2\) أيضًا مطابقة كاملة.
أما شرط منع “تبادل المكان عبر الحافة نفسها” فيعني تمامًا أن \(M_1\) و\(M_2\) لا يجوز أن يشتركا في الحافة غير الموجهة نفسها. لذلك توجد مطابقة واحد لواحد بين الهجرات الصحيحة وبين الأزواج المرتبة \((M_1,M_2)\) من المطابقات الكاملة المتباينة حافيًا. وهذا هو الوصف المركزي الذي تعتمد عليه ملفات الحل المحلية.
إذا كان \(n\) فرديًا، فإن عدد الخلايا السوداء يختلف عن عدد الخلايا البيضاء:
$$\left\lceil\frac{n^2}{2}\right\rceil \neq \left\lfloor\frac{n^2}{2}\right\rfloor.$$
والمطابقة الكاملة في رسم بياني ثنائي تتطلب تساوي حجم القسمين، ولذلك نحصل مباشرة على
$$F(n)=0.$$
وهذا يطابق ما يتحقق منه كود ++C، إذ يقارن الناتج مع brute force عند \(n=3\) ويجد بالفعل أن \(F(3)=0\).
تعالج البرامج اللوح صفًا صفًا. في طبقة matching واحدة قد تكون بعض خلايا الصف الحالي مشغولة أصلًا بسبب حافة عمودية جاءت من الصف السابق، ولهذا يخزن الكود هذه الأعمدة في قناع بتات \(in\). إذا كانت البتة \(c\) مفعلة فهذا يعني أن الخلية \((r,c)\) مغطاة سابقًا في تلك الطبقة ولا تحتاج إلى قرار جديد داخل الصف الحالي.
ولأن المسألة تتطلب تتبع طبقتين معًا، تكون الحالة هي الزوج \((in_1,in_2)\). ويقوم الكود بضغطه في عدد صحيح واحد على الصورة:
$$state = in_1 + (in_2 \ll n).$$
وبعد إنهاء الصف نحصل على \((out_1,out_2)\)، أي الأقنعة التي تمثل الحواف العمودية الممتدة إلى الصف التالي.
داخل طبقة matching واحدة، إذا كانت الخلية غير مشغولة أثناء المسح من اليسار إلى اليمين فليس أمامها إلا طريقتان للتغطية: إما مطابقة أفقية مع \((r,c+1)\)، أو مطابقة عمودية مع \((r+1,c)\).
أما إذا كانت الخلية قد غُطيت بالفعل بحافة عمودية من الأعلى فليس إلا الخيار Filled. وفي الصف الأخير تُمنع المطابقة العمودية إلى الأسفل لعدم وجود صف تالٍ.
وهذا بالضبط ما تعيده الدالة options_for_cell في نسخ ++C وPython وJava: أحد الأنواع Filled أو Horizontal أو Vertical، مع تحديثات البتات اللازمة لقناع الإشغال الحالي وقناع الخروج.
داخل الطبقة الواحدة يضمن قناع الإشغال أن كل خلية تستعمل مرة واحدة فقط. وبين الطبقتين لا يوجد تعارض محظور إلا إعادة استعمال الحافة غير الموجهة نفسها، لأن ذلك يعني السير عليها في اتجاهين متعاكسين. وعند العمود الحالي \(c\) لا يحدث هذا إلا في حالتين: أن تختار الطبقتان الحافة الأفقية نفسها \((r,c)\text{--}(r,c+1)\)، أو أن تختارا الحافة العمودية نفسها \((r,c)\text{--}(r+1,c)\).
لهذا يرفض البحث العميق في الكود فقط الزوجين (Horizontal, Horizontal) و(Vertical, Vertical) في العمود نفسه. ولا حاجة إلى أي فحوصات تقاطع إضافية بين الطبقتين.
عند تثبيت أقنعة الإدخال \((in_1,in_2)\) ومعرفة ما إذا كنا في الصف الأخير، يقوم البحث العميق بعدّ جميع طرق ملء الصف الحالية، ويجمع عدد المرات التي تنتج كل مخرجات \((out_1,out_2)\). لنكتب هذه الكثرة على الصورة
$$T_{\mathrm{last}}((in_1,in_2)\to(out_1,out_2)).$$
عندئذ تصبح علاقة البرمجة الديناميكية
$$\mathrm{DP}_{r+1}(out_1,out_2)=\sum_{in_1,in_2}\mathrm{DP}_r(in_1,in_2)\,T_{\mathrm{last}(r)}((in_1,in_2)\to(out_1,out_2)).$$
والشرط الابتدائي هو
$$\mathrm{DP}_0(0,0)=1,$$
لأنه قبل الصف الأول لا توجد حواف عمودية مفتوحة. أما الجواب النهائي فهو
$$F(n)=\mathrm{DP}_n(0,0),$$
لأننا بعد الصف الأخير يجب ألا نترك أي امتداد عمودي غير مغلق.
تملك شبكة \(2 \times 2\) مطابقتين كاملتين فقط: إما الحافتان الأفقيتان أو الحافتان العموديتان. وبما أن الطبقتين يجب أن تكونا متباينتين حافيًا، فلا بد أن تختار إحداهما المطابقة الأفقية والأخرى المطابقة العمودية. ولأن الزوج مرتب نحصل على حالتين:
$$F(2)=2.$$
وهاتان الحالتان هما الدورتان الموجهتان حول المربع مع عقارب الساعة وعكسها، وهذا يطابق نقطة التحقق f(2)=2 في المستودع.
يخزن حل ++C البنية dp على هيئة unordered_map<int, BigInt>، حيث يكون المفتاح هو حالة الملف المضغوطة، والقيمة هي عدد الطرق المؤدية إليها. أما transition_cache_ فيحفظ قائمة الانتقالات المحسوبة مسبقًا لكل ثلاثي \((in_1,in_2,last\_row)\). تستخدم نسخة Python القواميس العادية والأعداد الصحيحة ذات الدقة غير المحدودة، بينما تعيد نسخة Java البنية نفسها باستخدام HashMap وكائنات Transition وBigInteger.
كما يحتوي ملف ++C على اختبارات داخلية: \(F(2)=2\)، و\(F(4)=88\)، ومقارنة مع brute force عندما \(n=3\). وبالنسبة لإدخال Project Euler الحقيقي عند \(n=10\)، تعطي جميع التطبيقات
$$112398351350823112.$$
فضاء الحالات هو مجموعة جزئية من
$$\mathcal{S}\subseteq \{0,1\}^n \times \{0,1\}^n,$$
ولذلك يوجد في الحد الأقصى \(2^{2n}\) من الأقنعة المجمعة. إن توليد خريطة انتقال واحدة غير مخزنة مؤقتًا هو نفسه أسي في \(n\)، لأن البحث العميق يستكشف جميع طرائق ملء الصف القانونية لطبقتين مترابطتين من الـ matching. لكن كل ملف شخصي \((in_1,in_2,last\_row)\) يُحسب مرة واحدة فقط ثم يُعاد استعماله كلما ظهر من جديد في البرمجة الديناميكية الخارجية. لذلك فالخوارزمية أسية في عرض اللوح، ولكنها تصبح خطية في عدد الصفوف بعد إعادة استخدام الانتقالات. واستهلاك الذاكرة أسي أيضًا في \(n\)، ويهيمن عليه كل من حالات DP النشطة وذاكرة الانتقالات المؤقتة. ومع ذلك يبقى هذا عمليًا عندما \(n=10\)، في حين أن التعداد المباشر لكل اختيارات الجيران سيكون مستحيلًا عمليًا.
solutionsCpp/Euler393.cpp, solutionsPython/Euler393.py, solutionsJava/Euler393.java.