On an \(n\times n\) board we place exactly one queen in each row. A queen does not attack forever: it attacks vertically and diagonally only up to row distance \(D\), where
$$D=n-1-w.$$
Let \(Q(n,w)\) be the number of legal placements for weakness parameter \(w\). It is convenient to reparameterize by \(D\) and write \(N(n,D)=Q(n,n-1-D)\). Then the required quantity is
$$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D).$$
The endpoint cases clarify the model. When \(D=0\), no queen can reach a different row, so every row may use any of the \(n\) columns and \(N(n,0)=n^n\). When \(D=n-1\), every pair of rows can interact, so we recover the ordinary \(n\)-queens condition.
The decisive observation is that a queen more than \(D\) rows above the current row is irrelevant. Therefore a partial placement is completely summarized by the most recent \(D\) chosen columns.
Instead of summing directly over \(w\), we solve the fixed-depth problem \(N(n,D)\). This removes one layer of notation and matches the actual row-by-row rule: only row pairs whose distance is at most \(D\) can attack each other.
After computing every \(N(n,D)\) independently, the final answer is the outer sum
$$S(n)=\sum_{D=0}^{n-1}N(n,D).$$
Let \(c_r\in\{0,1,\dots,n-1\}\) denote the column used in row \(r\). A queen already placed in row \(r-d\) affects row \(r\) only when \(1\le d\le D\). In that case it forbids three possibilities:
$$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$$
whenever those columns stay inside the board. The first condition is the vertical attack, and the other two are the diagonals. Nothing older than \(D\) rows can matter.
After placing the first \(r\) rows, define \(\ell=\min(r,D)\). The future depends only on the tuple
$$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1}).$$
Two partial boards with the same tuple \(\sigma_r\) are equivalent for all future choices, because every earlier queen is already more than \(D\) rows away from the next row and can never attack again. This turns the search into dynamic programming on recent-history states.
Suppose the current state is \(\sigma=(a_1,\dots,a_\ell)\), with \(a_1\) the most recent column. The blocked set for the next row is
$$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}.$$
Every column in \(\{0,1,\dots,n-1\}\setminus B(\sigma)\) is legal. Choosing such a column \(c\) produces the new recent-history tuple obtained by putting \(c\) in front and dropping the oldest remembered column if necessary.
If \(F_r(\sigma)\) denotes the number of partial boards of height \(r\) that lead to state \(\sigma\), then the next layer is obtained by adding \(F_r(\sigma)\) to every legal successor of \(\sigma\).
Many different partial boards collapse to the same recent-history tuple. Once the next-row successors have been generated, equal tuples are merged and their multiplicities are added. This is the key compression step: the algorithm never distinguishes two histories once their last \(D\) columns agree.
The merging is exact because the future attack pattern is determined entirely by the recent tuple, so no information is lost.
When \(D=1\), each row interacts only with the immediately previous row, so the state is just the last column. If the previous column is \(0\), the next row may use only \(2\) or \(3\). If it is \(1\), only \(3\) is legal. If it is \(2\), only \(0\) is legal. If it is \(3\), only \(0\) or \(1\) are legal.
Starting from the first row, the counts of partial boards ending in columns \(0,1,2,3\) evolve as
$$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$$
Hence \(N(4,1)=16\). The same framework also gives \(N(4,0)=4^4=256\), \(N(4,2)=2\), and \(N(4,3)=2\), so
$$S(4)=256+16+2+2=276.$$
The C++, Python, and Java implementations all use this finite-memory dynamic program. For a fixed \(D\), they begin with the empty state of multiplicity \(1\), process rows from top to bottom, rebuild the blocked columns from the remembered recent columns, and enumerate every legal next column.
The compiled implementations store the remembered columns in a compact integer representation, using four bits per remembered row, which is sufficient for the target size \(n=14\). After each row, the generated successor states are ordered by their encoded state and equal states are merged by adding their counts.
Once all \(n\) rows have been processed, the counts of the surviving states are summed to obtain \(N(n,D)\). The outer routine repeats this for every \(D=0,1,\dots,n-1\) and adds the results. Because these fixed-\(D\) tasks are independent, the compiled implementations distribute them across worker threads. The Python implementation serves as a thin front end to the same compiled computation.
For fixed \(D\), let \(F_r\) be the number of merged states after row \(r\), and let \(G_r\) be the number of generated successors before merging at the next step. Building the blocked set for one parent state scans at most \(D\) remembered queens, so the transition phase at that row costs \(O(F_rD+G_r)\). The implementations then sort the generated states before merging, which adds \(O(G_r\log G_r)\).
Therefore the total time for one value of \(D\) is
$$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right),$$
and the memory usage is \(O(\max_r G_r)\). A coarse worst-case bound is exponential in \(D\), since there can be up to \(n^D\) recent-history states, but for the required instance \(n=14\) the state merging keeps the frontier manageable enough for a direct computation.
Auf einem \(n\times n\)-Brett wird genau eine Dame pro Zeile gesetzt. Eine Dame greift nicht unbegrenzt weit an: Vertikale und diagonale Angriffe reichen nur bis zur Zeilendistanz \(D\), wobei
$$D=n-1-w.$$
Sei \(Q(n,w)\) die Zahl der zulassigen Stellungen fur den Schwacheparameter \(w\). ZweckmaBig ist die Umparametrisierung uber \(D\):
$$N(n,D)=Q(n,n-1-D).$$
Dann lautet die gesuchte Summe
$$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D).$$
Die Randfalle zeigen die Struktur sofort. Fur \(D=0\) kann keine Dame eine andere Zeile erreichen, also hat jede Zeile frei \(n\) Spalten zur Wahl und damit \(N(n,0)=n^n\). Fur \(D=n-1\) konnen alle Zeilenpaare wechselwirken, also entsteht das gewohnliche Damenproblem.
Die entscheidende Beobachtung ist: Eine Dame, die mehr als \(D\) Zeilen uber der aktuellen Zeile steht, ist vollstandig irrelevant. Deshalb wird eine Teilbelegung vollstandig durch die letzten \(D\) gewahlten Spalten beschrieben.
Statt direkt uber \(w\) zu summieren, losen wir das Problem fur feste Angriffstiefe \(N(n,D)\). Das passt exakt zur zeilenweisen Konstruktion, denn nur Zeilen mit Abstand hochstens \(D\) konnen einander angreifen.
Nachdem alle Werte \(N(n,D)\) getrennt berechnet sind, liefert
$$S(n)=\sum_{D=0}^{n-1}N(n,D)$$
die gesuchte Endsumme.
Sei \(c_r\in\{0,1,\dots,n-1\}\) die Spalte der Dame in Zeile \(r\). Eine Dame in Zeile \(r-d\) beeinflusst Zeile \(r\) nur fur \(1\le d\le D\). Dann verbietet sie drei Moglichkeiten:
$$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$$
sofern diese Spalten noch auf dem Brett liegen. Die erste Bedingung ist der vertikale Angriff, die beiden anderen sind die Diagonalen. Altere Zeilen spielen keine Rolle mehr.
Nach den ersten \(r\) gesetzten Zeilen sei \(\ell=\min(r,D)\). Fur die Zukunft ist nur das Tupel
$$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1})$$
wichtig. Zwei Teilbelegungen mit demselben Tupel \(\sigma_r\) sind fur alle spateren Entscheidungen aquivalent, weil jede noch fruhere Dame bereits mehr als \(D\) Zeilen entfernt ist und nie wieder angreifen kann. Damit wird die Suche zu einer dynamischen Programmierung uber Zustande mit kurzer Historie.
Sei \(\sigma=(a_1,\dots,a_\ell)\) der aktuelle Zustand, wobei \(a_1\) die jungste Spalte ist. Die verbotene Menge fur die nachste Zeile lautet
$$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}.$$
Jede Spalte aus \(\{0,1,\dots,n-1\}\setminus B(\sigma)\) ist zulassig. Wahlen wir eine solche Spalte \(c\), entsteht der Folgezustand, indem \(c\) vorne eingefugt und bei Bedarf die alteste gemerkte Spalte entfernt wird.
Bezeichnet \(F_r(\sigma)\) die Zahl der Teilbelegungen der Hohe \(r\) mit Zustand \(\sigma\), dann wird \(F_r(\sigma)\) zu jedem legalen Folgezustand addiert.
Viele verschiedene Teilbelegungen enden in derselben kurzen Historie. Nachdem alle Nachfolgezustande erzeugt wurden, werden gleiche Tupel zusammengelegt und ihre Anzahlen addiert. Genau diese Verdichtung macht den Ansatz praktikabel.
Das ist mathematisch exakt, weil das gesamte zukunftige Angriffsmuster allein durch das aktuelle Historientupel bestimmt wird.
Fur \(D=1\) wechselwirkt jede Zeile nur mit der unmittelbar vorherigen Zeile, also besteht der Zustand nur aus der letzten Spalte. Steht die vorherige Dame in Spalte \(0\), dann sind fur die nachste Zeile nur \(2\) und \(3\) moglich. Bei Spalte \(1\) ist nur \(3\) erlaubt, bei Spalte \(2\) nur \(0\), und bei Spalte \(3\) sind \(0\) oder \(1\) moglich.
Ausgehend von der ersten Zeile entwickeln sich die Zahlen der Teilbelegungen mit Endspalten \(0,1,2,3\) zu
$$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$$
Also ist \(N(4,1)=16\). Derselbe Rahmen ergibt auBerdem \(N(4,0)=4^4=256\), \(N(4,2)=2\) und \(N(4,3)=2\), also
$$S(4)=256+16+2+2=276.$$
Die C++-, Python- und Java-Implementierungen benutzen alle genau diese DP mit endlichem Gedachtnis. Fur festes \(D\) starten sie mit dem leeren Zustand der Multiplizitat \(1\), gehen Zeile fur Zeile vor, rekonstruieren aus den gemerkten Spalten die blockierten Spalten und enumerieren jede erlaubte nachste Spalte.
Die kompilierten Implementierungen speichern die gemerkten Spalten in einer kompakten Ganzzahldarstellung mit vier Bits pro gemerkter Zeile; das reicht fur die ZielgroBe \(n=14\) aus. Nach jeder Zeile werden die erzeugten Folgezustande nach ihrem kodierten Zustand geordnet und gleiche Zustande durch Addition ihrer Anzahlen verschmolzen.
Nach \(n\) Zeilen werden die Anzahlen aller verbleibenden Zustande summiert; das ist \(N(n,D)\). AuBen herum wird dieser Ablauf fur alle \(D=0,1,\dots,n-1\) wiederholt und addiert. Weil diese Aufgaben fur festes \(D\) unabhangig sind, verteilen die kompilierten Implementierungen sie auf mehrere Worker-Threads. Die Python-Implementierung dient als schlanke Hulle um dieselbe kompilierte Berechnung.
Fur festes \(D\) sei \(F_r\) die Zahl der zusammengefassten Zustande nach Zeile \(r\), und \(G_r\) die Zahl der erzeugten Nachfolger vor dem Zusammenfassen im nachsten Schritt. Das Aufbauen der Sperrmenge fur einen Elternzustand betrachtet hochstens \(D\) gemerkte Damen, daher kostet die Ubergangsphase \(O(F_rD+G_r)\). Danach werden die erzeugten Zustande sortiert, was weitere \(O(G_r\log G_r)\) kostet.
Damit ist die Gesamtlaufzeit fur ein festes \(D\)
$$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right),$$
und der Speicherverbrauch ist \(O(\max_r G_r)\). Eine grobe Schranke ist exponentiell in \(D\), weil es bis zu \(n^D\) Historienzustande geben kann. Fur die geforderte Instanz \(n=14\) reicht die starke Zustandsverschmelzung jedoch fur eine direkte Berechnung aus.
\(n\times n\) tahtada her satira tam bir vezir yerlestiriyoruz. Bir vezir sonsuza kadar saldirmaz; dikey ve capraz saldirilar yalnizca \(D\) satirlik mesafeye kadar etkilidir ve
$$D=n-1-w.$$
\(Q(n,w)\), zayiflik parametresi \(w\) icin gecerli yerlestirme sayisi olsun. Hesabi sadeleştirmek icin \(D\) ile yeniden yazariz:
$$N(n,D)=Q(n,n-1-D).$$
Boylece istenen toplam
$$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D)$$
olur. Uc durumlar problemi iyi aciklar. \(D=0\) iken hicbir vezir baska bir satira ulasamaz; her satir herhangi bir sutunu secebilir ve \(N(n,0)=n^n\) olur. \(D=n-1\) iken her satir cifti etkilesebildigi icin klasik \(n\)-vezir kisiti geri gelir.
Kilit gozlem sudur: Guncel satirdan \(D\) satirdan daha yukaridaki bir vezir artik tamamen onemsizdir. Bu nedenle bir kismi yerlestirme, secilen son \(D\) sutun ile tamamen ozetlenebilir.
Dogrudan \(w\) uzerinden toplamak yerine sabit derinlik problemi \(N(n,D)\) cozulur. Bu, satir satir kurulan gercek kisitla tam uyumludur; cunku yalnizca aralarindaki uzaklik en fazla \(D\) olan satirlar birbirine saldirabilir.
Butun \(N(n,D)\) degerleri bagimsiz hesaplandiktan sonra son cevap
$$S(n)=\sum_{D=0}^{n-1}N(n,D)$$
olur.
\(c_r\in\{0,1,\dots,n-1\}\), \(r\). satirdaki vezirin sutunu olsun. Daha once yerlestirilmis bir vezir ancak \(1\le d\le D\) icin, yani \(r-d\). satirdaysa, \(r\). satiri etkiler. Bu durumda uc olasiligi yasaklar:
$$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$$
tabii bu sutunlar tahta icinde kaldigi surece. Ilk kosul dikey saldiridir; diger ikisi iki caprazdir. \(D\)'den daha eski satirlarin hicbir etkisi kalmaz.
Ilk \(r\) satir yerlestirildikten sonra \(\ell=\min(r,D)\) olsun. Gelecek kararlar yalnizca
$$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1})$$
demetine baglidir. Ayni \(\sigma_r\) demetine sahip iki farkli kismi tahta, bundan sonraki butun secimler icin esdegerdir; cunku daha eski her vezir bir sonraki satirdan artik \(D\)'den fazla uzaktadir ve bir daha saldiramaz. Boylece arama, yakin gecmisi tutan bir dinamik programlamaya donusur.
Guncel durum \(\sigma=(a_1,\dots,a_\ell)\) olsun; burada \(a_1\) en son secilen sutundur. Sonraki satir icin yasak kume
$$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}$$
seklindedir. \(\{0,1,\dots,n-1\}\setminus B(\sigma)\) icindeki her sutun yasaldir. Boyle bir \(c\) secilirse yeni yakin-gecmis durumu, \(c\)'yi basa ekleyip gerekirse en eski kaydi atarak elde edilir.
\(F_r(\sigma)\), yuksekligi \(r\) olan ve durum olarak \(\sigma\)'ya ulasan kismi yerlestirme sayisi ise, sonraki katmanda her yasal ardil duruma \(F_r(\sigma)\) eklenir.
Pek cok farkli kismi yerlestirme ayni son \(D\) sutuna cokebilir. Sonraki satir adaylari uretildikten sonra ayni demetler birlestirilir ve cokluklari toplanir. Algoritmayi uygulanabilir yapan temel sikistirma budur.
Bu birlestirme tam dogrudur; cunku gelecekteki saldiri deseni sadece elde kalan yakin-gecmis demeti tarafindan belirlenir.
\(D=1\) oldugunda her satir sadece hemen onceki satirla etkilesir; dolayisiyla durum son sutundan ibarettir. Onceki sutun \(0\) ise sonraki satir yalnizca \(2\) veya \(3\) olabilir. Onceki sutun \(1\) ise yalnizca \(3\), \(2\) ise yalnizca \(0\), \(3\) ise \(0\) veya \(1\) secilebilir.
Ilk satirdan baslayinca, son sutunlari \(0,1,2,3\) olan kismi yerlestirme sayilari su sekilde ilerler:
$$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$$
Demek ki \(N(4,1)=16\). Ayni cerceve \(N(4,0)=4^4=256\), \(N(4,2)=2\) ve \(N(4,3)=2\) degerlerini de verir; dolayisiyla
$$S(4)=256+16+2+2=276.$$
C++, Python ve Java uygulamalari bu sonlu hafizali dinamik programlamayi kullanir. Sabit bir \(D\) icin bos durum ve cokluk \(1\) ile baslanir, satirlar yukaridan asagi islenir, hatirlanan son sutunlardan yasak sutunlar yeniden kurulur ve her yasal sonraki sutun denenir.
Derlenmis uygulamalar, hatirlanan sutunlari kompakt bir tamsayi icinde tutar; her kayitli satir icin dort bit kullanilir ve bu \(n=14\) icin yeterlidir. Her satirdan sonra uretilen ardil durumlar kodlanmis durum anahtarina gore siralanir ve ayni durumlar sayilari toplanarak birlestirilir.
Butun \(n\) satir tamamlaninca kalan durumlarin sayilari toplanarak \(N(n,D)\) elde edilir. Dis rutinin yaptigi sey bunu \(D=0,1,\dots,n-1\) icin tekrarlayip sonuclari toplamaktir. Bu sabit-\(D\) gorevleri birbirinden bagimsiz oldugu icin derlenmis uygulamalar bunlari is parcaciklarina dagitir. Python uygulamasi ise ayni derlenmis hesabin ince bir on yuzudur.
Sabit \(D\) icin \(F_r\), \(r\). satirdan sonra birlesmis durum sayisi; \(G_r\) ise bir sonraki adimda birlestirme oncesi uretilen ardil sayisi olsun. Bir ebeveyn durum icin yasak kumesi en fazla \(D\) hatirlanan veziri tarar; dolayisiyla gecis asamasi \(O(F_rD+G_r)\) maliyetlidir. Ardindan uretilen durumlar siralanir ve bu da \(O(G_r\log G_r)\) ekler.
Boylece sabit bir \(D\) icin toplam sure
$$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right)$$
ve bellek kullanimi \(O(\max_r G_r)\) olur. Kaba bir ust sinir \(D\)'ye gore usseldir; cunku yakin-gecmis durumlarinin sayisi en fazla \(n^D\) olabilir. Buna ragmen gerekli ornekte \(n=14\) oldugu icin durum birlestirme on cephesi yeterince kucultur ve dogrudan hesaplama mumkun olur.
En un tablero \(n\times n\) colocamos exactamente una reina en cada fila. Una reina no ataca de forma ilimitada: sus ataques verticales y diagonales solo alcanzan una distancia de \(D\) filas, donde
$$D=n-1-w.$$
Sea \(Q(n,w)\) el numero de configuraciones validas para el parametro de debilidad \(w\). Resulta mas comodo reparametrizar con \(D\) y definir
$$N(n,D)=Q(n,n-1-D).$$
Entonces la cantidad pedida es
$$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D).$$
Los casos extremos aclaran el modelo. Si \(D=0\), ninguna reina puede alcanzar otra fila, de modo que cada fila puede elegir cualquiera de las \(n\) columnas y \(N(n,0)=n^n\). Si \(D=n-1\), cualquier par de filas puede interactuar y reaparece el problema clasico de las \(n\) reinas.
La observacion decisiva es que una reina situada a mas de \(D\) filas por encima de la fila actual deja de importar por completo. Por eso una configuracion parcial queda determinada totalmente por las ultimas \(D\) columnas elegidas.
En lugar de sumar directamente sobre \(w\), resolvemos el problema de profundidad fija \(N(n,D)\). Esto encaja exactamente con la restriccion fila a fila, porque solo pueden atacarse las parejas de filas cuya distancia es como maximo \(D\).
Una vez calculados todos los valores \(N(n,D)\), la respuesta final es
$$S(n)=\sum_{D=0}^{n-1}N(n,D).$$
Sea \(c_r\in\{0,1,\dots,n-1\}\) la columna elegida en la fila \(r\). Una reina ya colocada en la fila \(r-d\) solo afecta a la fila \(r\) cuando \(1\le d\le D\). En ese caso prohíbe tres posibilidades:
$$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$$
siempre que esas columnas sigan dentro del tablero. La primera condicion corresponde al ataque vertical y las otras dos a las diagonales. Nada mas antiguo que \(D\) filas puede influir.
Tras colocar las primeras \(r\) filas, definimos \(\ell=\min(r,D)\). El futuro depende solo de la tupla
$$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1}).$$
Dos tableros parciales con la misma tupla \(\sigma_r\) son equivalentes para todas las elecciones futuras, porque cualquier reina mas antigua ya esta a mas de \(D\) filas de distancia y nunca volvera a atacar. Asi, la busqueda se convierte en una programacion dinamica sobre estados de historial reciente.
Supongamos que el estado actual es \(\sigma=(a_1,\dots,a_\ell)\), donde \(a_1\) es la columna mas reciente. El conjunto bloqueado para la fila siguiente es
$$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}.$$
Cualquier columna de \(\{0,1,\dots,n-1\}\setminus B(\sigma)\) es valida. Si elegimos una de ellas, la nueva tupla de historial reciente se obtiene colocando esa columna delante y descartando la entrada mas antigua cuando sea necesario.
Si \(F_r(\sigma)\) denota el numero de tableros parciales de altura \(r\) que llegan al estado \(\sigma\), entonces la capa siguiente se obtiene anadiendo \(F_r(\sigma)\) a cada sucesor legal de \(\sigma\).
Muchos tableros parciales distintos terminan en la misma tupla de historial reciente. Una vez generados los sucesores de la siguiente fila, las tuplas iguales se fusionan y sus multiplicidades se suman. Esta es la compresion clave del metodo.
La fusion es exacta porque el patron futuro de ataques queda determinado por completo por la tupla reciente; no se pierde informacion.
Cuando \(D=1\), cada fila solo interactua con la fila inmediatamente anterior, de modo que el estado es solo la ultima columna. Si la columna previa es \(0\), la siguiente fila solo puede usar \(2\) o \(3\). Si es \(1\), solo \(3\) es valida. Si es \(2\), solo \(0\). Si es \(3\), se permiten \(0\) o \(1\).
Partiendo de la primera fila, los recuentos de tableros parciales que terminan en las columnas \(0,1,2,3\) evolucionan como
$$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$$
Por tanto, \(N(4,1)=16\). El mismo esquema tambien da \(N(4,0)=4^4=256\), \(N(4,2)=2\) y \(N(4,3)=2\), asi que
$$S(4)=256+16+2+2=276.$$
Las implementaciones en C++, Python y Java utilizan exactamente esta programacion dinamica de memoria finita. Para un \(D\) fijo comienzan con el estado vacio y multiplicidad \(1\), avanzan fila por fila, reconstruyen las columnas bloqueadas a partir de las columnas recientes recordadas y enumeran cada columna siguiente que sea legal.
Las implementaciones compiladas guardan las columnas recordadas en una representacion entera compacta, usando cuatro bits por fila recordada, lo cual basta para el caso objetivo \(n=14\). Despues de cada fila, los estados sucesores generados se ordenan por su estado codificado y los estados iguales se fusionan sumando sus recuentos.
Una vez procesadas las \(n\) filas, se suman los recuentos de todos los estados supervivientes y asi se obtiene \(N(n,D)\). El procedimiento exterior repite esto para \(D=0,1,\dots,n-1\) y acumula los resultados. Como estas tareas de \(D\) fijo son independientes, las implementaciones compiladas las reparten entre varios hilos de trabajo. La implementacion en Python actua como una capa ligera sobre el mismo calculo compilado.
Para un \(D\) fijo, sea \(F_r\) el numero de estados fusionados despues de la fila \(r\), y \(G_r\) el numero de sucesores generados antes de fusionar en el paso siguiente. Construir el conjunto bloqueado para un estado padre inspecciona como maximo \(D\) reinas recordadas, asi que la fase de transicion cuesta \(O(F_rD+G_r)\). Luego las implementaciones ordenan los estados generados antes de fusionarlos, lo que anade \(O(G_r\log G_r)\).
En consecuencia, el tiempo total para un valor fijo de \(D\) es
$$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right),$$
y la memoria es \(O(\max_r G_r)\). Una cota grosera en el peor caso es exponencial en \(D\), porque puede haber hasta \(n^D\) estados de historial reciente. Aun asi, para la instancia requerida con \(n=14\), la fusion de estados mantiene la frontera en un tamano manejable para un calculo directo.
在一个 \(n\times n\) 的棋盘上，每一行恰好放置一个皇后。这里的皇后不是无限攻击：它只会在纵向和两条对角线方向上攻击距离自己不超过 \(D\) 行的位置，其中
$$D=n-1-w.$$
记 \(Q(n,w)\) 为弱度参数 \(w\) 下的合法摆放数量。为了书写和推导更自然，可以改用攻击深度 \(D\) 作为参数，定义
$$N(n,D)=Q(n,n-1-D).$$
那么题目要求的总量就是
$$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D).$$
两个边界情形可以帮助理解这个模型。当 \(D=0\) 时，任意皇后都无法攻击到别的行，因此每一行都可以自由选择 \(n\) 个列位置之一，于是 \(N(n,0)=n^n\)。当 \(D=n-1\) 时，任意两行之间都可能互相作用，这就退化成普通的 \(n\) 皇后问题。
核心观察是：如果某个皇后位于当前行上方超过 \(D\) 行的位置，那么它以后再也不会影响当前决策。于是，一个部分摆放是否会产生相同的未来，只取决于最近的 \(D\) 行放在了哪些列上。
与其直接对 \(w\) 求和，不如先解决固定攻击深度的计数问题 \(N(n,D)\)。这样做的好处是，约束条件本来就是按“行距是否不超过 \(D\)”来定义的，所以固定 \(D\) 后，状态转移会变得非常清晰。
当所有 \(N(n,D)\) 都分别算出之后，最终答案只需要再做一次外层求和：
$$S(n)=\sum_{D=0}^{n-1}N(n,D).$$
设第 \(r\) 行皇后所在的列为 \(c_r\in\{0,1,\dots,n-1\}\)。一枚已经放在第 \(r-d\) 行的皇后，只有在 \(1\le d\le D\) 时才会对第 \(r\) 行产生影响。此时它会禁掉三种可能：
$$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$$
当然前提是这些列号仍然落在棋盘范围内。第一项表示同列攻击，后两项表示两条对角线攻击。只要行距超过 \(D\)，这枚旧皇后就再也不需要考虑。
当前已经放好了前 \(r\) 行时，记 \(\ell=\min(r,D)\)。接下来的所有合法性判断，只依赖于最近的 \(\ell\) 个列位置：
$$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1}).$$
这一步是整个方法成立的原因。如果两个不同的部分棋盘有完全相同的 \(\sigma_r\)，那么它们在未来每一行面对的攻击模式也完全相同，因为更早的那些皇后已经远在 \(D\) 行之外，不会再产生任何新的限制。于是，原本巨大的搜索树可以压缩成“最近历史状态”上的动态规划。
设当前状态为 \(\sigma=(a_1,\dots,a_\ell)\)，其中 \(a_1\) 表示最近一行使用的列。下一行的禁用列集合为
$$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}.$$
于是，\(\{0,1,\dots,n-1\}\setminus B(\sigma)\) 中的每一列都是合法选择。若下一行选择列 \(c\)，那么新状态就是把 \(c\) 放到最前面，并在长度超过 \(D\) 时删掉最旧的一项。
如果 \(F_r(\sigma)\) 表示放完前 \(r\) 行后到达状态 \(\sigma\) 的部分摆放数量，那么转移到下一层时，只需把 \(F_r(\sigma)\) 加到 \(\sigma\) 的每一个合法后继状态上。
很多不同的早期摆放过程，走到某一行之后会拥有相同的最近 \(D\) 行列模式。一旦这一点发生，它们在未来就完全等价，没有必要再分开保存。因此，在生成出下一行的所有候选状态以后，可以把相同的状态合并起来，并把它们的方案数相加。
这个合并不会丢失任何信息，因为未来的攻击关系完全由保留下来的最近历史决定。这也是算法能够处理目标规模的关键压缩步骤。
当 \(D=1\) 时，每一行只会受到上一行的影响，所以状态只需要记录“上一行在哪一列”。如果上一行在列 \(0\)，那么下一行只能放在列 \(2\) 或 \(3\)。如果上一行在列 \(1\)，下一行只能放在列 \(3\)。如果上一行在列 \(2\)，下一行只能放在列 \(0\)。如果上一行在列 \(3\)，下一行可以放在列 \(0\) 或 \(1\)。
从第一行开始，末列分别为 \(0,1,2,3\) 的部分摆放数量按行演化如下：
$$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$$
因此 \(N(4,1)=16\)。同一套框架还给出 \(N(4,0)=4^4=256\)、\(N(4,2)=2\)、\(N(4,3)=2\)，于是
$$S(4)=256+16+2+2=276.$$
C++、Python 和 Java 实现都遵循上述有限记忆动态规划。对于固定的 \(D\)，它们从“空状态、计数为 \(1\)”开始，自上而下逐行处理，依据最近记住的列位置重建当前的禁用列集合，然后枚举所有合法的下一列。
编译型实现会把最近的列历史压缩编码到一个整数中。由于目标规模是 \(n=14\)，每个记忆的行位置用四位二进制就足够表示。每处理完一行，就把生成出来的后继状态按照编码后的状态值排序，并把相同状态的计数合并相加。
当 \(n\) 行全部处理完之后，把所有存活状态的计数加总，就得到这个固定 \(D\) 下的 \(N(n,D)\)。最外层再对 \(D=0,1,\dots,n-1\) 重复这一过程并累加结果。由于不同 \(D\) 的任务彼此独立，编译型实现会把这些任务分发给多个工作线程。Python 实现则作为一个很薄的前端，调用同一套编译后的核心计算。
对固定的 \(D\)，记 \(F_r\) 为处理完第 \(r\) 行后合并得到的状态数，记 \(G_r\) 为下一步在合并之前生成的后继状态数。对每个父状态，构造禁用集合需要扫描至多 \(D\) 个仍被记住的皇后，因此转移阶段的代价为 \(O(F_rD+G_r)\)。随后实现会先对生成的状态排序，再做合并，这一步再增加 \(O(G_r\log G_r)\) 的时间。
所以，对单个 \(D\) 而言，总时间复杂度可以写成
$$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right),$$
空间复杂度为 \(O(\max_r G_r)\)。从最粗略的最坏情形看，算法对 \(D\) 仍然是指数级的，因为最近历史状态最多可能达到 \(n^D\) 个。不过在题目要求的 \(n=14\) 情况下，大量状态会在每一层被合并，实际前沿规模仍然足够可控。
На доске \(n\times n\) нужно поставить ровно по одной ферзю в каждую строку. Ферзь атакует не бесконечно далеко: вертикальные и диагональные атаки действуют только на расстоянии не больше \(D\) строк, где
$$D=n-1-w.$$
Пусть \(Q(n,w)\) обозначает число допустимых расстановок для параметра слабости \(w\). Удобно переписать задачу через глубину атаки \(D\), введя
$$N(n,D)=Q(n,n-1-D).$$
Тогда искомая сумма равна
$$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D).$$
Крайние случаи хорошо показывают смысл модели. При \(D=0\) ни один ферзь не может дотянуться до другой строки, поэтому в каждой строке можно свободно выбрать любой из \(n\) столбцов и \(N(n,0)=n^n\). При \(D=n-1\) взаимодействовать может любая пара строк, и мы получаем обычную задачу о \(n\) ферзях.
Ключевое наблюдение состоит в том, что ферзь, стоящий более чем на \(D\) строк выше текущей, уже никогда не повлияет на будущие решения. Значит, частичная расстановка полностью определяется последними \(D\) выбранными столбцами.
Вместо прямого суммирования по \(w\) удобнее решать задачу для фиксированной глубины \(N(n,D)\). Это точно совпадает с реальным ограничением построчного построения: атаковать друг друга могут только строки на расстоянии не больше \(D\).
После того как все значения \(N(n,D)\) посчитаны независимо, окончательный ответ дает формула
$$S(n)=\sum_{D=0}^{n-1}N(n,D).$$
Пусть \(c_r\in\{0,1,\dots,n-1\}\) — столбец, выбранный в строке \(r\). Ферзь в строке \(r-d\) влияет на строку \(r\) только если \(1\le d\le D\). Тогда он запрещает три варианта:
$$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$$
при условии, что соответствующие столбцы остаются на доске. Первая возможность отвечает вертикальной атаке, а две другие — диагоналям. Более старые строки уже не важны.
После размещения первых \(r\) строк положим \(\ell=\min(r,D)\). Все будущее зависит только от кортежа
$$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1}).$$
Если две разные частичные доски имеют один и тот же кортеж \(\sigma_r\), то для всех будущих выборов они эквивалентны: любой еще более ранний ферзь находится уже дальше чем на \(D\) строк и больше никогда не сможет атаковать. Так полный перебор превращается в динамическое программирование по состояниям недавней истории.
Пусть текущее состояние равно \(\sigma=(a_1,\dots,a_\ell)\), где \(a_1\) — самый недавний столбец. Тогда множество запрещенных столбцов для следующей строки равно
$$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}.$$
Любой столбец из \(\{0,1,\dots,n-1\}\setminus B(\sigma)\) допустим. Если выбрать такой столбец \(c\), то новое состояние получается добавлением \(c\) в начало и удалением самого старого запомненного столбца, если длина стала больше \(D\).
Если \(F_r(\sigma)\) — число частичных расстановок высоты \(r\), приводящих к состоянию \(\sigma\), то на следующем слое величина \(F_r(\sigma)\) добавляется ко всем допустимым потомкам \(\sigma\).
Многие разные частичные расстановки приводят к одному и тому же кортежу последних столбцов. После генерации всех состояний следующей строки одинаковые кортежи можно объединить и сложить их кратности. Именно это сжатие делает алгоритм практичным.
Слияние абсолютно корректно, потому что весь будущий рисунок атак полностью определяется сохраненным кортежем недавней истории.
При \(D=1\) каждая строка взаимодействует только с непосредственно предыдущей строкой, поэтому состояние состоит лишь из последнего столбца. Если предыдущий столбец равен \(0\), то в следующей строке можно ставить ферзя только в \(2\) или \(3\). Если предыдущий столбец равен \(1\), разрешен только \(3\). Если он равен \(2\), разрешен только \(0\). Если он равен \(3\), разрешены \(0\) или \(1\).
Начиная с первой строки, количества частичных расстановок, заканчивающихся столбцами \(0,1,2,3\), развиваются так:
$$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$$
Следовательно, \(N(4,1)=16\). Та же схема дает \(N(4,0)=4^4=256\), \(N(4,2)=2\) и \(N(4,3)=2\), поэтому
$$S(4)=256+16+2+2=276.$$
Реализации на C++, Python и Java используют именно эту динамику с конечной памятью. Для фиксированного \(D\) они стартуют с пустого состояния кратности \(1\), затем обрабатывают строки сверху вниз, восстанавливают запрещенные столбцы по запомненным недавним столбцам и перебирают каждый допустимый следующий столбец.
Компилируемые реализации хранят недавнюю историю столбцов в компактном целочисленном кодировании, по четыре бита на каждую запомненную строку; для целевого случая \(n=14\) этого достаточно. После каждой строки порожденные состояния сортируются по закодированному ключу, а совпадающие состояния сливаются сложением их счетчиков.
После обработки всех \(n\) строк суммы по оставшимся состояниям дают \(N(n,D)\). Внешняя часть повторяет этот процесс для всех \(D=0,1,\dots,n-1\) и складывает результаты. Поскольку задачи для разных \(D\) независимы, компилируемые реализации распределяют их между рабочими потоками. Python-реализация выступает тонкой оболочкой над тем же скомпилированным вычислением.
Для фиксированного \(D\) обозначим через \(F_r\) число слитых состояний после строки \(r\), а через \(G_r\) — число порожденных потомков до слияния на следующем шаге. Построение множества запретов для одного родительского состояния просматривает не более \(D\) запомненных ферзей, поэтому фаза переходов стоит \(O(F_rD+G_r)\). Затем реализации сортируют порожденные состояния перед слиянием, что добавляет \(O(G_r\log G_r)\).
Итак, полное время для одного значения \(D\) равно
$$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right),$$
а память равна \(O(\max_r G_r)\). В грубой худшей оценке алгоритм экспоненциален по \(D\), поскольку состояний недавней истории может быть до \(n^D\). Однако для требуемого случая \(n=14\) слияние состояний достаточно сильно сжимает фронт, чтобы прямой расчет оставался выполнимым.
على لوحة \(n\times n\)، نضع وزيرة واحدة بالضبط في كل صف. الوزيرة هنا لا تهاجم إلى ما لا نهاية؛ فالهجوم الرأسي والقطري يمتدان فقط حتى مسافة \(D\) صفوف، حيث
$$D=n-1-w.$$
ولنرمز بـ \(Q(n,w)\) إلى عدد الترتيبات الصحيحة عند قيمة الضعف \(w\). ومن الأنسب إعادة كتابة المسألة بدلالة عمق الهجوم \(D\) عبر التعريف
$$N(n,D)=Q(n,n-1-D).$$
وعندئذ تصبح الكمية المطلوبة
$$S(n)=\sum_{w=0}^{n-1}Q(n,w)=\sum_{D=0}^{n-1}N(n,D).$$
الحالتان الطرفيتان توضحان الفكرة بسرعة. عندما يكون \(D=0\)، لا تستطيع أي وزيرة الوصول إلى صف آخر، لذلك يملك كل صف حرية اختيار أي واحد من الأعمدة \(n\)، ومن ثم \(N(n,0)=n^n\). وعندما يكون \(D=n-1\)، يمكن لأي زوج من الصفوف أن يتفاعل، فنعود إلى مسألة الملكات التقليدية.
الملاحظة الحاسمة هي أن أي وزيرة تقع أعلى الصف الحالي بأكثر من \(D\) صفوف لا يمكنها أن تؤثر في أي قرار لاحق. لذلك فإن أي ترتيب جزئي يمكن تلخيصه بالكامل بواسطة الأعمدة المختارة في آخر \(D\) صفوف فقط.
بدل أن نجمع مباشرة على \(w\)، نحل مسألة العد عند قيمة ثابتة لـ \(D\)، أي \(N(n,D)\). هذا يطابق القيد الحقيقي في البناء الصفّي، لأن الهجوم لا يحدث إلا بين صفين يفصل بينهما مسافة لا تتجاوز \(D\).
وبعد حساب جميع القيم \(N(n,D)\) على حدة، يكون الجواب النهائي هو
$$S(n)=\sum_{D=0}^{n-1}N(n,D).$$
ليكن \(c_r\in\{0,1,\dots,n-1\}\) هو العمود المختار في الصف \(r\). الوزيرة الموجودة في الصف \(r-d\) لا تؤثر في الصف \(r\) إلا إذا كان \(1\le d\le D\). في هذه الحالة تمنع ثلاثة احتمالات:
$$c_r=c_{r-d},\qquad c_r=c_{r-d}+d,\qquad c_r=c_{r-d}-d,$$
وذلك ما دامت هذه الأعمدة ضمن حدود اللوحة. الشرط الأول هو الهجوم الرأسي، والشرطان الآخران هما الهجومان القطريان. أما الصفوف الأقدم من ذلك فلا يبقى لها أي أثر.
بعد وضع أول \(r\) صفوف، نأخذ \(\ell=\min(r,D)\). كل ما يهم للمستقبل هو المتتالية
$$\sigma_r=(c_r,c_{r-1},\dots,c_{r-\ell+1}).$$
إذا كان لدينا ترتيبان جزئيان مختلفان لكنهما يملكان المتتالية نفسها \(\sigma_r\)، فهما متكافئان تماماً بالنسبة إلى جميع القرارات اللاحقة، لأن أي وزيرة أقدم من ذلك أصبحت أبعد من \(D\) صفوف ولن تتمكن من الهجوم مرة أخرى. بهذه الفكرة يتحول البحث الكامل إلى برمجة ديناميكية على حالات تمثل التاريخ القريب فقط.
لنفرض أن الحالة الحالية هي \(\sigma=(a_1,\dots,a_\ell)\)، حيث \(a_1\) هو أحدث عمود. مجموعة الأعمدة المحظورة في الصف التالي هي
$$B(\sigma)=\bigcup_{d=1}^{\ell}\left(\{a_d\}\cup\{a_d+d\}\cup\{a_d-d\}\right)\cap\{0,1,\dots,n-1\}.$$
كل عمود في \(\{0,1,\dots,n-1\}\setminus B(\sigma)\) هو اختيار قانوني. وعند اختيار عمود \(c\)، تتكون الحالة الجديدة بوضع \(c\) في البداية ثم حذف أقدم عمود محفوظ إذا تجاوز الطول قيمة \(D\).
وإذا رمزنا بـ \(F_r(\sigma)\) إلى عدد الترتيبات الجزئية ذات الارتفاع \(r\) التي تصل إلى الحالة \(\sigma\)، فإن الطبقة التالية تُبنى بإضافة \(F_r(\sigma)\) إلى كل تابع قانوني لهذه الحالة.
كثير من الترتيبات الجزئية المختلفة تنتهي إلى المتتالية نفسها من آخر \(D\) أعمدة. بعد توليد حالات الصف التالي، يمكن دمج الحالات المتطابقة وجمع عدد طرقها. هذه هي خطوة الضغط الأساسية التي تجعل الخوارزمية عملية.
هذا الدمج دقيق تماماً، لأن نمط الهجمات في المستقبل يتحدد بالكامل بواسطة التاريخ القريب المحفوظ، لذلك لا تضيع أي معلومة.
عندما يكون \(D=1\)، فإن كل صف يتفاعل فقط مع الصف السابق مباشرة، ولهذا تصبح الحالة مجرد العمود الأخير. إذا كان العمود السابق هو \(0\)، فالصف التالي لا يستطيع الاختيار إلا بين \(2\) و\(3\). وإذا كان العمود السابق هو \(1\)، فالاختيار الوحيد هو \(3\). وإذا كان \(2\)، فالاختيار الوحيد هو \(0\). وإذا كان \(3\)، فيجوز اختيار \(0\) أو \(1\).
ابتداءً من الصف الأول، تتطور أعداد الترتيبات الجزئية المنتهية بالأعمدة \(0,1,2,3\) كما يلي:
$$\begin{aligned} r=1&:\ (1,1,1,1), &&T_1=4,\\ r=2&:\ (2,1,1,2), &&T_2=6,\\ r=3&:\ (3,2,2,3), &&T_3=10,\\ r=4&:\ (5,3,3,5), &&T_4=16. \end{aligned}$$
إذن \(N(4,1)=16\). والإطار نفسه يعطي أيضاً \(N(4,0)=4^4=256\)، و\(N(4,2)=2\)، و\(N(4,3)=2\)، ومن ثم
$$S(4)=256+16+2+2=276.$$
تستخدم تطبيقات C++ وPython وJava هذه البرمجة الديناميكية ذات الذاكرة المحدودة نفسها. عند قيمة ثابتة لـ \(D\)، تبدأ من الحالة الفارغة ذات التعدد \(1\)، ثم تعالج الصفوف من الأعلى إلى الأسفل، وتعيد بناء الأعمدة المحظورة من الأعمدة الحديثة المحفوظة، وتعدد كل عمود تالٍ قانوني.
التطبيقات المترجمة تحفظ تاريخ الأعمدة الحديث داخل تمثيل عددي مضغوط، مع أربع بتات لكل صف محفوظ، وهذا يكفي للحالة الهدف \(n=14\). وبعد كل صف، ترتب الحالات الناتجة بحسب مفتاحها المشفر، ثم تدمج الحالات المتساوية بجمع أعدادها.
بعد معالجة جميع الصفوف \(n\)، يُجمع عدد الطرق في كل الحالات الباقية للحصول على \(N(n,D)\). ثم تكرر الطبقة الخارجية ذلك لكل \(D=0,1,\dots,n-1\) وتجمع النتائج. ولأن مسائل \(D\) المختلفة مستقلة تماماً، توزع التطبيقات المترجمة هذه الأعمال على عدة خيوط تنفيذ. أما تطبيق Python فيعمل كواجهة خفيفة فوق الحساب المترجم نفسه.
لثابت \(D\)، لنرمز بـ \(F_r\) إلى عدد الحالات بعد الدمج عقب الصف \(r\)، وبـ \(G_r\) إلى عدد الحالات المتولدة قبل الدمج في الخطوة التالية. بناء مجموعة المنع لحالة أب واحدة يتطلب فحص ما يصل إلى \(D\) وزيرات محفوظات، ولذلك تكلف مرحلة الانتقال \(O(F_rD+G_r)\). بعد ذلك ترتب التطبيقات الحالات المتولدة قبل دمجها، مما يضيف زمناً مقداره \(O(G_r\log G_r)\).
وبالتالي فإن الزمن الكلي لقيمة واحدة من \(D\) هو
$$O\left(\sum_{r=0}^{n-1}\left(F_rD+G_r\log G_r\right)\right),$$
بينما يساوي استهلاك الذاكرة \(O(\max_r G_r)\). وهناك حد خشن في أسوأ الأحوال يكون أسيّاً في \(D\)، لأن عدد حالات التاريخ القريب قد يصل إلى \(n^D\). ومع ذلك، في الحالة المطلوبة حيث \(n=14\)، يبقى الحجم العملي للجبهة قابلاً للإدارة بفضل الدمج القوي للحالات.