Project Euler 185 asks for a 16-digit secret code consistent with 22 clues. Each clue is another 16-digit string together with a number telling us how many positions are exact matches. Digits may repeat, and only digit-and-position matches matter; a correct digit in the wrong place gives no credit. One of the clues already says that 2321386104303845 has 0 correct positions, so the search begins with one forbidden digit at every position.
Brute force would mean checking up to \(10^{16}\) possible codes. The implementations avoid that by turning the puzzle into a small but rigid system of exact-match equations and then solving it with propagation plus a carefully chosen depth-first search.
Let the unknown secret be \(x=(x_1,\dots,x_{16})\), where each \(x_i\in\{0,\dots,9\}\). For the \(t\)-th clue, write the guessed digits as \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\) and its required number of exact matches as \(m_t\). Every clue imposes the equation
$$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$$
Equivalently, the Hamming distance between the secret and clue \(t\) is \(16-m_t\). The search does not guess complete codes; it maintains partial information about these 22 equations and keeps only states that can still satisfy all of them simultaneously.
At any stage, position \(i\) carries a current allowed set \(A_i\subseteq\{0,\dots,9\}\). If \(A_i=\{d\}\), then the digit at that position is already forced to be \(d\). If \(|A_i|\gt 1\), the position is still undecided.
This is the right state space for Number Mind because every clue talks about a specific digit at a specific position. The zero-match clue is therefore immediate information: if \(m_t=0\), then for every position \(i\) the digit \(g_i^{(t)}\) is removed from \(A_i\). In the full puzzle this single row already performs 16 bans before any branching happens.
Fix one clue \(t\). From the current sets \(A_i\), define
$$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|.$$
Here \(f_t\) counts positions already forced to match clue \(t\), while \(c_t\) counts undecided positions that could still match it. Any completion of the current state must satisfy the invariant
$$f_t\le m_t\le f_t+c_t.$$
If \(f_t\gt m_t\), we have already matched the clue too often. If \(f_t+c_t\lt m_t\), even making every remaining candidate match would not be enough. Either way the branch is impossible and can be pruned immediately. This inequality is the central mathematical test used throughout the search.
The same bound yields strong deterministic moves. If \(f_t=m_t\), then clue \(t\) has already used up all of its allowed matches, so every other candidate position for that clue must become a mismatch and the digit \(g_i^{(t)}\) can be deleted from \(A_i\).
If instead \(f_t+c_t=m_t\), then every position that can still match clue \(t\) must in fact match it, so all those positions are forced to their clue digits. There is also a purely positional consequence: if some \(A_i\) shrinks to size 1, that digit is fixed immediately. Repeating these implications is exactly what makes propagation powerful on this puzzle.
For clue \(t\), let
$$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t.$$
Any valid completion must choose exactly \(r_t\) positions from \(C_t\) that will match clue \(t\); all remaining positions in \(C_t\) must fail to match it. So the clue naturally induces
$$\binom{|C_t|}{r_t}$$
possible subsets. This is much sharper than branching digit-by-digit, because one branch decision can simultaneously create several equalities and several inequalities.
The search therefore chooses the clue with the smallest binomial branching factor. Once a subset \(S\subseteq C_t\) with \(|S|=r_t\) is selected, positions in \(S\) are forced to equal their clue digits, and positions in \(C_t\setminus S\) are forbidden from taking those digits. After that, feasibility and singleton propagation are run again.
The five-digit sample has clues 90342 with 2 exact matches, 70794 with 0, 39458 with 2, 34109 with 1, 51545 with 2, and 12531 with 1. The zero-match clue 70794 immediately forbids 7 at positions 1 and 3, 0 at position 2, 9 at position 4, and 4 at position 5.
Now inspect the clue 90342 with target 2. Because position 2 can no longer be 0, only positions \(1,3,4,5\) can still match that clue, so \(|C_t|=4\) and the branching count is \(\binom{4}{2}=6\). By contrast, the clue 34109 with target 1 still has five candidate positions, so its branching count is \(\binom{5}{1}=5\). That is slightly smaller, so it is the better clue to branch on first.
Continuing this exact logic yields the unique sample secret \(39542\). Checking it against the six sample clues gives match counts \(2,0,2,1,2,1\), so the sample is a complete small-scale version of the full 16-digit search.
The C++, Python, and Java implementations store a partial 16-digit assignment together with a 16 by 10 table of forbidden digits. Clues are sorted by their target match counts, so the most restrictive rows, especially the zero-match row and the one-match rows, are examined early. Before recursion begins, every zero-match clue is applied as an immediate position-wise ban.
Each recursive call first propagates singleton positions: whenever only one digit remains allowed at a position, that digit is fixed. Then every clue is rescanned to recompute the current values of \(f_t\) and \(c_t\). If any clue violates \(f_t\le m_t\le f_t+c_t\), the branch is abandoned at once.
The saturated cases \(r_t=0\) and \(r_t=|C_t|\) are especially strong. They mean a clue has no freedom left: either all of its remaining candidates must be mismatches or all of them must be matches. One of the implementations applies the first case explicitly as an extra propagation pass, while the common search logic handles both cases naturally because they create only one possible subset branch.
If the state is still incomplete, the implementation computes \(\binom{|C_t|}{r_t}\) for every clue and branches on the smallest value. A branch is not a raw digit guess; it decides exactly which positions of one clue are the remaining matches. That usually changes several positions at once and triggers more propagation immediately afterward.
When all 16 positions are fixed, the resulting code is checked against all 22 exact-match counts. The instance is known to have a unique solution, and the search is structured to make that visible: the C++ implementation explicitly continues until a second solution would be found, while the others stop after the first consistent completion on this unique-solution input.
In the worst case this remains an exponential backtracking problem: arbitrary exact-match clue systems do not come with a polynomial-time guarantee, and the naive space starts at \(10^{16}\) possible codes. The algorithm becomes practical because it cuts away most of that space long before full assignments are formed.
For this specific puzzle, each node of the search tree is cheap. There are only \(G=22\) clues and \(L=16\) positions, so a full feasibility scan costs \(O(GL)\), which here is just a small constant-size table scan. The expensive part is the number of recursive states, but zero-match preprocessing, singleton propagation, feasibility bounds, and the minimum-\(\binom{|C_t|}{r_t}\) branching rule collapse the tree dramatically.
Memory use is modest. One active recursive path stores the partial assignment and the forbidden-digit table, so the working state is \(O(16\cdot 10)\), plus recursion depth at most 16. In practice the solver succeeds because it reasons about whole clue rows at once instead of exploring codes digit-by-digit.
Project Euler 185 verlangt einen 16-stelligen Geheimcode, der mit 22 Hinweisen zugleich verträglich ist. Jeder Hinweis besteht aus einer weiteren 16-stelligen Ziffernfolge und einer Zahl, die angibt, wie viele Stellen exakt stimmen. Ziffern dürfen sich wiederholen, und es zählen nur Treffer an der richtigen Position; eine richtige Ziffer an der falschen Stelle bringt nichts. Einer der Hinweise sagt bereits, dass 2321386104303845 an keiner Position korrekt ist, also startet die Suche sofort mit einer verbotenen Ziffer pro Stelle.
Brute Force hieße, bis zu \(10^{16}\) mögliche Codes zu testen. Die Implementierungen vermeiden das, indem sie das Rätsel als kleines, aber sehr starres System von Exakt-Treffer-Gleichungen auffassen und dieses System mit Propagation plus gezielter Tiefensuche lösen.
Sei \(x=(x_1,\dots,x_{16})\) der unbekannte Geheimcode mit \(x_i\in\{0,\dots,9\}\). Für den \(t\)-ten Hinweis schreiben wir die geratenen Ziffern als \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\) und die geforderte Zahl exakter Treffer als \(m_t\). Jeder Hinweis liefert die Gleichung
$$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$$
Äquivalent dazu ist der Hamming-Abstand zwischen dem Geheimcode und Hinweis \(t\) gleich \(16-m_t\). Die Suche rät also nicht komplette Codes, sondern verwaltet partielle Information über diese 22 Gleichungen und behält nur Zustände, die alle noch gleichzeitig erfüllen können.
In jedem Suchzustand besitzt Position \(i\) eine aktuelle erlaubte Menge \(A_i\subseteq\{0,\dots,9\}\). Falls \(A_i=\{d\}\) gilt, ist diese Stelle bereits auf \(d\) festgelegt. Falls \(|A_i|\gt 1\), bleibt die Position noch offen.
Genau das ist für Number Mind die richtige Zustandsbeschreibung, weil jeder Hinweis nur über eine bestimmte Ziffer an einer bestimmten Position spricht. Ein Hinweis mit \(m_t=0\) ist deshalb sofort verwertbar: Für jede Position \(i\) wird die Ziffer \(g_i^{(t)}\) aus \(A_i\) entfernt. Im vollen 16-stelligen Rätsel erzeugt diese eine Zeile bereits 16 Verbote, noch bevor verzweigt wird.
Fixiere einen Hinweis \(t\). Aus den aktuellen Mengen \(A_i\) definieren wir
$$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|.$$
Dabei zählt \(f_t\) die Positionen, die bereits sicher mit Hinweis \(t\) übereinstimmen, während \(c_t\) die noch offenen Positionen zählt, die Hinweis \(t\) eventuell noch treffen könnten. Jede Vervollständigung des Zustands muss daher die Invariante
$$f_t\le m_t\le f_t+c_t$$
erfüllen. Wenn \(f_t\gt m_t\) ist, wurde der Hinweis schon zu oft getroffen. Wenn \(f_t+c_t\lt m_t\) ist, reichen selbst alle verbleibenden Kandidaten nicht mehr aus. In beiden Fällen ist der Zweig unmöglich und wird sofort abgeschnitten.
Aus derselben Ungleichung folgen starke deterministische Schritte. Gilt \(f_t=m_t\), dann hat Hinweis \(t\) alle seine erlaubten Treffer bereits verbraucht. Jede andere Kandidatenposition dieses Hinweises muss also zu einem Nicht-Treffer werden, und die Ziffer \(g_i^{(t)}\) kann aus \(A_i\) entfernt werden.
Gilt dagegen \(f_t+c_t=m_t\), dann ist jeder noch mögliche Treffer dieses Hinweises tatsächlich zwingend, also werden alle diese Positionen auf ihre Hinweisziffern festgelegt. Hinzu kommt eine rein positionsbezogene Konsequenz: Sobald eine Menge \(A_i\) nur noch ein Element enthält, wird diese Ziffer sofort gesetzt. Das wiederholte Anwenden solcher Schlüsse ist genau die Propagation.
Für Hinweis \(t\) definieren wir
$$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t.$$
Jede gültige Lösung muss genau \(r_t\) Positionen aus \(C_t\) auswählen, die mit Hinweis \(t\) übereinstimmen; alle übrigen Positionen in \(C_t\) dürfen nicht übereinstimmen. Damit entstehen auf natürliche Weise
$$\binom{|C_t|}{r_t}$$
mögliche Teilmengen. Das ist viel schärfer als eine naive ziffernweise Verzweigung, weil eine einzige Fallunterscheidung gleichzeitig mehrere Gleichheiten und mehrere Ungleichheiten festlegt.
Die Suche wählt deshalb den Hinweis mit dem kleinsten binomialen Verzweigungsfaktor. Ist eine Teilmenge \(S\subseteq C_t\) mit \(|S|=r_t\) ausgewählt, dann werden die Positionen in \(S\) auf ihre Hinweisziffern gesetzt, und für die Positionen in \(C_t\setminus S\) wird genau diese Ziffer verboten. Danach laufen Machbarkeitsprüfung und Singleton-Propagation erneut.
Das Beispiel aus der Aufgabenstellung hat die Hinweise 90342 mit 2 exakten Treffern, 70794 mit 0, 39458 mit 2, 34109 mit 1, 51545 mit 2 und 12531 mit 1. Der Null-Treffer-Hinweis 70794 verbietet sofort die Ziffern 7 an den Positionen 1 und 3, 0 an Position 2, 9 an Position 4 und 4 an Position 5.
Betrachten wir nun 90342 mit Zielwert 2. Weil Position 2 nicht mehr 0 sein darf, kommen nur die Positionen \(1,3,4,5\) noch als Treffer infrage. Also ist \(|C_t|=4\) und die Zahl der Fälle beträgt \(\binom{4}{2}=6\). Beim Hinweis 34109 mit Zielwert 1 sind dagegen noch fünf Kandidatenpositionen möglich, also beträgt der Verzweigungsfaktor \(\binom{5}{1}=5\). Das ist etwas kleiner und daher die bessere Wahl für den ersten Suchschritt.
Führt man diese Logik fort, erhält man den eindeutigen Beispielcode \(39542\). Gegen die sechs Beispielhinweise geprüft liefert er die exakten Trefferzahlen \(2,0,2,1,2,1\) und illustriert damit im Kleinen genau denselben Mechanismus wie das volle 16-stellige Problem.
Die Implementierungen in C++, Python und Java speichern eine partielle 16-stellige Belegung zusammen mit einer 16-mal-10-Tabelle verbotener Ziffern. Die Hinweise werden nach ihrer Trefferzahl sortiert, sodass besonders einschränkende Zeilen, vor allem der Null-Treffer-Hinweis und die Hinweise mit nur einem Treffer, früh betrachtet werden. Vor dem Start der Rekursion wird jeder Null-Treffer-Hinweis sofort positionsweise als Verbot eingetragen.
Jeder rekursive Aufruf beginnt mit Singleton-Propagation: Wenn an einer Position nur noch eine Ziffer erlaubt ist, wird diese fest gesetzt. Anschließend werden alle Hinweise erneut durchlaufen, um die aktuellen Werte \(f_t\) und \(c_t\) zu berechnen. Verletzt irgendein Hinweis die Bedingung \(f_t\le m_t\le f_t+c_t\), wird der Zweig sofort verworfen.
Besonders stark sind die gesättigten Fälle \(r_t=0\) und \(r_t=|C_t|\). Dann besitzt ein Hinweis keine Freiheit mehr: Entweder müssen alle verbliebenen Kandidaten Nicht-Treffer sein oder alle müssen Treffer sein. Eine der Implementierungen nutzt den ersten Fall explizit als zusätzlichen Propagationsschritt, während die gemeinsame Suchlogik beide Fälle ohnehin natürlich behandelt, weil jeweils nur noch genau ein Teilmengenast übrig bleibt.
Ist der Zustand noch nicht vollständig, berechnet die Implementierung für jeden Hinweis den Wert \(\binom{|C_t|}{r_t}\) und verzweigt beim kleinsten davon. Ein Ast rät also nicht einfach eine Ziffer, sondern entscheidet, welche Positionen eines Hinweises die restlichen Treffer bilden. Das verändert meist mehrere Stellen zugleich und löst sofort weitere Propagation aus.
Sobald alle 16 Positionen festliegen, wird der Kandidat noch einmal gegen alle 22 Exakt-Treffer-Bedingungen geprüft. Die Instanz besitzt bekanntermaßen eine eindeutige Lösung, und die Suche macht das sichtbar: Die C++-Implementierung läuft explizit so weit weiter, bis eine zweite Lösung gefunden würde, während die anderen Implementierungen bei dieser eindeutigen Eingabe nach der ersten konsistenten Komplettbelegung stoppen.
Im Worst Case bleibt dies ein exponentielles Backtracking-Problem: Für beliebige Systeme solcher Exakt-Treffer-Hinweise gibt es keine polynomialzeitliche Garantie, und der naive Suchraum beginnt bei \(10^{16}\) Codes. Praktisch wird das Verfahren nur deshalb schnell, weil es den größten Teil dieses Raums frühzeitig wegschneidet.
Für dieses konkrete Rätsel ist jeder Suchknoten billig. Es gibt nur \(G=22\) Hinweise und \(L=16\) Positionen, daher kostet ein vollständiger Machbarkeitsdurchlauf \(O(GL)\), also hier nur das erneute Durchmustern einer kleinen Tabelle. Teuer ist die Zahl der rekursiven Zustände, aber Null-Treffer-Vorverarbeitung, Singleton-Propagation, Machbarkeitsgrenzen und die Regel mit minimalem \(\binom{|C_t|}{r_t}\) schrumpfen den Suchbaum drastisch.
Auch der Speicherbedarf ist klein. Ein aktiver Rekursionspfad speichert die partielle Belegung und die Verbotstabelle, also einen Arbeitszustand von \(O(16\cdot 10)\), plus Rekursionstiefe von höchstens 16. Der Solver funktioniert in der Praxis, weil er über ganze Hinweiszeilen argumentiert und nicht Ziffer für Ziffer blind ausprobiert.
Project Euler 185, 22 ipucunun tamamıyla uyumlu olan 16 basamaklı gizli kodu ister. Her ipucu, başka bir 16 basamaklı dizi ve onunla tam olarak aynı olan konum sayısını verir. Rakamlar tekrar edebilir; sadece doğru rakamın doğru yerde olması önemlidir, yanlış yerde duran doğru rakam puan getirmez. İpuçlarından biri 2321386104303845 dizisinin hiçbir konumda doğru olmadığını söylediği için arama daha baştan her pozisyon için bir yasaklı rakamla başlar.
Kaba kuvvet yaklaşımı en fazla \(10^{16}\) olası kodu denemek anlamına gelir. Uygulamalar bunu yapmaz; bunun yerine problemi tam eşleşme denklemlerinden oluşan küçük ama çok katı bir sistem olarak görür ve bu sistemi yayılım artı dikkatli seçilmiş bir derinlik öncelikli arama ile çözer.
Bilinmeyen gizli kodu \(x=(x_1,\dots,x_{16})\) ile gösterelim; her \(x_i\in\{0,\dots,9\}\) olsun. \(t\)-inci ipucunun rakamlarını \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\), istenen tam eşleşme sayısını da \(m_t\) ile yazalım. Her ipucu şu denklemi verir:
$$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$$
Eşdeğer olarak, gizli kod ile \(t\)-inci ipucu arasındaki Hamming uzaklığı \(16-m_t\) olur. Arama, tüm kodu bir anda tahmin etmek yerine bu 22 denklem hakkında kısmi bilgi tutar ve ancak hepsi birlikte hâlâ sağlanabiliyorsa durumu korur.
Aramanın her anında \(i\) konumu için bir izinli küme \(A_i\subseteq\{0,\dots,9\}\) tutulur. Eğer \(A_i=\{d\}\) ise o pozisyon artık kesin olarak \(d\)'dir. Eğer \(|A_i|\gt 1\) ise pozisyon henüz tam belirlenmemiştir.
Bu durum uzayı Number Mind için çok uygundur, çünkü her ipucu belirli bir konumdaki belirli bir rakam hakkında konuşur. Bu yüzden \(m_t=0\) olan bir satır doğrudan bilgi verir: her \(i\) için \(g_i^{(t)}\) rakamı \(A_i\)'den çıkarılır. Tam 16 basamaklı bulmacada bu tek satır, dallanmadan önce 16 ayrı yasağı otomatik olarak üretir.
Bir \(t\) ipucunu sabitleyelim. Güncel \(A_i\) kümelerinden
$$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|$$
tanımlarını yapalım. Burada \(f_t\), o ipucuyla eşleşmesi artık kesinleşmiş konumları; \(c_t\) ise hâlâ o ipucuyla eşleşme ihtimali olan açık konumları sayar. Her geçerli tamamlanış şu değişmezi sağlamak zorundadır:
$$f_t\le m_t\le f_t+c_t.$$
Eğer \(f_t\gt m_t\) ise ipucu şimdiden fazla eşleşmiştir. Eğer \(f_t+c_t\lt m_t\) ise kalan bütün adaylar eşleşse bile hedefe ulaşılamaz. Her iki durumda da dal imkansızdır ve hemen budanır. Aramanın ana matematiksel kontrolü bu eşitsizliktir.
Aynı eşitsizlik güçlü deterministik hamleler de üretir. Eğer \(f_t=m_t\) ise ilgili ipucu izin verilen bütün eşleşmelerini zaten kullanmıştır. Bu durumda o ipucu için kalan her aday konum artık eşleşme olamaz ve \(g_i^{(t)}\) rakamı \(A_i\)'den silinir.
Eğer bunun yerine \(f_t+c_t=m_t\) ise, hâlâ mümkün olan her eşleşme aslında zorunludur; yani bu aday konumların tümü ilgili ipucu rakamlarına sabitlenir. Pozisyonların kendi içinden gelen bir başka zorlayıcı durum da şudur: bir \(A_i\) kümesi tek elemana düştüğünde o rakam hemen atanır. Bu çıkarımları art arda uygulamak, kodun yaptığı yayılımdır.
\(t\) ipucusu için
$$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t$$
olsun. Geçerli bir çözüm, \(C_t\) içinden tam olarak \(r_t\) tane konumu bu ipucuyla eşleşecek şekilde seçmek zorundadır; \(C_t\)'deki diğer konumlar ise bu ipucuyla eşleşemez. Böylece doğal olarak
$$\binom{|C_t|}{r_t}$$
adet alt durum ortaya çıkar. Bu, konum konum on rakam denemekten çok daha keskindir; çünkü tek bir dallanma kararı aynı anda birkaç eşitlik ve birkaç eşitsizlik üretir.
Bu yüzden arama, binom katsayısı en küçük olan ipucunu seçer. \(|S|=r_t\) olacak biçimde \(S\subseteq C_t\) alt kümesi seçildiğinde, \(S\)'deki konumlar ipucu rakamlarına sabitlenir; \(C_t\setminus S\)'deki konumlarda ise o rakamlar yasaklanır. Sonra yapılabilirlik testi ve tek-aday yayılımı yeniden çalıştırılır.
Sorudaki beş basamaklı örnekte şu ipuçları vardır: 90342 için 2 tam eşleşme, 70794 için 0, 39458 için 2, 34109 için 1, 51545 için 2 ve 12531 için 1. Sıfır eşleşmeli 70794 satırı, 1. ve 3. konumda 7'yi, 2. konumda 0'ı, 4. konumda 9'u ve 5. konumda 4'ü hemen yasaklar.
Şimdi hedefi 2 olan 90342 ipucusuna bakalım. 2. konum artık 0 olamayacağı için bu ipucuyla yalnızca \(1,3,4,5\) konumları eşleşebilir. Dolayısıyla \(|C_t|=4\) ve dal sayısı \(\binom{4}{2}=6\) olur. Buna karşılık hedefi 1 olan 34109 ipucusunda beş konum da hâlâ adaydır; bu yüzden dal sayısı \(\binom{5}{1}=5\) olur. Bu biraz daha küçük olduğu için önce dallanmak adına daha iyi ipucudur.
Aynı mantık sürdürülünce örnek bulmacanın tek çözümünün \(39542\) olduğu bulunur. Bu dizi altı örnek ipucusuna karşı sırasıyla \(2,0,2,1,2,1\) tam eşleşme verdiği için, tam 16 basamaklı problemdeki mekanizmanın küçük ölçekli bir kopyasını oluşturur.
C++, Python ve Java uygulamaları kısmi bir 16 basamaklı atama ile birlikte 16'ya 10 boyutlu bir yasaklı rakam tablosu tutar. İpuçları hedef eşleşme sayılarına göre sıralanır; böylece özellikle sıfır eşleşmeli ve bir eşleşmeli satırlar baştan daha etkili olur. Özyineleme başlamadan önce, her sıfır eşleşmeli satır konum bazında doğrudan yasak olarak uygulanır.
Her özyinelemeli çağrı önce tek-aday yayılımı yapar: bir konumda yalnızca tek rakam kaldıysa o rakam sabitlenir. Sonra bütün ipuçları tekrar taranarak güncel \(f_t\) ve \(c_t\) değerleri hesaplanır. Eğer herhangi bir ipucu \(f_t\le m_t\le f_t+c_t\) koşulunu bozuyorsa ilgili dal anında terk edilir.
\(r_t=0\) ve \(r_t=|C_t|\) durumları özellikle kuvvetlidir. Çünkü artık o ipucu için özgürlük kalmamıştır: kalan bütün adaylar ya eşleşmemek zorundadır ya da eşleşmek zorundadır. Uygulamalardan biri ilk durumu ek bir yayılım adımı olarak açıkça uygular; ortak arama mantığı ise iki durumu da doğal biçimde kapsar, çünkü her ikisinde de yalnızca tek bir alt küme dalı vardır.
Durum tamamlanmamışsa, uygulama her ipucu için \(\binom{|C_t|}{r_t}\) değerini hesaplar ve en küçük olan üzerinden dallanır. Yani dal, ham bir rakam tahmini değildir; bir ipucunun kalan eşleşmelerinin hangi konumlarda olduğunu seçer. Bu, aynı anda birçok pozisyonu değiştirir ve çoğu zaman hemen ardından yeni yayılımlar doğurur.
Tüm 16 konum sabitlendiğinde bulunan aday, 22 ipucunun hepsine karşı tekrar doğrulanır. Bu girdinin tek çözümlü olduğu bilinir ve arama bunu görünür kılacak şekilde düzenlenmiştir: C++ uygulaması ikinci bir çözüm çıkıp çıkmayacağını da kontrol edecek kadar devam eder; diğerleri ise bu tek çözümlü girdide ilk tutarlı tamamlanışta durur.
En kötü durumda bu yöntem hâlâ üstel bir geri izleme problemidir: bu tür tam eşleşme sistemleri için genel bir polinom-zaman garantisi yoktur ve saf arama uzayı \(10^{16}\) kodla başlar. Yöntemin pratik olmasının nedeni, tam atama oluşmadan önce bu uzayın büyük kısmını budamasıdır.
Bu özel bulmacada her arama düğümü ucuzdur. Yalnızca \(G=22\) ipucu ve \(L=16\) konum vardır; dolayısıyla tam bir yapılabilirlik taraması \(O(GL)\) maliyetlidir ve burada küçük sabit boyutlu bir tablo turundan ibarettir. Asıl pahalı kısım özyinelemeli durum sayısıdır; fakat sıfır eşleşmeli ön işleme, tek-aday yayılımı, yapılabilirlik sınırları ve en küçük \(\binom{|C_t|}{r_t}\) kuralı arama ağacını dramatik biçimde küçültür.
Bellek kullanımı da sınırlıdır. Etkin bir özyineleme yolu, kısmi atamayı ve yasaklı rakam tablosunu tutar; dolayısıyla çalışma durumu \(O(16\cdot 10)\) boyutundadır ve özyineleme derinliği en fazla 16'dır. Pratikte başarının nedeni, kodları rakam rakam denemek yerine bütün ipucu satırları hakkında birlikte akıl yürütmesidir.
Project Euler 185 pide encontrar un código secreto de 16 dígitos compatible con 22 pistas. Cada pista es otra cadena de 16 dígitos acompañada por un número que indica cuántas posiciones coinciden exactamente. Los dígitos pueden repetirse, y solo cuentan las coincidencias de dígito y posición; un dígito correcto en una posición distinta no aporta nada. Una de las pistas ya afirma que 2321386104303845 tiene 0 aciertos posicionales, así que la búsqueda arranca con un dígito prohibido en cada posición.
La fuerza bruta significaría revisar hasta \(10^{16}\) códigos posibles. Las implementaciones evitan eso reinterpretando el rompecabezas como un sistema pequeño pero muy rígido de ecuaciones de coincidencia exacta, y luego resolviéndolo con propagación más una búsqueda en profundidad cuidadosamente escogida.
Sea \(x=(x_1,\dots,x_{16})\) el código secreto desconocido, con cada \(x_i\in\{0,\dots,9\}\). Para la pista número \(t\), escribimos los dígitos propuestos como \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\) y el número exigido de coincidencias exactas como \(m_t\). Cada pista impone la ecuación
$$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$$
De manera equivalente, la distancia de Hamming entre el secreto y la pista \(t\) es \(16-m_t\). La búsqueda no adivina códigos completos; mantiene información parcial sobre estas 22 ecuaciones y solo conserva estados que todavía pueden satisfacerlas todas a la vez.
En cada momento, la posición \(i\) lleva asociada un conjunto permitido \(A_i\subseteq\{0,\dots,9\}\). Si \(A_i=\{d\}\), entonces esa posición ya está fijada al dígito \(d\). Si \(|A_i|\gt 1\), la posición sigue sin decidirse.
Este es el espacio de estados adecuado para Number Mind porque cada pista habla de un dígito concreto en una posición concreta. Por eso una pista con \(m_t=0\) aporta información inmediata: para cada \(i\), el dígito \(g_i^{(t)}\) se elimina de \(A_i\). En el problema completo de 16 cifras, esa sola fila ya produce 16 prohibiciones antes de cualquier ramificación.
Fijemos una pista \(t\). A partir de los conjuntos actuales \(A_i\), definimos
$$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|.$$
Aquí \(f_t\) cuenta las posiciones que ya están forzadas a coincidir con la pista \(t\), mientras que \(c_t\) cuenta las posiciones todavía abiertas que aún podrían coincidir. Cualquier completación válida del estado debe satisfacer la invariante
$$f_t\le m_t\le f_t+c_t.$$
Si \(f_t\gt m_t\), ya hemos igualado la pista demasiadas veces. Si \(f_t+c_t\lt m_t\), ni siquiera haciendo coincidir todos los candidatos restantes podríamos alcanzar el objetivo. En ambos casos la rama es imposible y se poda en el acto.
La misma desigualdad produce movimientos deterministas muy fuertes. Si \(f_t=m_t\), la pista \(t\) ya ha gastado todas sus coincidencias permitidas, de modo que cualquier otra posición candidata de esa pista debe convertirse en un desacierto, y el dígito \(g_i^{(t)}\) se puede eliminar de \(A_i\).
Si en cambio \(f_t+c_t=m_t\), entonces toda coincidencia que todavía sea posible en esa pista pasa a ser obligatoria, así que esas posiciones quedan fijadas a los dígitos de la pista. También hay una consecuencia puramente posicional: si algún conjunto \(A_i\) se reduce a un solo elemento, ese dígito se asigna de inmediato. Repetir estas implicaciones es precisamente la propagación.
Para la pista \(t\), definimos
$$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t.$$
Cualquier solución válida debe escoger exactamente \(r_t\) posiciones de \(C_t\) que terminarán coincidiendo con la pista \(t\); todas las demás posiciones de \(C_t\) deben fallar respecto a esa pista. Por tanto, la pista induce de forma natural
$$\binom{|C_t|}{r_t}$$
subconjuntos posibles. Eso es mucho más preciso que probar dígitos uno a uno, porque una sola decisión de rama impone varias igualdades y varias desigualdades al mismo tiempo.
La heurística de búsqueda consiste entonces en elegir la pista con el menor factor binomial de ramificación. Una vez elegido un subconjunto \(S\subseteq C_t\) con \(|S|=r_t\), las posiciones de \(S\) se fuerzan a tomar los dígitos de la pista y las posiciones de \(C_t\setminus S\) quedan prohibidas para esos mismos dígitos. Después se ejecutan otra vez la factibilidad y la propagación de singletons.
El ejemplo de cinco dígitos del enunciado tiene las pistas 90342 con 2 coincidencias exactas, 70794 con 0, 39458 con 2, 34109 con 1, 51545 con 2 y 12531 con 1. La pista sin coincidencias, 70794, prohíbe inmediatamente el 7 en las posiciones 1 y 3, el 0 en la posición 2, el 9 en la posición 4 y el 4 en la posición 5.
Ahora observemos la pista 90342 con objetivo 2. Como la posición 2 ya no puede ser 0, solo las posiciones \(1,3,4,5\) pueden seguir coincidiendo con esa pista. Por tanto \(|C_t|=4\) y el número de ramas es \(\binom{4}{2}=6\). En cambio, la pista 34109 con objetivo 1 todavía tiene cinco posiciones candidatas, así que su factor de ramificación es \(\binom{5}{1}=5\). Eso es un poco menor, y por tanto es mejor pista para ramificar primero.
Si se continúa con esta misma lógica, se obtiene la solución única del ejemplo: \(39542\). Al compararla con las seis pistas del ejemplo aparecen exactamente los conteos \(2,0,2,1,2,1\), de modo que el ejemplo es una versión en miniatura del problema completo de 16 dígitos.
Las implementaciones en C++, Python y Java guardan una asignación parcial de 16 dígitos junto con una tabla de 16 por 10 de dígitos prohibidos. Las pistas se ordenan por su número objetivo de coincidencias, de modo que las filas más restrictivas, en especial la de 0 coincidencias y las de 1 coincidencia, se examinan pronto. Antes de comenzar la recursión, toda pista con 0 coincidencias se aplica como una prohibición posicional inmediata.
Cada llamada recursiva empieza propagando los singletons: cuando en una posición solo queda un dígito permitido, ese dígito se fija. Después se recorren todas las pistas para recomputar los valores actuales de \(f_t\) y \(c_t\). Si alguna pista viola \(f_t\le m_t\le f_t+c_t\), la rama se descarta al instante.
Los casos saturados \(r_t=0\) y \(r_t=|C_t|\) son especialmente potentes. Significan que una pista ya no tiene libertad: o bien todos sus candidatos restantes deben ser desaciertos o bien todos deben ser aciertos. Una de las implementaciones aplica el primer caso explícitamente como paso extra de propagación, mientras que la lógica común de búsqueda gestiona ambos casos de forma natural porque dejan un único subconjunto posible.
Si el estado todavía no está completo, la implementación calcula \(\binom{|C_t|}{r_t}\) para cada pista y ramifica en el valor más pequeño. Una rama no es una mera prueba de dígitos; decide exactamente qué posiciones de una pista constituyen las coincidencias restantes. Eso modifica varias posiciones a la vez y suele desencadenar más propagación inmediatamente.
Cuando las 16 posiciones quedan fijadas, el candidato resultante se verifica contra las 22 cuentas de coincidencia exacta. La instancia se sabe de solución única, y la estructura de búsqueda lo hace visible: la implementación en C++ continúa explícitamente hasta comprobar si aparecería una segunda solución, mientras que las otras se detienen en la primera completación consistente para esta entrada de solución única.
En el peor caso esto sigue siendo un problema exponencial de backtracking: para sistemas arbitrarios de pistas de coincidencia exacta no hay garantía de tiempo polinómico, y el espacio ingenuo comienza en \(10^{16}\) códigos posibles. La mejora real proviene de la poda, no de un cambio en la clase teórica del problema.
Para esta instancia concreta, cada nodo del árbol es barato. Solo hay \(G=22\) pistas y \(L=16\) posiciones, así que un barrido completo de factibilidad cuesta \(O(GL)\), que aquí es simplemente volver a recorrer una tabla muy pequeña. Lo costoso es el número de estados recursivos, pero el preprocesamiento de la pista de 0 coincidencias, la propagación de singletons, las cotas de factibilidad y la regla de ramificar con el menor \(\binom{|C_t|}{r_t}\) reducen el árbol de forma drástica.
El uso de memoria es modesto. Una ruta activa de la recursión almacena la asignación parcial y la tabla de dígitos prohibidos, de modo que el estado de trabajo es \(O(16\cdot 10)\), más una profundidad recursiva de como mucho 16. En la práctica el método funciona porque razona sobre filas completas de pistas en lugar de probar códigos dígito a dígito.
Project Euler 185 要求找出一个满足 22 条线索的 16 位秘密数字串。每条线索都是另一串 16 位数字，外加一个整数，表示其中有多少个位置同时满足“数字正确且位置正确”。数字可以重复，题目只关心精确位置匹配；如果某个数字出现在别的位置上，并不会得到任何计数。给定线索中还有一条特别强：2321386104303845 的匹配数为 0，因此一开始就能在 16 个位置上各排除一个特定数字。
如果直接暴力搜索，就相当于检查最多 \(10^{16}\) 个候选密码，这显然不可行。三个实现真正做的是把题目写成一组精确匹配方程，再在这组方程上做传播与剪枝，只在必要时进行很小的分支搜索。
设未知密码为 \(x=(x_1,\dots,x_{16})\)，其中每个 \(x_i\in\{0,\dots,9\}\)。把第 \(t\) 条线索写成 \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\)，其要求的精确匹配个数记为 \(m_t\)。那么每条线索都对应约束
$$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$$
也可以说，密码与第 \(t\) 条线索之间的 Hamming 距离等于 \(16-m_t\)。整个搜索的核心并不是猜完整密码，而是维护这些 22 个方程在“部分已知”状态下还能否同时成立。
在任意时刻，第 \(i\) 个位置都带有一个当前允许集合 \(A_i\subseteq\{0,\dots,9\}\)。如果 \(A_i=\{d\}\)，说明这个位置已经被强制确定为数字 \(d\)；如果 \(|A_i|\gt 1\)，则该位置仍未决定。
这种表示法正好贴合 Number Mind，因为每条线索只约束“某个位置能否等于某个具体数字”。因此匹配数为 0 的线索具有立刻可用的力量：只要 \(m_t=0\)，就能对每个位置 \(i\) 删除数字 \(g_i^{(t)}\)。在完整的 16 位实例里，这一行线索本身就先完成了 16 次位置定向排除。
固定一条线索 \(t\)。根据当前的允许集合 \(A_i\)，定义
$$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|.$$
这里 \(f_t\) 表示已经被强制与线索 \(t\) 匹配的位置数，\(c_t\) 表示还未定值、但仍有可能与线索 \(t\) 匹配的位置数。任何对当前状态的合法补全都必须满足
$$f_t\le m_t\le f_t+c_t.$$
如果 \(f_t\gt m_t\)，就说明这条线索已经“匹配过头”；如果 \(f_t+c_t\lt m_t\)，则说明即便把剩余所有候选位置都设成匹配，也达不到目标值。两种情况都意味着当前分支不可能成功，可以立刻回溯。这条不等式正是搜索过程中最核心的可行性不变量。
上述不等式不仅能剪枝，还能直接推出确定信息。如果 \(f_t=m_t\)，那么线索 \(t\) 允许的匹配数已经全部用完，剩余所有还可能匹配该线索的位置都必须变成不匹配，于是对应的线索数字可以从那些 \(A_i\) 中删除。
相反，如果 \(f_t+c_t=m_t\)，则线索 \(t\) 剩下的每一个“可能匹配”实际上都必须真的匹配，所以这些位置都要被强制设成相应的线索数字。还有一种来自位置自身的强制：一旦某个 \(A_i\) 缩成单元素集合，该位置就立即定值。代码不断重复这些逻辑，这就是传播步骤的数学含义。
对线索 \(t\)，记
$$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t.$$
任何合法解都必须从 \(C_t\) 中恰好选出 \(r_t\) 个位置，使它们最终与线索 \(t\) 匹配；而 \(C_t\) 中剩下的位置则必须与这条线索不匹配。因此，这条线索天然给出了
$$\binom{|C_t|}{r_t}$$
种可能的子集选择。与逐位尝试 10 个数字相比，这样的分支要精确得多，因为一次子集决策会同时引入多条等式和多条不等式。
因此，搜索策略是挑选 \(\binom{|C_t|}{r_t}\) 最小的那条线索来分支。若选定某个子集 \(S\subseteq C_t\) 且 \(|S|=r_t\)，则 \(S\) 中的位置被强制等于对应线索数字，而 \(C_t\setminus S\) 中的位置则被禁止取这些数字。随后再次运行可行性检查和单候选传播。
题目给出的五位数样例包含六条线索：90342 有 2 个精确匹配，70794 有 0 个，39458 有 2 个，34109 有 1 个，51545 有 2 个，12531 有 1 个。首先，零匹配线索 70794 立即排除：第 1 位和第 3 位不能是 7，第 2 位不能是 0，第 4 位不能是 9，第 5 位不能是 4。
再看目标值为 2 的线索 90342。由于第 2 位已经不可能是 0，所以只有位置 \(1,3,4,5\) 仍可能与它匹配，于是 \(|C_t|=4\)，对应的分支数是 \(\binom{4}{2}=6\)。而目标值为 1 的线索 34109 此时五个位置都还可能匹配，所以它的分支数是 \(\binom{5}{1}=5\)。因为 5 比 6 更小，优先用这条线索分支更合理。
沿着这套逻辑继续推进，最终会得到样例的唯一答案 \(39542\)。把它代回六条样例线索，得到的精确匹配数正好是 \(2,0,2,1,2,1\)。这说明样例已经完整体现了 16 位正式题目的数学机制，只是规模更小。
C++、Python 和 Java 实现都维护一份部分赋值，以及一个 \(16\times 10\) 的禁用数字表。线索会按目标匹配数从小到大排序，这样限制最强的行，尤其是 0 匹配和 1 匹配的行，会更早参与搜索。在递归开始之前，所有 0 匹配线索都会先作为逐位置禁用规则应用一次。
每次递归调用首先做单候选传播：如果某个位置只剩一个允许数字，就立刻把它固定下来。然后重新扫描全部线索，计算当前的 \(f_t\) 和 \(c_t\)。只要有任何一条线索违反 \(f_t\le m_t\le f_t+c_t\)，该分支就立即终止。
其中 \(r_t=0\) 和 \(r_t=|C_t|\) 两种饱和情形尤其重要。它们表示该线索已经没有自由度了：要么剩余候选位置全部必须不匹配，要么全部必须匹配。三个实现共享的搜索框架都会自然处理这两种单分支情况，而其中一个实现还把前一种情形额外作为一次显式传播。
如果 16 个位置还没有全部定值，程序就为每条线索计算 \(\binom{|C_t|}{r_t}\)，并选择最小的那个值进行分支。这里的分支不是“猜一个数字”，而是“决定某条线索剩余的匹配位置究竟是哪几个”。这样的决策通常会同时更新多个位置，因此后续往往马上又触发新的传播。
当全部 16 位都被固定后，得到的候选密码还会再次对照 22 条线索做完整验证。题目实例已知只有唯一解，搜索结构也体现了这一点：C++ 版本会继续搜索到足以发现“是否存在第二解”，而另外两个版本则在这个唯一解实例上于第一组一致的完整赋值处停止。
从最坏情况看，这仍然是指数级回溯搜索。对任意“精确匹配计数”约束系统，并不存在普适的多项式时间保证，而朴素候选空间一开始就是 \(10^{16}\) 个密码。这个算法之所以可行，靠的是强剪枝，而不是改变理论上的最坏复杂度。
对本题来说，每个搜索节点本身很便宜。线索数只有 \(G=22\)，位置数只有 \(L=16\)，因此一次完整可行性扫描的成本是 \(O(GL)\)，实际就是反复查看一个很小的表。真正决定运行时间的是递归状态数，但零匹配预处理、单候选传播、可行性界以及最小 \(\binom{|C_t|}{r_t}\) 分支规则会把搜索树大幅压缩。
内存使用也很小。递归路径上一个活动状态只需要保存部分赋值和禁用数字表，所以工作状态规模是 \(O(16\cdot 10)\)，递归深度最多 16。它之所以高效，是因为程序始终按整条线索进行推理，而不是逐位盲猜密码。
Project Euler 185 просит найти 16-значный секретный код, согласованный сразу с 22 подсказками. Каждая подсказка состоит из другой 16-значной строки и числа, показывающего, сколько позиций совпадает точно. Цифры могут повторяться, и учитываются только совпадения вида «правильная цифра в правильной позиции»; правильная цифра в другом месте не приносит ничего. Одна из подсказок сразу сообщает, что 2321386104303845 не совпадает ни в одной позиции, поэтому поиск стартует уже с одним запрещенным значением на каждом месте.
Полный перебор означал бы проверку до \(10^{16}\) возможных кодов. Реальные реализации этого не делают: они рассматривают задачу как небольшую, но жесткую систему уравнений на точные совпадения и решают ее с помощью пропагации ограничений и аккуратно выбранного поиска в глубину.
Обозначим неизвестный код через \(x=(x_1,\dots,x_{16})\), где каждое \(x_i\in\{0,\dots,9\}\). Для подсказки номер \(t\) запишем предложенную строку как \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\), а требуемое число точных совпадений как \(m_t\). Тогда каждая подсказка задает ограничение
$$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$$
Иначе говоря, расстояние Хэмминга между секретом и подсказкой \(t\) равно \(16-m_t\). Поиск устроен так, чтобы хранить не целые коды-кандидаты, а частичную информацию о том, могут ли все 22 равенства еще быть выполнены одновременно.
На каждом шаге позиции \(i\) соответствует текущее допустимое множество \(A_i\subseteq\{0,\dots,9\}\). Если \(A_i=\{d\}\), то цифра в этой позиции уже принудительно равна \(d\). Если \(|A_i|\gt 1\), позиция пока не определена.
Именно такое описание состояния естественно для Number Mind, потому что каждая подсказка говорит только о конкретной цифре в конкретной позиции. Поэтому подсказка с \(m_t=0\) дает мгновенный вывод: для каждого \(i\) цифра \(g_i^{(t)}\) удаляется из \(A_i\). В полном 16-значном экземпляре одна эта строка сразу создает 16 позиционных запретов.
Зафиксируем одну подсказку \(t\). По текущим множествам \(A_i\) определим
$$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|.$$
Здесь \(f_t\) считает позиции, уже принудительно совпадающие с подсказкой \(t\), а \(c_t\) считает еще не зафиксированные позиции, которые все еще могут с ней совпасть. Любое продолжение текущего состояния обязано удовлетворять инварианту
$$f_t\le m_t\le f_t+c_t.$$
Если \(f_t\gt m_t\), то мы уже совпали слишком много раз. Если \(f_t+c_t\lt m_t\), то даже при максимальном числе оставшихся совпадений до цели не дотянуться. В обоих случаях ветвь невозможна и отсекается сразу. Это центральная проверка, удерживающая поиск в допустимой области.
Та же самая оценка дает сильные детерминированные ходы. Если \(f_t=m_t\), то подсказка \(t\) уже исчерпала все допустимые совпадения, и каждая другая кандидатная позиция для этой подсказки должна стать несовпадением. Значит, цифру \(g_i^{(t)}\) можно удалить из соответствующего \(A_i\).
Если же \(f_t+c_t=m_t\), то каждая еще возможная позиция совпадения на самом деле обязательна, и такие позиции принудительно фиксируются в цифры подсказки. Есть и чисто позиционное следствие: как только какое-то множество \(A_i\) сжимается до одного элемента, цифра в этой позиции фиксируется немедленно. Повторение всех этих выводов и образует фазу пропагации.
Для подсказки \(t\) обозначим
$$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t.$$
Любое допустимое решение должно выбрать ровно \(r_t\) позиций из \(C_t\), которые в итоге совпадут с подсказкой \(t\); остальные позиции из \(C_t\) обязаны не совпасть. Следовательно, эта подсказка естественным образом задает
$$\binom{|C_t|}{r_t}$$
возможных подмножеств. Это гораздо точнее, чем пробовать цифры по одной позиции, потому что один выбор ветви сразу вводит несколько равенств и несколько неравенств.
Поэтому эвристика выбирает ту подсказку, у которой биномиальный фактор ветвления минимален. После выбора подмножества \(S\subseteq C_t\) с \(|S|=r_t\) позиции из \(S\) принудительно ставятся равными цифрам подсказки, а в позициях из \(C_t\setminus S\) эти цифры запрещаются. Затем снова запускаются проверки выполнимости и пропагация одиночных вариантов.
Пятизначный пример из условия содержит подсказки 90342 с 2 точными совпадениями, 70794 с 0, 39458 с 2, 34109 с 1, 51545 с 2 и 12531 с 1. Подсказка 70794 с нулевым числом совпадений немедленно запрещает цифру 7 в позициях 1 и 3, цифру 0 в позиции 2, цифру 9 в позиции 4 и цифру 4 в позиции 5.
Теперь посмотрим на подсказку 90342 с целью 2. Поскольку во второй позиции уже нельзя ставить 0, совпасть с этой подсказкой все еще могут только позиции \(1,3,4,5\). Значит, \(|C_t|=4\), и число вариантов ветвления равно \(\binom{4}{2}=6\). Для подсказки 34109 с целью 1 кандидатными остаются все пять позиций, так что ее фактор ветвления равен \(\binom{5}{1}=5\). Он меньше, поэтому именно такая строка лучше подходит для первого разбиения поиска.
Если продолжать точно тем же рассуждением, получается единственное решение образца: \(39542\). Проверка по шести примерным подсказкам дает числа совпадений \(2,0,2,1,2,1\), так что образец полностью отражает математику полного 16-значного случая, только в меньшем масштабе.
Реализации на C++, Python и Java хранят частичное 16-значное присваивание вместе с таблицей запрещенных цифр размера \(16\times 10\). Подсказки сортируются по требуемому числу совпадений, поэтому наиболее жесткие строки, особенно строка с нулем совпадений и строки с одним совпадением, попадают в работу раньше. До запуска рекурсии каждая подсказка с нулем совпадений сразу применяется как покоординатный запрет.
Каждый рекурсивный вызов сначала выполняет пропагацию одиночных вариантов: если в какой-то позиции осталась только одна допустимая цифра, она фиксируется. Затем все подсказки заново просматриваются, чтобы вычислить текущие значения \(f_t\) и \(c_t\). Если какая-либо подсказка нарушает условие \(f_t\le m_t\le f_t+c_t\), ветвь немедленно отбрасывается.
Особенно важны насыщенные случаи \(r_t=0\) и \(r_t=|C_t|\). Они означают, что у подсказки больше нет свободы: либо все оставшиеся кандидаты должны оказаться несовпадениями, либо все они обязаны совпасть. Общая логика поиска обрабатывает оба случая естественно, потому что в них остается ровно одна подветвь, а одна из реализаций дополнительно делает первый случай явным шагом пропагации.
Если все 16 позиций еще не зафиксированы, программа вычисляет \(\binom{|C_t|}{r_t}\) для каждой подсказки и ветвится по минимальному значению. Ветка здесь не означает «угадать очередную цифру»; она означает «выбрать, какие именно позиции данной подсказки являются оставшимися совпадениями». Такой шаг обычно меняет сразу несколько позиций и почти сразу вызывает новую волну вывода.
Когда все 16 позиций уже заданы, получившийся код дополнительно проверяется по всем 22 подсказкам. Известно, что вход имеет единственное решение, и структура поиска это подчеркивает: версия на C++ продолжает поиск до тех пор, пока не станет ясно, существует ли второе решение, тогда как две другие реализации на этом единственном входе останавливаются на первой полной согласованной конфигурации.
В худшем случае это по-прежнему экспоненциальный поиск с возвратом. Для произвольных систем ограничений вида «точное число позиционных совпадений» нет общей полиномиальной оценки времени, а наивное пространство кандидатов начинается с \(10^{16}\) кодов. Выигрыш достигается исключительно за счет сильного отсечения, а не за счет изменения теоретического класса задачи.
Для данной конкретной задачи каждый узел дерева дешев. Есть только \(G=22\) подсказки и \(L=16\) позиций, поэтому полный проход по условию выполнимости стоит \(O(GL)\), то есть здесь это просто повторный просмотр очень маленькой таблицы. Основную цену задает число рекурсивных состояний, но предварительная обработка нулевой строки, пропагация одиночных вариантов, оценки выполнимости и правило минимального \(\binom{|C_t|}{r_t}\) резко сокращают дерево поиска.
Памяти нужно немного. Один активный рекурсивный путь хранит частичное присваивание и таблицу запрещенных цифр, поэтому рабочее состояние имеет размер \(O(16\cdot 10)\), а глубина рекурсии не превышает 16. Практическая эффективность появляется потому, что программа рассуждает сразу о целых строках подсказок, а не перебирает коды цифра за цифрой.
تطلب مسألة Project Euler 185 إيجاد شيفرة سرية مكوّنة من 16 رقمًا وتحقق في الوقت نفسه 22 تلميحًا. كل تلميح عبارة عن سلسلة أخرى من 16 رقمًا ومعها عدد يحدد كم موضعًا يطابق الشيفرة تمامًا. يمكن أن تتكرر الأرقام، ولا يُحسب إلا التطابق من نوع «الرقم الصحيح في الموضع الصحيح»؛ أما الرقم الصحيح في موضع آخر فلا يمنح أي تطابق. وهناك تلميح قوي جدًا يقول إن 2321386104303845 لا يطابق الشيفرة في أي موضع، ولذلك يبدأ البحث أصلًا مع رقم محظور واحد في كل موضع.
العدّ الشامل يعني فحص ما يصل إلى \(10^{16}\) شيفرة ممكنة، وهذا غير عملي تمامًا. لذلك تتعامل التطبيقات مع المسألة بوصفها نظامًا صغيرًا لكنه شديد الصرامة من معادلات التطابق الدقيق، ثم تحل هذا النظام بالاستنتاج التدريجي والبحث المتشعب المحدود بعناية.
لنرمز إلى الشيفرة المجهولة بـ \(x=(x_1,\dots,x_{16})\)، حيث إن كل \(x_i\in\{0,\dots,9\}\). ولْنكتب التلميح رقم \(t\) على الصورة \(g^{(t)}=(g_1^{(t)},\dots,g_{16}^{(t)})\)، ولنرمز إلى عدد التطابقات الدقيقة المطلوبة فيه بالرمز \(m_t\). عندئذٍ يفرض كل تلميح القيد
$$\sum_{i=1}^{16}\mathbf{1}[x_i=g_i^{(t)}]=m_t,\qquad t=1,\dots,22.$$
وبصيغة مكافئة، فإن مسافة Hamming بين الشيفرة والتلميح \(t\) تساوي \(16-m_t\). البحث لا يحاول تخمين الشيفرة كاملة دفعة واحدة، بل يحتفظ بمعلومة جزئية عن هذه المعادلات الـ 22 ويستبعد كل حالة لم يعد ممكنًا أن تحققها جميعًا معًا.
في أي لحظة من البحث يكون لكل موضع \(i\) مجموعة مسموحة حالية \(A_i\subseteq\{0,\dots,9\}\). إذا كان \(A_i=\{d\}\)، فهذا يعني أن ذلك الموضع قد ثبت بالفعل على الرقم \(d\). وإذا كان \(|A_i|\gt 1\)، فالخانة ما تزال غير محسومة.
هذا هو فضاء الحالات المناسب لمسألة Number Mind، لأن كل تلميح يتحدث فقط عن رقم محدد في موضع محدد. ولذلك فإن أي تلميح له \(m_t=0\) يعطي معلومة فورية: لكل موضع \(i\) يُحذف الرقم \(g_i^{(t)}\) من المجموعة \(A_i\). وفي النسخة الكاملة ذات 16 رقمًا، ينتج من هذا السطر الواحد 16 حظرًا موضعيًا قبل أي تشعب.
لنثبت تلميحًا واحدًا \(t\). انطلاقًا من المجموعات الحالية \(A_i\)، نعرّف
$$f_t=\left|\{i:A_i=\{g_i^{(t)}\}\}\right|,\qquad c_t=\left|\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\}\right|.$$
يمثل \(f_t\) عدد المواضع التي صار تطابقها مع التلميح \(t\) مؤكدًا بالفعل، بينما يمثل \(c_t\) عدد المواضع غير المحسومة التي ما زال يمكنها أن تطابق ذلك التلميح. أي إكمال صالح للحالة الحالية يجب أن يحقق المتباينة
$$f_t\le m_t\le f_t+c_t.$$
إذا كان \(f_t\gt m_t\)، فهذا يعني أننا تجاوزنا عدد التطابقات المسموح بها لهذا التلميح. وإذا كان \(f_t+c_t\lt m_t\)، فهذا يعني أن كل المرشحين الباقين، حتى لو طابقوا، لا يكفون للوصول إلى العدد المطلوب. وفي كلتا الحالتين يكون الفرع مستحيلًا ويُستبعد فورًا. هذه المتباينة هي الاختبار الرياضي المركزي في البحث كله.
المتباينة نفسها تعطي استنتاجات حتمية قوية. فإذا تحقق \(f_t=m_t\)، فهذا يعني أن التلميح \(t\) استنفد جميع تطابقاته المسموح بها، وبالتالي فإن كل موضع مرشح آخر لهذا التلميح يجب أن يتحول إلى عدم تطابق، ومن ثم يمكن حذف الرقم \(g_i^{(t)}\) من \(A_i\).
أما إذا تحقق \(f_t+c_t=m_t\)، فكل تطابق لا يزال ممكنًا يصبح تطابقًا مفروضًا، فتثبت تلك المواضع جميعًا على أرقام التلميح. وهناك نتيجة قسرية أخرى ناتجة من المواضع نفسها: إذا تقلصت مجموعة \(A_i\) إلى عنصر واحد فقط، فإن ذلك الرقم يثبت فورًا في هذا الموضع. وتكرار هذه الاستنتاجات هو بالضبط ما تقوم به مرحلة الانتشار.
بالنسبة إلى التلميح \(t\)، نكتب
$$C_t=\{i:|A_i|\gt 1,\ g_i^{(t)}\in A_i\},\qquad r_t=m_t-f_t.$$
أي حل صحيح يجب أن يختار بالضبط \(r_t\) مواضع من \(C_t\) لتكون هي المواضع التي ستطابق التلميح \(t\) في النهاية، بينما يجب أن تفشل بقية المواضع في \(C_t\) في هذا التطابق. ولذلك يعطي هذا التلميح بطبيعته
$$\binom{|C_t|}{r_t}$$
احتمالًا مختلفًا. وهذا أدق بكثير من تجربة الأرقام موضعًا موضعًا، لأن قرار تشعب واحد يمكن أن يفرض عدة مساويات وعدة لا مساويات دفعة واحدة.
ومن هنا تأتي القاعدة الاسترشادية: نختار التلميح الذي يملك أصغر عامل تشعب ثنائي الحد. فإذا اخترنا مجموعة فرعية \(S\subseteq C_t\) بحيث \(|S|=r_t\)، فإن مواضع \(S\) تُجبر على أرقام التلميح، أما مواضع \(C_t\setminus S\) فتُمنع من أخذ تلك الأرقام. وبعد ذلك تُعاد فحوص القابلية للتحقق وانتشار الخانات الأحادية.
المثال الصغير في نص المسألة يحتوي على التلميحات التالية: 90342 مع تطابقين دقيقين، و70794 مع صفر، و39458 مع تطابقين، و34109 مع تطابق واحد، و51545 مع تطابقين، و12531 مع تطابق واحد. التلميح ذو الصفر 70794 يمنع مباشرة الرقم 7 في الموضعين 1 و3، والرقم 0 في الموضع 2، والرقم 9 في الموضع 4، والرقم 4 في الموضع 5.
لننظر الآن إلى التلميح 90342 الذي يحتاج إلى تطابقين. بما أن الموضع 2 لم يعد يمكن أن يكون 0، فإن المواضع \(1,3,4,5\) فقط ما تزال قادرة على مطابقة هذا التلميح. لذا يكون \(|C_t|=4\) ويصبح عدد الفروع \(\binom{4}{2}=6\). أما التلميح 34109 الذي يحتاج إلى تطابق واحد، فما تزال المواضع الخمسة كلها مرشحة له، ولذلك يكون عامل تشعبه \(\binom{5}{1}=5\). وهذا أصغر قليلًا، ولذلك يكون هو الاختيار الأفضل للتشعب أولًا.
ومع متابعة المنطق نفسه نحصل على الحل الوحيد للمثال وهو \(39542\). وعند فحصه مقابل التلميحات الستة نحصل على أعداد التطابق \(2,0,2,1,2,1\) تمامًا، لذلك يمثل هذا المثال نسخة مصغرة كاملة من آلية المسألة الأصلية ذات 16 خانة.
تحتفظ تطبيقات C++ وPython وJava بتعيين جزئي مكوّن من 16 خانة، ومعه جدول حظر للأرقام حجمه \(16\times 10\). وتُرتب التلميحات حسب عدد التطابقات المطلوبة، بحيث تظهر الصفوف الأكثر تقييدًا، وبخاصة صف الصفر وصفوف الواحد، في وقت مبكر من البحث. وقبل أن يبدأ الاستدعاء التراجعي، يُطبَّق كل تلميح ذي صفر تطابق على الفور بوصفه حظرًا موضعيًا مباشرًا.
تبدأ كل خطوة عودية بانتشار الخانات الأحادية: إذا بقي رقم واحد فقط مسموحًا في موضع ما، يثبت ذلك الرقم مباشرة. بعد ذلك يُعاد مسح جميع التلميحات لحساب القيم الحالية لـ \(f_t\) و\(c_t\). وإذا خالف أي تلميح الشرط \(f_t\le m_t\le f_t+c_t\)، يُهمل ذلك الفرع فورًا.
الحالتان \(r_t=0\) و\(r_t=|C_t|\) مهمتان جدًا. فهما تعنيان أن التلميح لم يعد يملك أي حرية: إما أن جميع المرشحين الباقين يجب أن يكونوا عدم تطابق، أو يجب أن يكونوا جميعًا تطابقًا. ويعالج إطار البحث المشترك الحالتين طبيعيًا لأن كل واحدة منهما تترك مجموعة فرعية واحدة فقط، كما أن إحدى التطبيقات تطبق الحالة الأولى صراحة كجولة انتشار إضافية.
إذا لم تكن الخانات الست عشرة قد حُسمت كلها بعد، تحسب الشيفرة \(\binom{|C_t|}{r_t}\) لكل تلميح وتتشعب عند أصغر قيمة. والفرع هنا ليس «تخمين رقم جديد»، بل «تحديد أي المواضع ضمن هذا التلميح تمثل التطابقات المتبقية». وغالبًا ما يغير هذا عدة مواضع دفعة واحدة، فيؤدي مباشرة إلى انتشار إضافي.
وعندما تثبت جميع الخانات الست عشرة، يُفحص المرشح الناتج مرة أخرى مقابل جميع التلميحات الـ 22. هذه المسألة معروفة بامتلاكها حلًا وحيدًا، وبنية البحث تعكس ذلك: تنفيذ C++ يواصل البحث حتى يتضح ما إذا كان يمكن أن يظهر حل ثانٍ، بينما يكتفي التنفيذان الآخران في هذا الإدخال ذي الحل الوحيد بأول إكمال متسق.
في أسوأ الأحوال يبقى هذا بحثًا تراجعيًا أسيًا. فأنظمة القيود من نوع «عدد دقيق من التطابقات الموضعية» لا تملك عمومًا ضمانًا بزمن كثير الحدود، والفضاء الساذج للبحث يبدأ من \(10^{16}\) شيفرة محتملة. ما يجعل الطريقة عملية هو قوة التقليص، لا تغير طبيعة أسوأ حالة نظريًا.
لكن كل عقدة بحث في هذه المسألة رخيصة نسبيًا. فلدينا فقط \(G=22\) تلميحًا و\(L=16\) موضعًا، ولذلك فإن فحص القابلية الكامل يكلف \(O(GL)\)، وهو هنا مجرد مرور على جدول صغير جدًا. الكلفة الحقيقية تكمن في عدد الحالات العودية، غير أن المعالجة المسبقة لصف الصفر، وانتشار الخانات الأحادية، وحدود القابلية، وقاعدة اختيار أصغر \(\binom{|C_t|}{r_t}\) تقلص شجرة البحث بدرجة كبيرة.
أما الذاكرة فتبقى محدودة. فمسار عودي نشط واحد يحتاج إلى التعيين الجزئي وجدول الأرقام المحظورة، أي حالة عمل بحجم \(O(16\cdot 10)\)، مع عمق عودية لا يتجاوز 16. والسبب العملي لنجاح الطريقة هو أنها تستنتج من صفوف التلميحات كاملة بدل أن تجرب الشيفرات رقمًا رقمًا بصورة عمياء.