Each puzzle is a Kakuro grid whose clue sums are written with letters \(A,\dots,J\) instead of decimal digits. The same bijection between those ten letters and the ten digits \(0,\dots,9\) is used everywhere in the puzzle, so solving one grid means recovering a single global permutation of the digits. Every white cell contains a value from \(1\) to \(9\), digits may not repeat inside one horizontal or vertical run, and each run must add up to the number represented by its clue.
After a puzzle is solved, the digits assigned to \(A,B,\dots,J\) are concatenated in that order to form one encrypted 10-digit number. The Project Euler task asks for the sum of those encrypted values over the full dataset.
Let \(L_0,\dots,L_9\) denote the digits assigned to the ten letters. They satisfy
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$
For each white cell \(c\), introduce a cell variable \(x_c\in\{1,\dots,9\}\). If that cell is labelled by letter \(i\), then the cell and the letter must agree:
$$x_c=L_i.$$
This already yields useful pruning. Letters may use \(0\), but white cells may not, so every letter that appears in a white cell is immediately restricted to \(\{1,\dots,9\}\).
A Kakuro run is an ordered list \(R=(c_1,\dots,c_\ell)\) of consecutive white cells. For a run of length \(\ell\) and sum \(s\), the relevant object is the set
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$$
The order matters, because \((1,2,3)\) and \((3,2,1)\) fill different cells. The implementation therefore precomputes all ordered tuples for every \(\ell\le 9\) and every achievable sum \(s\le 45\). The total size of this library is
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$$
which is large enough to power strong propagation, but still a fixed constant for this problem.
If a clue contains one letter \(a\), its numeric value is simply
$$s=L_a.$$
If a clue contains two letters \(ab\), it is read as a decimal number:
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
Because a Kakuro run built from distinct digits \(1,\dots,9\) can never exceed \(45\), only clue sums in \([0,45]\) are relevant. That gives immediate pruning on clue letters before search. The solver also treats repeated two-letter clues such as \(aa\) correctly; in that case the sum has the form \(s=11L_a\).
During solving, each cell and each letter has a current domain \(D(\cdot)\). For a fixed run \(R=(c_1,\dots,c_\ell)\), one first computes the set of currently allowed sums. For a one-letter clue \(a\), this is
$$S_R=\{d\in D(a): 0\le d\le 9\}.$$
For a two-letter clue \(ab\), it is
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
A tuple \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) is feasible exactly when every coordinate matches the current domain of its cell:
$$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$$
Let \(\mathcal F_R\) be the set of all feasible tuples over all allowed sums. Then each cell can be pruned by projection:
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
If no feasible tuple survives, the current branch is inconsistent and can be abandoned immediately.
The same information is projected back to the clue letters. A one-letter clue keeps only digits that still occur as valid run sums. A two-letter clue keeps only digit pairs whose decimal value \(10u+v\) still occurs among feasible sums. This two-way filtering between clue digits and run digits is the main reason the search tree stays small.
The ten letters must form a permutation of \(0,\dots,9\). Instead of a heavy general matching algorithm, the implementation repeatedly applies two light but effective reductions.
First, if a letter is already fixed to one digit, that digit is removed from all other letter domains. Second, if a digit appears in only one remaining letter domain, that letter is forced to take it. In constraint-programming language these are singleton elimination and hidden-single detection for the global all-different condition.
Propagation often solves most of a puzzle by itself. When it does not, the solver chooses the unresolved variable with minimum remaining domain size, considering both letters and white cells, and branches on its candidate digits. After each tentative assignment, the full propagation cycle runs again. This is the standard minimum-remaining-values heuristic combined with depth-first search.
Once all letters are fixed, the encrypted value of one puzzle is
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$$
The required answer is the sum of \(E\) over all puzzles in the input.
The C++, Python, and Java implementations all follow the same pipeline. They parse one puzzle into white cells, letter-labelled white cells, and horizontal or vertical runs. Next they build the tuple tables \(\mathcal T_{\ell,s}\), initialize each letter with domain \(\{0,\dots,9\}\), and initialize each white cell with domain \(\{1,\dots,9\}\).
The propagation loop alternates between three ideas: linking letter domains to labelled cells, pruning the global letter permutation, and scanning each run against the precomputed tuple tables. If propagation no longer changes anything and the puzzle is still incomplete, the implementation branches on the smallest non-singleton domain and recurses. The three language versions differ only in syntax; algorithmically they are the same solver.
The worst-case complexity remains exponential, because Kakuro solving with a global digit substitution still requires backtracking in difficult cases. However, the expensive combinatorial structure is mostly front-loaded into a constant-size precomputation. For this problem the tuple library has fixed size \(986409\), so it does not grow with the number of puzzles.
If a run has length \(\ell\), one propagation pass examines at most the tuples attached to sums that are still allowed by its clue. A rough upper bound for one pass over that run is
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$$
The overall runtime is therefore dominated by the number of search nodes that survive propagation. In practice, tuple filtering, clue back-projection, all-different pruning, and MRV branching reduce that number sharply. Memory usage is linear in the current puzzle state plus the fixed tuple table.
Jedes Rätsel ist ein Kakuro-Gitter, in dem die Hinweis-Summen nicht direkt als Dezimalzahlen, sondern mit den Buchstaben \(A,\dots,J\) geschrieben werden. Dieselbe bijektive Zuordnung zwischen diesen zehn Buchstaben und den zehn Ziffern \(0,\dots,9\) gilt im gesamten Rätsel. Ein gelöstes Gitter liefert also eine einzige globale Permutation der Ziffern. Jede weiße Zelle enthält einen Wert aus \(1\) bis \(9\), innerhalb eines horizontalen oder vertikalen Laufs dürfen Ziffern nicht wiederholt werden, und jeder Lauf muss genau die durch den Hinweis kodierte Summe ergeben.
Nach dem Lösen werden die Ziffern der Buchstaben \(A,B,\dots,J\) in dieser Reihenfolge zu einer verschlüsselten 10-stelligen Zahl zusammengesetzt. Gesucht ist die Summe dieser Werte über alle Rätsel der Eingabe.
Seien \(L_0,\dots,L_9\) die Ziffern der zehn Buchstaben. Dann gilt
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ für } i\neq j.$$
Für jede weiße Zelle \(c\) führen wir zusätzlich eine Zellvariable \(x_c\in\{1,\dots,9\}\) ein. Ist die Zelle mit Buchstabe \(i\) markiert, so müssen Zelle und Buchstabe übereinstimmen:
$$x_c=L_i.$$
Daraus folgt sofort eine nützliche Asymmetrie: Buchstaben dürfen den Wert \(0\) annehmen, weiße Zellen jedoch nicht. Jeder Buchstabe, der in einer weißen Zelle auftaucht, wird deshalb sofort auf \(\{1,\dots,9\}\) eingeschränkt.
Ein Kakuro-Lauf ist eine geordnete Liste \(R=(c_1,\dots,c_\ell)\) benachbarter weißer Zellen. Für einen Lauf der Länge \(\ell\) und Summe \(s\) ist die zentrale Menge
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ für } u\neq v\right\}.$$
Die Reihenfolge zählt, denn \((1,2,3)\) und \((3,2,1)\) belegen unterschiedliche Zellen. Deshalb erzeugt die Implementierung alle geordneten Tupel für jedes \(\ell\le 9\) und jede erreichbare Summe \(s\le 45\) im Voraus. Der Gesamtumfang dieser Bibliothek beträgt
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$$
also genug für starke Propagation, aber weiterhin eine feste Konstante dieses Problems.
Besteht ein Hinweis aus einem Buchstaben \(a\), so ist sein Zahlenwert einfach
$$s=L_a.$$
Besteht er aus zwei Buchstaben \(ab\), wird er als Dezimalzahl gelesen:
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
Da ein Kakuro-Lauf mit verschiedenen Ziffern \(1,\dots,9\) niemals größer als \(45\) sein kann, bleiben nur Hinweise in \([0,45]\) relevant. Das schneidet die Domänen der Hinweis-Buchstaben schon vor der Suche deutlich ein. Auch doppelte Zweibuchstaben-Hinweise wie \(aa\) werden korrekt behandelt; dann hat die Summe die Form \(s=11L_a\).
Während des Lösens besitzt jede Zelle und jeder Buchstabe eine aktuelle Domäne \(D(\cdot)\). Für einen festen Lauf \(R=(c_1,\dots,c_\ell)\) wird zunächst die Menge der momentan möglichen Summen bestimmt. Für einen einbuchstabigen Hinweis \(a\) ist das
$$S_R=\{d\in D(a): 0\le d\le 9\}.$$
Für einen zweibuchstabigen Hinweis \(ab\) erhält man
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
Ein Tupel \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) ist genau dann zulässig, wenn jede Koordinate mit der aktuellen Zell-Domäne verträglich ist:
$$d_j\in D(c_j)\qquad\text{für alle }j=1,\dots,\ell.$$
Sei \(\mathcal F_R\) die Menge aller zulässigen Tupel über alle erlaubten Summen. Dann kann jede Zelle per Projektion beschnitten werden:
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
Bleibt kein zulässiges Tupel übrig, ist der aktuelle Suchzweig widersprüchlich und wird sofort verworfen.
Dieselbe Information wird zurück auf die Hinweis-Buchstaben projiziert. Ein einbuchstabiger Hinweis behält nur noch Ziffern, die tatsächlich als Laufsumme vorkommen. Ein zweibuchstabiger Hinweis behält nur noch Ziffernpaare, deren Dezimalwert \(10u+v\) unter den zulässigen Summen noch auftritt. Gerade diese wechselseitige Filterung zwischen Hinweis und Lauf macht den Suchbaum in der Praxis klein.
Die zehn Buchstaben müssen eine Permutation von \(0,\dots,9\) bilden. Anstelle eines schweren allgemeinen Matching-Algorithmus verwendet die Implementierung zwei leichte, aber wirksame Reduktionen in einer Schleife.
Erstens wird eine bereits festgelegte Ziffer aus allen anderen Buchstaben-Domänen entfernt. Zweitens wird ein Digit erzwungen, wenn es nur noch in genau einer Buchstaben-Domäne vorkommt. In der Sprache der Constraint-Programmierung sind das Singleton-Elimination und Hidden-Single-Erkennung für die globale All-Different-Bedingung.
Propagation allein löst oft schon den größten Teil eines Rätsels. Reicht das nicht, wählt der Solver die noch ungelöste Variable mit der kleinsten Restdomäne, wobei sowohl Buchstaben als auch weiße Zellen berücksichtigt werden, und verzweigt auf ihre Kandidaten. Nach jeder probeweisen Festlegung läuft der vollständige Propagationszyklus erneut. Das ist die klassische Minimum-Remaining-Values-Heuristik in Kombination mit Tiefensuche.
Sind alle Buchstaben festgelegt, lautet der verschlüsselte Wert eines Rätsels
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$$
Gesucht ist die Summe dieser Werte über alle Rätsel der Eingabe.
Die C++-, Python- und Java-Implementierungen benutzen dieselbe Pipeline. Zuerst wird jedes Rätsel in weiße Zellen, buchstabenmarkierte weiße Zellen und horizontale oder vertikale Läufe zerlegt. Danach werden die Tupel-Tabellen \(\mathcal T_{\ell,s}\) vorab erzeugt, jede Buchstaben-Domäne mit \(\{0,\dots,9\}\) initialisiert und jede weiße Zelle mit \(\{1,\dots,9\}\).
Die Propagationsschleife wechselt dann zwischen drei Ideen: Verknüpfung von Buchstaben- und Zell-Domänen, Ausdünnung der globalen Ziffernpermutation und Prüfung jedes Laufs gegen die vorberechneten Tupel-Tabellen. Wenn diese Schritte nichts mehr ändern und das Rätsel noch unvollständig ist, verzweigt die Implementierung auf der kleinsten Nicht-Singleton-Domäne und ruft sich rekursiv erneut auf. Zwischen den drei Sprachen unterscheidet sich nur die Syntax, nicht der Algorithmus.
Im Worst Case bleibt die Komplexität exponentiell, denn Kakuro mit globaler Ziffernsubstitution ist weiterhin ein Backtracking-Problem. Der teure kombinatorische Teil wird jedoch weitgehend in eine Vorberechnung fester Größe verschoben. Für dieses Problem umfasst die Tupel-Bibliothek genau \(986409\) Einträge und wächst daher nicht mit der Anzahl der Rätsel.
Hat ein Lauf die Länge \(\ell\), so untersucht ein Propagationsdurchlauf höchstens die Tupel zu den Summen, die durch den aktuellen Hinweis noch erlaubt sind. Eine grobe Schranke für einen Durchlauf über diesen Lauf ist
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$$
Die Gesamtlaufzeit wird also vor allem von der Zahl der Suchknoten bestimmt, die nach der Propagation noch übrig bleiben. In der Praxis drücken Tupel-Filterung, Rückprojektion auf Hinweise, All-Different-Reduktion und MRV-Verzweigung diese Zahl stark. Der Speicherbedarf ist linear im aktuellen Rätselzustand plus der festen Tupel-Tabelle.
Her bulmaca, toplam ipuçlarının doğrudan sayı olarak değil \(A,\dots,J\) harfleriyle yazıldığı bir Kakuro ızgarasıdır. Bu on harf ile \(0,\dots,9\) rakamları arasındaki birebir eşleme bulmacanın tamamında aynıdır; dolayısıyla tek bir ızgarayı çözmek, aslında on rakamın tek bir global permütasyonunu bulmak anlamına gelir. Her beyaz hücre \(1\) ile \(9\) arasında bir değer alır, aynı yatay ya da dikey koşu içinde rakam tekrarı yasaktır ve her koşunun toplamı kendi ipucunun temsil ettiği sayıya eşit olmalıdır.
Bulmaca çözüldükten sonra \(A,B,\dots,J\) harflerine karşılık gelen rakamlar bu sırayla birleştirilerek şifrelenmiş 10 basamaklı bir sayı elde edilir. İstenen sonuç, tüm veri kümesindeki bu değerlerin toplamıdır.
\(L_0,\dots,L_9\) ile on harfe atanan rakamları gösterelim. Şu koşullar geçerlidir:
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$
Her beyaz hücre \(c\) için ayrıca \(x_c\in\{1,\dots,9\}\) değişkenini tanımlayalım. Eğer o hücre \(i\) harfiyle etiketliyse, hücre ile harf aynı değeri taşımalıdır:
$$x_c=L_i.$$
Buradaki önemli asimetri şudur: harfler \(0\) alabilir, ama beyaz hücreler alamaz. Bu yüzden bir beyaz hücrede görünen her harf daha en başta \(\{1,\dots,9\}\) kümesine daralır.
Bir Kakuro koşusu, ardışık beyaz hücrelerden oluşan sıralı bir liste \(R=(c_1,\dots,c_\ell)\) olarak düşünülebilir. Uzunluğu \(\ell\), toplamı \(s\) olan bir koşu için temel nesne
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$$
Burada sıra önemlidir; çünkü \((1,2,3)\) ile \((3,2,1)\) farklı hücre yerleşimleridir. Bu nedenle uygulama, her \(\ell\le 9\) ve her erişilebilir \(s\le 45\) için tüm sıralı tuple'ları önceden üretir. Bu kütüphanenin toplam boyutu
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409$$
olur. Bu sayı güçlü yayılım için yeterince büyük, ama problem boyutundan bağımsız sabit bir maliyettir.
İpucu tek harften \(a\) oluşuyorsa sayısal değer doğrudan
$$s=L_a$$
şeklindedir. İpucu iki harften \(ab\) oluşuyorsa onluk sistemde yorumlanır:
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
\(1,\dots,9\) rakamlarının tekrarsız kullanıldığı bir Kakuro koşusu \(45\)'ten büyük olamayacağı için, sadece \([0,45]\) aralığındaki ipucu toplamları anlamlıdır. Bu da arama başlamadan önce ipucu harflerinde ciddi daralma sağlar. Uygulama ayrıca \(aa\) gibi tekrar eden iki harfli ipuçlarını da ayrı biçimde ele alır; böyle bir durumda toplam \(s=11L_a\) formundadır.
Çözüm sırasında her hücrenin ve her harfin güncel bir alanı \(D(\cdot)\) vardır. Sabit bir \(R=(c_1,\dots,c_\ell)\) koşusu için önce şu an izin verilen toplamlar kümesi hesaplanır. Tek harfli ipucu \(a\) için bu küme
$$S_R=\{d\in D(a): 0\le d\le 9\}$$
olur. Çift harfli ipucu \(ab\) için ise
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
Bir \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) tuple'ı ancak her koordinat ilgili hücrenin güncel alanıyla uyumluysa uygulanabilir:
$$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$$
Tüm izinli toplamlar üzerindeki uygulanabilir tuple'ların kümesine \(\mathcal F_R\) diyelim. O zaman her hücre alanı izdüşüm alınarak daraltılır:
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
Eğer hiçbir uygulanabilir tuple kalmazsa mevcut dal tutarsızdır ve hemen terk edilir.
Aynı bilgi ipucu harflerine de geri yansıtılır. Tek harfli ipucu, gerçekten geçerli koşu toplamı olarak kalan rakamları tutar. Çift harfli ipucu ise onluk değeri \(10u+v\) olan ve hâlâ uygulanabilir bir toplam üreten rakam çiftlerini korur. Arama ağacını pratikte küçülten ana unsur, ipuçları ile koşular arasındaki bu çift yönlü filtredir.
On harf, \(0,\dots,9\) rakamlarının bir permütasyonu olmalıdır. Uygulama bunu ağır bir eşleme algoritmasıyla değil, hafif ama etkili iki indirgeme kuralını tekrar tekrar uygulayarak kullanır.
Birinci kural, tek değere sabitlenmiş bir harfin rakamını diğer tüm harf alanlarından silmektir. İkinci kural ise bir rakam yalnızca tek bir harf alanında görünüyorsa o harfi zorunlu olarak o rakama atamaktır. Kısıt programlama terminolojisinde bunlar singleton yayılımı ve hidden-single yakalamasıdır.
Yayılım çoğu zaman bulmacanın büyük bölümünü tek başına çözer. Yetmediği anda çözücü, hem harfler hem de beyaz hücreler arasında kalan alanı en küçük olan değişkeni seçer ve aday rakamları üzerinde dallanır. Her deneme atamasından sonra tam yayılım döngüsü yeniden çalıştırılır. Bu, minimum remaining values sezgisinin derinlik öncelikli aramayla birleşmiş halidir.
Tüm harfler belirlendiğinde tek bulmacanın şifreli değeri
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}$$
olarak hesaplanır. İstenen sonuç, girişteki tüm bulmacalar için bu \(E\) değerlerinin toplamıdır.
C++, Python ve Java uygulamaları aynı çözüm hattını kullanır. Önce her bulmaca beyaz hücrelere, harf etiketli beyaz hücrelere ve yatay ya da dikey koşulara ayrıştırılır. Ardından \(\mathcal T_{\ell,s}\) tuple tabloları hazırlanır, her harf \(\{0,\dots,9\}\) alanıyla, her beyaz hücre ise \(\{1,\dots,9\}\) alanıyla başlatılır.
Yayılım döngüsü üç fikri sırayla uygular: harf alanları ile etiketli hücreleri eşitlemek, global harf permütasyonunu budamak ve her koşuyu önceden üretilmiş tuple tablolarına karşı taramak. Bu adımlar artık değişiklik üretmiyorsa ve bulmaca hâlâ tamamlanmadıysa, uygulama en küçük tek olmayan alan üzerinde dallanır ve özyinelemeli olarak devam eder. Üç dildeki sürümler sözdizimi dışında aynı algoritmayı uygular.
En kötü durumda karmaşıklık üsteldir; çünkü global rakam eşlemeli Kakuro çözümü zor örneklerde geri izleme gerektirir. Buna rağmen pahalı kombinatorik yapı büyük ölçüde sabit boyutlu bir önhesaba taşınmıştır. Bu problem için tuple kütüphanesi tam olarak \(986409\) öğedir ve bulmaca sayısıyla büyümez.
Uzunluğu \(\ell\) olan bir koşuda tek bir yayılım geçişi, ipucunun şu anda izin verdiği toplamlarla ilişkili tuple'ları inceler. Bu geçiş için kaba üst sınır
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right)$$
şeklindedir. Dolayısıyla toplam çalışma süresini belirleyen asıl etken, yayılım sonrasında hayatta kalan arama düğümlerinin sayısıdır. Pratikte tuple filtreleme, ipucuna geri izdüşüm, all-different budaması ve MRV dallanması bu sayıyı ciddi biçimde düşürür. Bellek kullanımı, mevcut bulmaca durumu artı sabit tuple tablosu kadardır.
Cada rompecabezas es una cuadrícula de Kakuro en la que las sumas de las pistas no aparecen como números decimales directos, sino mediante las letras \(A,\dots,J\). La misma biyección entre esas diez letras y los diez dígitos \(0,\dots,9\) se usa en toda la cuadrícula, así que resolver un tablero equivale a recuperar una sola permutación global de los dígitos. Cada celda blanca contiene un valor entre \(1\) y \(9\), dentro de una misma corrida horizontal o vertical no se permiten repeticiones y la suma de la corrida debe coincidir exactamente con el valor representado por su pista.
Cuando una cuadrícula queda resuelta, los dígitos asignados a \(A,B,\dots,J\) se concatenan en ese orden para formar un número cifrado de 10 cifras. La tarea final es sumar esos valores sobre todo el conjunto de entrada.
Sea \(L_0,\dots,L_9\) el conjunto de dígitos asignados a las diez letras. Deben cumplir
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$
Para cada celda blanca \(c\), introducimos además una variable \(x_c\in\{1,\dots,9\}\). Si la celda está etiquetada con la letra \(i\), entonces ambas variables deben coincidir:
$$x_c=L_i.$$
Esto ya produce una poda importante. Las letras sí pueden tomar el valor \(0\), pero las celdas blancas no; por lo tanto, toda letra que aparezca dentro de una celda blanca queda restringida inmediatamente a \(\{1,\dots,9\}\).
Una corrida de Kakuro es una lista ordenada \(R=(c_1,\dots,c_\ell)\) de celdas blancas consecutivas. Para una corrida de longitud \(\ell\) y suma \(s\), el objeto central es
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$$
El orden importa, porque \((1,2,3)\) y \((3,2,1)\) corresponden a asignaciones distintas sobre las celdas. Por eso la implementación precalcula todas las tuplas ordenadas para cada \(\ell\le 9\) y cada suma alcanzable \(s\le 45\). El tamaño total de esa biblioteca es
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$$
lo bastante grande como para ofrecer una propagación fuerte, pero todavía una constante fija del problema.
Si una pista contiene una sola letra \(a\), su valor numérico es
$$s=L_a.$$
Si contiene dos letras \(ab\), se interpreta como un número decimal:
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
Como una corrida de Kakuro formada por dígitos distintos de \(1\) a \(9\) nunca puede superar \(45\), sólo interesan las pistas dentro de \([0,45]\). Eso ya recorta bastante los dominios de las letras de pista antes de empezar la búsqueda. La implementación también trata correctamente las pistas repetidas del tipo \(aa\); en ese caso la suma tiene la forma \(s=11L_a\).
Durante la resolución, cada celda y cada letra tienen un dominio actual \(D(\cdot)\). Para una corrida fija \(R=(c_1,\dots,c_\ell)\), primero se calcula el conjunto de sumas todavía permitidas. Para una pista de una letra \(a\), ese conjunto es
$$S_R=\{d\in D(a): 0\le d\le 9\}.$$
Para una pista de dos letras \(ab\), se usa
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
Una tupla \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) es factible exactamente cuando cada coordenada encaja en el dominio actual de su celda correspondiente:
$$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$$
Sea \(\mathcal F_R\) el conjunto de todas las tuplas factibles sobre todas las sumas permitidas. Entonces cada dominio de celda se puede reducir por proyección:
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
Si no sobrevive ninguna tupla factible, la rama actual es inconsistente y se descarta inmediatamente.
La misma información se proyecta de vuelta a las letras de la pista. Una pista de una letra conserva sólo los dígitos que siguen apareciendo como suma válida. Una pista de dos letras conserva sólo los pares de dígitos cuyo valor decimal \(10u+v\) sigue apareciendo entre las sumas factibles. Este filtrado bidireccional entre pistas y corridas es la razón principal por la que el árbol de búsqueda permanece pequeño.
Las diez letras deben formar una permutación de \(0,\dots,9\). En lugar de usar un algoritmo general de emparejamiento más pesado, la implementación repite dos reducciones sencillas pero efectivas.
Primero, si una letra ya quedó fijada a un único dígito, ese dígito se elimina de todos los demás dominios de letras. Segundo, si un dígito aparece en un solo dominio restante, esa letra queda forzada a tomarlo. En términos de programación por restricciones, esto corresponde a propagación de singletons y detección de hidden singles sobre la restricción global all-different.
La propagación sola suele resolver gran parte del tablero. Cuando no basta, el solucionador elige la variable no resuelta con el dominio restante más pequeño, considerando tanto letras como celdas blancas, y ramifica sobre sus candidatos. Después de cada asignación tentativa, vuelve a ejecutar todo el ciclo de propagación. Es la heurística clásica de minimum remaining values combinada con búsqueda en profundidad.
Una vez fijadas todas las letras, el valor cifrado de una cuadrícula es
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$$
La respuesta pedida es la suma de \(E\) sobre todos los rompecabezas de la entrada.
Las implementaciones en C++, Python y Java siguen exactamente la misma estructura. Primero descomponen cada rompecabezas en celdas blancas, celdas blancas etiquetadas con letras y corridas horizontales o verticales. Después construyen las tablas de tuplas \(\mathcal T_{\ell,s}\), inicializan cada letra con el dominio \(\{0,\dots,9\}\) e inicializan cada celda blanca con el dominio \(\{1,\dots,9\}\).
El bucle de propagación alterna entre tres ideas: enlazar dominios de letras con celdas etiquetadas, podar la permutación global de letras y revisar cada corrida contra las tablas precalculadas. Si la propagación ya no cambia nada y el tablero sigue incompleto, la implementación ramifica sobre el dominio no singleton más pequeño y continúa recursivamente. Las tres versiones cambian sólo de sintaxis; el algoritmo es el mismo.
En el peor caso, la complejidad sigue siendo exponencial, porque resolver Kakuro con una sustitución global de dígitos todavía requiere backtracking en instancias difíciles. Sin embargo, la parte combinatoria más costosa se desplaza casi por completo a una precalculación de tamaño constante. Para este problema, la biblioteca de tuplas tiene tamaño fijo \(986409\), de modo que no crece con el número de rompecabezas.
Si una corrida tiene longitud \(\ell\), una pasada de propagación examina como máximo las tuplas asociadas a las sumas que su pista todavía permite. Una cota superior razonable para una pasada sobre esa corrida es
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$$
Por lo tanto, el tiempo total queda dominado por el número de nodos de búsqueda que sobreviven a la propagación. En la práctica, el filtrado por tuplas, la retroproyección hacia las pistas, la poda all-different y la heurística MRV reducen mucho ese número. La memoria usada es lineal en el estado actual del rompecabezas más la tabla fija de tuplas.
每个谜题都是一个 Kakuro 网格，只不过题目中的提示和不是直接写成十进制数字，而是写成字母 \(A,\dots,J\)。这十个字母与 \(0,\dots,9\) 之间存在同一个全局双射，因此解出一张网格，本质上就是恢复十个数字的一次全排列。每个白格都必须填入 \(1\) 到 \(9\) 之间的数字，同一条横向或纵向连续段内数字不能重复，而且该连续段的数字和必须等于提示字母所代表的数值。
当一张网格被完全解出后，把 \(A,B,\dots,J\) 对应的数字按顺序拼接，就得到一个 10 位加密数。最终要求的是所有谜题对应加密数之和。
设 \(L_0,\dots,L_9\) 表示十个字母对应的数字，则有
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$
对每一个白格 \(c\)，再引入格子变量 \(x_c\in\{1,\dots,9\}\)。如果该白格标记的是字母 \(i\)，那么格子值必须与字母值一致：
$$x_c=L_i.$$
这里有一个很重要的不对称性：字母可以取 \(0\)，白格不能取 \(0\)。因此，只要某个字母出现在白格中，它的定义域就会立刻缩小到 \(\{1,\dots,9\}\)。
一条 Kakuro 连续段可以表示为相邻白格组成的有序列表 \(R=(c_1,\dots,c_\ell)\)。对于长度为 \(\ell\)、目标和为 \(s\) 的连续段，核心对象是
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$$
这里必须保留顺序，因为 \((1,2,3)\) 和 \((3,2,1)\) 虽然数字集合相同，但对应到格子上的赋值不同。因此实现会预先生成所有 \(\ell\le 9\) 和所有可达和 \(s\le 45\) 的有序元组。这个元组库的总规模为
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$$
足以支持很强的剪枝，同时又是这个问题的固定常数开销。
如果提示只有一个字母 \(a\)，那么它表示的和就是
$$s=L_a.$$
如果提示由两个字母 \(ab\) 组成，则按十进制解释：
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
由于由互不相同的 \(1,\dots,9\) 组成的一条 Kakuro 连续段，其和不可能超过 \(45\)，所以只有 \([0,45]\) 范围内的提示值才有意义。这一点在搜索前就能直接裁剪提示字母的定义域。实现还专门处理了 \(aa\) 这类重复两字母提示，此时和满足 \(s=11L_a\)。
求解过程中，每个格子和每个字母都有当前定义域 \(D(\cdot)\)。对于固定连续段 \(R=(c_1,\dots,c_\ell)\)，先求当前仍可能的和的集合。若提示为单字母 \(a\)，则
$$S_R=\{d\in D(a): 0\le d\le 9\}.$$
若提示为双字母 \(ab\)，则
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
当且仅当每个坐标都落在对应格子的当前定义域中时，\((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) 才是可行元组：
$$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$$
记所有允许和上的可行元组集合为 \(\mathcal F_R\)。那么第 \(j\) 个格子的定义域可以通过投影收缩为
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
如果一个可行元组都不存在，那么当前搜索分支立即矛盾，可以直接回溯。
同样的信息还会反向投影到提示字母。单字母提示只保留那些仍能作为合法连续段和出现的数字；双字母提示只保留那些十进制值 \(10u+v\) 仍出现在可行和中的数字对。正是这种从提示到连续段、再从连续段回到提示的双向过滤，使得搜索树在实践中很小。
十个字母必须构成 \(0,\dots,9\) 的一个排列。实现没有使用更重的通用匹配算法，而是反复执行两条简单但有效的规则。
第一条是：如果某个字母已经被确定为唯一数字，那么这个数字从其他所有字母定义域中删除。第二条是：如果某个数字只出现在一个剩余字母定义域里，那么该字母就被迫取这个数字。在约束程序设计语言里，这对应于 singleton 传播和 hidden single 检测。
仅靠传播通常就能解决谜题的大部分内容。如果还不能完成，求解器就会在字母变量和白格变量中选择当前定义域最小的那个，并对其候选数字逐一分支。每做一次试探赋值，完整的传播循环都会重新执行。这就是 minimum remaining values 启发式与深度优先搜索的结合。
当所有字母都被确定后，一张谜题的加密值为
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$$
题目要求的就是输入中所有谜题对应 \(E\) 的总和。
C++、Python 和 Java 三个实现遵循完全相同的流程。它们先把每个谜题解析成白格、带字母的白格，以及横向或纵向连续段；然后预计算 \(\mathcal T_{\ell,s}\) 元组表，把每个字母的初始定义域设为 \(\{0,\dots,9\}\)，把每个白格的初始定义域设为 \(\{1,\dots,9\}\)。
传播循环依次做三件事：把字母定义域与对应白格链接起来，裁剪全局字母排列，再利用预计算元组表扫描每一条连续段。如果这些步骤已经不再产生变化，而谜题仍未完全确定，那么实现就对最小的非单元素定义域进行分支并递归继续。三种语言版本只有语法不同，算法行为完全一致。
最坏情况下，复杂度仍然是指数级，因为带有全局数字替换的 Kakuro 在困难实例上仍需要回溯搜索。不过最昂贵的组合结构已经基本被前移到了一个固定大小的预计算阶段。对本题而言，元组库大小固定为 \(986409\)，不会随着谜题数量增长。
若某条连续段长度为 \(\ell\)，一次传播最多会检查该提示当前仍允许的和所对应的元组。因此，对这条连续段的一次传播可以粗略写成
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$$
整体运行时间最终由传播后仍然存活的搜索节点数量主导。在实际数据上，元组过滤、对提示的反向投影、all-different 剪枝以及 MRV 分支共同把这个数量压得很低。内存消耗则是当前谜题状态的线性规模，再加上固定的元组表。
Каждая головоломка представляет собой сетку Kakuro, где суммы в подсказках записаны не обычными десятичными числами, а буквами \(A,\dots,J\). Одна и та же биекция между этими десятью буквами и цифрами \(0,\dots,9\) действует во всей сетке, поэтому решение одной головоломки фактически означает восстановление единственной глобальной перестановки десяти цифр. Каждая белая клетка содержит число от \(1\) до \(9\), внутри одного горизонтального или вертикального пробега повторения запрещены, а сумма в пробеге должна совпадать со значением, заданным его буквенной подсказкой.
После решения цифры, соответствующие \(A,B,\dots,J\), конкатенируются в этом порядке и образуют зашифрованное 10-значное число. Требуется просуммировать такие значения по всему входному набору.
Обозначим через \(L_0,\dots,L_9\) цифры, присвоенные десяти буквам. Тогда
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$
Для каждой белой клетки \(c\) введем клеточную переменную \(x_c\in\{1,\dots,9\}\). Если клетка помечена буквой \(i\), то значение клетки и значение буквы должны совпадать:
$$x_c=L_i.$$
Здесь сразу возникает полезная асимметрия: буквы могут принимать \(0\), а белые клетки не могут. Следовательно, любая буква, встречающаяся в белой клетке, немедленно ограничивается множеством \(\{1,\dots,9\}\).
Пробег Kakuro удобно рассматривать как упорядоченный список соседних белых клеток \(R=(c_1,\dots,c_\ell)\). Для пробега длины \(\ell\) и суммы \(s\) ключевым объектом является множество
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$$
Порядок важен: \((1,2,3)\) и \((3,2,1)\) дают разные заполнения клеток. Поэтому реализация заранее генерирует все упорядоченные кортежи для каждого \(\ell\le 9\) и каждой достижимой суммы \(s\le 45\). Полный размер этой библиотеки равен
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$$
что достаточно для сильной пропагации и при этом остается фиксированной константой задачи.
Если подсказка состоит из одной буквы \(a\), то ее числовое значение равно
$$s=L_a.$$
Если подсказка состоит из двух букв \(ab\), она читается как десятичное число:
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
Поскольку сумма пробега из различных цифр \(1,\dots,9\) не может превосходить \(45\), имеют смысл только значения подсказок из интервала \([0,45]\). Это дает заметную предварительную отсечку доменов букв еще до поиска. Реализация также корректно обрабатывает повторяющиеся двубуквенные подсказки вроде \(aa\); тогда сумма имеет вид \(s=11L_a\).
Во время решения у каждой клетки и у каждой буквы есть текущий домен \(D(\cdot)\). Для фиксированного пробега \(R=(c_1,\dots,c_\ell)\) сначала строится множество сумм, которые еще разрешены. Для однобуквенной подсказки \(a\) это
$$S_R=\{d\in D(a): 0\le d\le 9\}.$$
Для двубуквенной подсказки \(ab\) получаем
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
Кортеж \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) считается допустимым тогда и только тогда, когда каждая его координата согласована с текущим доменом соответствующей клетки:
$$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$$
Обозначим через \(\mathcal F_R\) множество всех допустимых кортежей по всем разрешенным суммам. Тогда домен каждой клетки сужается проекцией:
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
Если не остается ни одного допустимого кортежа, текущая ветвь противоречива и сразу отбрасывается.
Та же информация проектируется обратно на буквы подсказки. Однобуквенная подсказка сохраняет только те цифры, которые еще возникают как допустимая сумма пробега. Двубуквенная подсказка сохраняет только те пары цифр, для которых десятичное значение \(10u+v\) по-прежнему встречается среди допустимых сумм. Именно эта двусторонняя фильтрация между подсказкой и пробегом резко уменьшает дерево поиска.
Десять букв должны образовывать перестановку множества \(0,\dots,9\). Вместо тяжелого общего алгоритма сопоставления реализация многократно применяет две простые, но эффективные редукции.
Во-первых, если буква уже зафиксирована в одном значении, эта цифра удаляется из доменов всех остальных букв. Во-вторых, если какая-то цифра встречается только в одном оставшемся домене буквы, то эта буква обязана принять ее. В терминах constraint programming это singleton propagation и hidden-single detection для глобального ограничения all-different.
Одна только пропагация часто решает большую часть головоломки. Если этого недостаточно, решатель выбирает неразрешенную переменную с минимальным текущим доменом, рассматривая и буквы, и белые клетки, после чего ветвится по ее кандидатам. После каждого пробного присваивания полный цикл пропагации выполняется заново. Это классическая эвристика minimum remaining values в сочетании с поиском в глубину.
Когда все буквы зафиксированы, зашифрованное значение одной головоломки равно
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$$
Требуемый ответ есть сумма \(E\) по всем головоломкам входа.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала каждая головоломка разбирается на белые клетки, белые клетки с буквенными метками и горизонтальные или вертикальные пробеги. Затем заранее строятся таблицы кортежей \(\mathcal T_{\ell,s}\), для каждой буквы задается начальный домен \(\{0,\dots,9\}\), а для каждой белой клетки задается \(\{1,\dots,9\}\).
Далее цикл пропагации чередует три идеи: связывание доменов букв с помеченными клетками, отсечение глобальной перестановки букв и проверку каждого пробега по заранее вычисленным таблицам. Если изменения больше не происходят, а головоломка еще не завершена, реализация ветвится по наименьшему нетривиальному домену и рекурсивно продолжает поиск. Различия между тремя языками только синтаксические; сам алгоритм одинаков.
В худшем случае сложность остается экспоненциальной, поскольку Kakuro с глобальной подстановкой цифр все равно сводится к задаче с возвратом назад. Однако основная комбинаторная нагрузка почти полностью вынесена в предвычисление фиксированного размера. Для этой задачи библиотека кортежей содержит ровно \(986409\) элементов и не растет с числом головоломок.
Если длина пробега равна \(\ell\), то один проход пропагации просматривает не более тех кортежей, которые соответствуют суммам, еще разрешенным текущей подсказкой. Грубая оценка стоимости такого прохода имеет вид
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$$
Следовательно, общее время в основном определяется количеством узлов поиска, переживших пропагацию. На практике фильтрация по кортежам, обратная проекция на подсказки, отсечка all-different и ветвление MRV сильно уменьшают это число. Память расходуется линейно по текущему состоянию головоломки плюс фиксированная таблица кортежей.
كل لغز هو شبكة Kakuro، لكن مجاميع التلميحات لا تُكتب كأعداد عشرية مباشرة، بل بالحروف \(A,\dots,J\). وتبقى المطابقة نفسها بين هذه الحروف العشرة والأرقام \(0,\dots,9\) ثابتة في كامل الشبكة، لذلك فإن حل شبكة واحدة يعني في الحقيقة استرجاع تبديلة عالمية واحدة للأرقام العشرة. كل خلية بيضاء تأخذ قيمة من \(1\) إلى \(9\)، ولا يسمح بتكرار الأرقام داخل المسار الأفقي أو العمودي الواحد، ويجب أن يساوي مجموع خلايا المسار القيمة التي يمثلها تلميحه.
بعد حل اللغز، تُجمع الأرقام المناظرة لـ \(A,B,\dots,J\) بهذا الترتيب لتكوين عدد مشفر من 10 خانات. والمطلوب في النهاية هو جمع هذه القيم على كامل مجموعة الألغاز.
لنرمز إلى الأرقام المسندة إلى الحروف العشرة بـ \(L_0,\dots,L_9\). عندئذ يتحقق الشرط
$$L_i\in\{0,\dots,9\},\qquad L_i\neq L_j \text{ for } i\neq j.$$
ولكل خلية بيضاء \(c\) نعرف متغير خلية \(x_c\in\{1,\dots,9\}\). وإذا كانت هذه الخلية موسومة بالحرف \(i\)، فيجب أن تتطابق قيمة الخلية مع قيمة الحرف:
$$x_c=L_i.$$
وهنا تظهر لا تماثلية مهمة: الحروف يمكن أن تأخذ \(0\)، أما الخلايا البيضاء فلا يمكنها ذلك. لذلك فإن أي حرف يظهر داخل خلية بيضاء يُقيد مباشرة إلى \(\{1,\dots,9\}\).
يمكن تمثيل مسار Kakuro على أنه قائمة مرتبة من الخلايا البيضاء المتجاورة \(R=(c_1,\dots,c_\ell)\). وإذا كان طول المسار \(\ell\) ومجموعه \(s\)، فالمجموعة الأساسية هي
$$\mathcal T_{\ell,s}=\left\{(d_1,\dots,d_\ell)\in\{1,\dots,9\}^\ell:\sum_{j=1}^{\ell} d_j=s,\ d_u\neq d_v \text{ for } u\neq v\right\}.$$
الترتيب هنا مهم، لأن \((1,2,3)\) و\((3,2,1)\) يعطيان تعبئتين مختلفتين للخلايا. ولهذا تُحسب جميع الرتب المرتبة مسبقاً لكل \(\ell\le 9\) ولكل مجموع ممكن \(s\le 45\). ويبلغ الحجم الكلي لهذه المكتبة
$$\sum_{\ell=1}^{9}\frac{9!}{(9-\ell)!}=986409,$$
وهو حجم كافٍ لإعطاء تقليم قوي، لكنه يبقى ثابتاً بالنسبة إلى هذه المسألة.
إذا كان التلميح مكوناً من حرف واحد \(a\)، فإن قيمته العددية هي ببساطة
$$s=L_a.$$
أما إذا كان مكوناً من حرفين \(ab\)، فإنه يُقرأ كعدد عشري:
$$s=10L_a+L_b,\qquad L_a\neq 0.$$
وبما أن مجموع مسار Kakuro المؤلف من أرقام مختلفة من \(1\) إلى \(9\) لا يمكن أن يتجاوز \(45\)، فلا يبقى مهماً إلا ما يقع داخل المجال \([0,45]\). وهذا يزيل كثيراً من القيم المستحيلة من مجالات حروف التلميحات قبل بدء البحث. كما أن التنفيذ يتعامل أيضاً مع التلميحات المكررة من الشكل \(aa\)، حيث يصبح المجموع من الصورة \(s=11L_a\).
أثناء الحل، لكل خلية ولكل حرف مجال حالي \(D(\cdot)\). لمسار ثابت \(R=(c_1,\dots,c_\ell)\)، نحسب أولاً مجموعة المجاميع التي ما زالت ممكنة. إذا كان التلميح من حرف واحد \(a\)، فإن
$$S_R=\{d\in D(a): 0\le d\le 9\}.$$
وإذا كان التلميح من حرفين \(ab\)، فإن
$$S_R=\{10u+v:\ u\in D(a),\ v\in D(b),\ 10u+v\le 45\}.$$
وتكون الرتبة \((d_1,\dots,d_\ell)\in \mathcal T_{\ell,s}\) ممكنة فقط إذا كانت كل قيمة فيها متوافقة مع المجال الحالي لخلية موضعها:
$$d_j\in D(c_j)\qquad\text{for all }j=1,\dots,\ell.$$
ولنرمز إلى جميع الرتب الممكنة عبر كل المجاميع المسموح بها بالرمز \(\mathcal F_R\). عندئذ يمكن تقليص مجال كل خلية بالإسقاط:
$$D(c_j)\leftarrow D(c_j)\cap \{d_j:(d_1,\dots,d_\ell)\in \mathcal F_R\}.$$
فإذا لم تبق أي رتبة ممكنة، كانت هذه الفرع من البحث متناقضاً ويُرفض فوراً.
وتُسقط المعلومات نفسها مرة أخرى على حروف التلميح. فالتلميح ذو الحرف الواحد يحتفظ فقط بالأرقام التي ما زالت تظهر كمجموع صالح للمسار، أما التلميح ذو الحرفين فيحتفظ فقط بأزواج الأرقام التي تبقى قيمتها العشرية \(10u+v\) ضمن المجاميع الممكنة. هذا الترشيح ثنائي الاتجاه بين أرقام التلميح وأرقام المسار هو السبب الرئيسي في بقاء شجرة البحث صغيرة عملياً.
يجب أن تشكل الحروف العشرة تبديلة للمجموعة \(0,\dots,9\). وبدلاً من استخدام خوارزمية مطابقة عامة أثقل، يطبق التنفيذ قاعدتين بسيطتين لكنهما فعالتان بشكل متكرر.
القاعدة الأولى هي: إذا ثبت حرف على رقم واحد، فإن هذا الرقم يُحذف من مجالات بقية الحروف. والقاعدة الثانية هي: إذا ظهر رقم ما في مجال حرف واحد فقط، فإن ذلك الحرف يُجبر على أخذه. في لغة البرمجة بالقيود، يمثل هذا نشر القيم المفردة واكتشاف القيمة المخفية الوحيدة داخل القيد العالمي all-different.
في كثير من الأحيان تكفي عملية النشر وحدها لحل جزء كبير من اللغز. وإذا لم تكفِ، يختار المحلل المتغير غير المحسوم ذي أصغر مجال متبق، سواء كان حرفاً أو خلية بيضاء، ثم يتفرع على قيمه المرشحة. وبعد كل تعيين تجريبي، تُعاد دورة النشر الكاملة من جديد. وهذا هو أسلوب minimum remaining values مع البحث بالعمق أولاً.
بعد تثبيت جميع الحروف، تكون القيمة المشفرة للغز الواحد
$$E=\sum_{i=0}^{9} L_i\,10^{9-i}.$$
والجواب المطلوب هو مجموع هذه القيم على جميع الألغاز في الإدخال.
تتبع تطبيقات C++ وPython وJava خط العمل نفسه تماماً. فهي تفكك كل لغز إلى خلايا بيضاء، وخلايا بيضاء موسومة بحروف، ومسارات أفقية أو عمودية. بعد ذلك تُبنى جداول الرتب \(\mathcal T_{\ell,s}\) مسبقاً، ويُهيأ مجال كل حرف بالقيم \(\{0,\dots,9\}\)، بينما يُهيأ مجال كل خلية بيضاء بالقيم \(\{1,\dots,9\}\).
ثم تتناوب حلقة النشر بين ثلاث أفكار: ربط مجالات الحروف بالخلايا الموسومة، وتقليص التبديلة العالمية للحروف، وفحص كل مسار مقابل جداول الرتب المحسوبة مسبقاً. وإذا توقفت هذه الخطوات عن إحداث أي تغيير وبقي اللغز غير مكتمل، يتفرع التنفيذ على أصغر مجال غير أحادي ويتابع بصورة تراجعية. الاختلاف بين اللغات الثلاث نحوي فقط، أما الخوارزمية فهي نفسها.
يبقى التعقيد في أسوأ الحالات أسيّاً، لأن حل Kakuro مع استبدال عالمي للأرقام ما زال يتطلب بحثاً رجعياً في الحالات الصعبة. لكن البنية التوافقية المكلفة نُقلت تقريباً بالكامل إلى مرحلة تمهيدية ثابتة الحجم. ففي هذه المسألة يبلغ حجم مكتبة الرتب \(986409\) ولا ينمو مع عدد الألغاز.
إذا كان طول المسار \(\ell\)، فإن مرور نشر واحد يفحص على الأكثر الرتب المرتبطة بالمجاميع التي ما زال التلميح يسمح بها. ويمكن كتابة حد علوي تقريبي لهذا المرور على صورة
$$O\left(\sum_{s\in S_R} |\mathcal T_{\ell,s}|\,\ell\right).$$
لذلك فإن الزمن الكلي تحكمه أساساً عدد عقد البحث التي تبقى بعد النشر. وعملياً، فإن ترشيح الرتب، والإسقاط العكسي على التلميحات، وتقليم all-different، وتفرع MRV كلها تخفض هذا العدد بوضوح. أما الذاكرة فمقدارها خطي في حالة اللغز الحالية، بالإضافة إلى جدول الرتب الثابت.