The input consists of 50 standard Sudoku grids. Each grid is a \(9 \times 9\) array with digits \(0\) through \(9\), where \(0\) marks an empty cell. After solving a grid, the required contribution is the three-digit number formed by the first three entries of the top row.
If the completed grid is written as \(x_{r,c}\) for \(1 \le r,c \le 9\), then one puzzle contributes
$$100x_{1,1}+10x_{1,2}+x_{1,3}.$$
The final answer is the sum of this quantity over all 50 solved grids. The real work is therefore to complete each partially filled grid while respecting the Sudoku rules: every row, every column, and every \(3 \times 3\) box must contain each digit from 1 to 9 exactly once.
The implementations treat Sudoku as a finite search problem with a very strict legality invariant. At every recursive step, the current board is a partial completion that already agrees with all row, column, and box constraints.
For a partially filled grid, define the used-digit sets
$$R_r=\{x_{r,c}\ne 0:1\le c\le 9\},\qquad C_c=\{x_{r,c}\ne 0:1\le r\le 9\},$$
and for each box
$$B_b=\{x_{r,c}\ne 0:b(r,c)=b\}.$$
A box is identified by
$$b(r,c)=3\left\lfloor\frac{r-1}{3}\right\rfloor+\left\lfloor\frac{c-1}{3}\right\rfloor+1.$$
The essential invariant is simple: no nonzero digit may appear twice inside the same \(R_r\), the same \(C_c\), or the same \(B_b\). Any recursive branch that would violate this invariant can be discarded immediately.
For an empty position \((r,c)\), the allowable digits are exactly
$$A(r,c)=\{1,2,\dots,9\}\setminus\bigl(R_r\cup C_c\cup B_{b(r,c)}\bigr).$$
This set is the mathematical core of the solver. If \(A(r,c)=\varnothing\), the current partial grid cannot be extended to a full solution. If \(|A(r,c)|=1\), the placement is forced. Otherwise the solver must branch on the candidates in \(A(r,c)\).
The C++ implementation stores these used-digit sets as bit patterns, so the candidate set is recovered with bitwise operations. The Python and Java implementations compute the same set more directly by scanning the corresponding row, column, and box whenever they test a trial digit.
Let \(S\) be a legal partial Sudoku state. If there are no empty cells left, then \(S\) is already a complete solution. Otherwise choose one empty cell \(u\), compute its candidate set \(A(u)\), and try each legal digit in turn. In logical form, the search is
$$\operatorname{Solve}(S)=\bigvee_{d\in A(u)} \operatorname{Solve}(S[u\leftarrow d]).$$
Here \(S[u\leftarrow d]\) means the new state after writing digit \(d\) into cell \(u\). A branch returns failure as soon as some empty cell has no legal digit left.
The C++ implementation improves this recurrence by choosing the empty cell with the smallest candidate set, which reduces the branching factor. The Python and Java implementations keep a list of empty cells and recurse through that list in order. Both strategies enumerate only legal completions, and backtracking guarantees completeness because every admissible digit assignment is eventually explored unless a solution is found earlier.
One built-in checkpoint uses a nearly complete grid whose first row is
$$[0,3,4,6,7,8,9,1,2].$$
The missing entry is \(x_{1,1}\). Row 1 is missing only the digit 5. Column 1 contains
$$[0,6,1,8,4,7,9,2,3],$$
so that column is also missing only 5. The upper-left \(3\times 3\) box contains
$$[0,3,4;\ 6,7,2;\ 1,9,8],$$
which again excludes every digit except 5. Therefore
$$A(1,1)=\{5\},\qquad x_{1,1}=5.$$
Once that forced move is made, the top-left three-digit value is
$$100\cdot 5+10\cdot 3+4=534.$$
This small example shows exactly how the solver reasons: legal digits are determined by row, column, and box exclusions, and forced cells collapse immediately before any deeper branching is needed.
All three implementations read the 50 grids, solve each grid independently, and add the quantity \(100x_{1,1}+10x_{1,2}+x_{1,3}\) to a running total. The recursion updates the board in place, and a failed branch is undone before trying the next candidate.
Each implementation parses the nine text rows of a puzzle into a \(9 \times 9\) board. Empty cells are represented by zeroes. Once a solution is found, the first three cells of the top row are read and converted into the required three-digit contribution.
The C++ implementation first checks that the given clues do not already violate Sudoku constraints. It maintains row, column, and box occupancy masks, recomputes candidate masks efficiently, and at each recursive level chooses the still-empty cell with the fewest legal digits. The Python and Java implementations instead store the empty positions once and recurse through them in order; legality is tested by direct scans of the row, column, and \(3\times 3\) box for each trial digit. Mathematically the search tree is the same kind of backtracking tree, but the C++ version prunes it more aggressively.
If a grid has \(m\) empty cells, the worst-case search tree has branching factor at most 9 and depth \(m\), so the crude upper bound is \(O(9^m)\). That is the unavoidable exponential behavior of generic backtracking on Sudoku constraints.
Inside one recursive step, the bookkeeping is constant-time on a fixed \(9 \times 9\) board. In the Python and Java implementations, checking one tentative digit means scanning at most 9 cells in the row, 9 in the column, and 9 in the box. In the C++ implementation, candidate computation is bitwise, but it also scans the board to find the empty cell with minimum candidate count. Memory usage is \(O(m)\) for the recursion stack, plus the fixed board representation and the auxiliary row, column, and box state.
Because the board size is fixed and there are only 50 puzzles, the practical running time is small even though the worst-case search bound is exponential.
Die Eingabe besteht aus 50 klassischen Sudoku-Gittern. Jedes Gitter ist ein \(9 \times 9\)-Raster mit Ziffern von \(0\) bis \(9\), wobei \(0\) eine leere Zelle bedeutet. Nach dem Lösen eines Gitters liefert die dreistellige Zahl aus den ersten drei Einträgen der obersten Zeile den Beitrag dieses Rätsels.
Schreibt man das gelöste Gitter als \(x_{r,c}\) mit \(1 \le r,c \le 9\), dann ist der Beitrag
$$100x_{1,1}+10x_{1,2}+x_{1,3}.$$
Gesucht ist die Summe dieser Werte über alle 50 Sudokus. Der eigentliche Kern des Problems ist also nicht die Schlussaddition, sondern das saubere Vervollständigen jedes teilweise gefüllten Gitters unter den drei Sudoku-Bedingungen: jede Zeile, jede Spalte und jeder \(3\times 3\)-Block muss die Ziffern 1 bis 9 genau einmal enthalten.
Die Implementierungen behandeln Sudoku als endliches Suchproblem mit einer klaren Invariante: In jedem rekursiven Zustand ist das bisher gefüllte Teilgitter bereits mit allen Zeilen-, Spalten- und Blockbedingungen verträglich.
Für ein teilweise gefülltes Gitter definieren wir die Mengen der bereits verwendeten Ziffern
$$R_r=\{x_{r,c}\ne 0:1\le c\le 9\},\qquad C_c=\{x_{r,c}\ne 0:1\le r\le 9\},$$
sowie für jeden Block
$$B_b=\{x_{r,c}\ne 0:b(r,c)=b\}.$$
Der zugehörige Blockindex ist
$$b(r,c)=3\left\lfloor\frac{r-1}{3}\right\rfloor+\left\lfloor\frac{c-1}{3}\right\rfloor+1.$$
Die zentrale Invariante lautet: Keine von null verschiedene Ziffer darf zweimal in derselben Zeile, derselben Spalte oder demselben Block vorkommen. Sobald ein Suchzweig diese Bedingung verletzt, kann er verworfen werden.
Für eine leere Position \((r,c)\) sind genau die Ziffern erlaubt, die noch in keiner der drei relevanten Strukturen vorkommen:
$$A(r,c)=\{1,2,\dots,9\}\setminus\bigl(R_r\cup C_c\cup B_{b(r,c)}\bigr).$$
Diese Menge ist das mathematische Herz des Solvers. Gilt \(A(r,c)=\varnothing\), dann ist der aktuelle Teilzustand unlösbar. Gilt \(|A(r,c)|=1\), dann ist der Eintrag erzwungen. Andernfalls muss der Algorithmus über die Elemente von \(A(r,c)\) verzweigen.
In C++ werden die verwendeten Ziffern als Bitmasken gespeichert, so dass sich die Kandidatenmenge mit bitweisen Operationen ergibt. Die Python- und Java-Implementierungen berechnen dieselbe Menge direkter, indem sie bei jedem Versuch Zeile, Spalte und Block absuchen.
Sei \(S\) ein zulässiger partieller Sudoku-Zustand. Wenn keine leere Zelle mehr existiert, ist \(S\) bereits eine vollständige Lösung. Sonst wählen wir eine leere Zelle \(u\), bestimmen \(A(u)\) und probieren jede erlaubte Ziffer aus. Logisch lässt sich das als
$$\operatorname{Solve}(S)=\bigvee_{d\in A(u)} \operatorname{Solve}(S[u\leftarrow d])$$
schreiben. Hier bezeichnet \(S[u\leftarrow d]\) den Zustand nach dem Eintragen von \(d\) in \(u\). Ein Zweig scheitert sofort, sobald für irgendeine leere Zelle keine legale Ziffer mehr übrig bleibt.
Die C++-Implementierung verbessert diese Rekursion, indem sie jeweils die leere Zelle mit der kleinsten Kandidatenmenge wählt. Dadurch sinkt der Verzweigungsgrad typischerweise deutlich. Die Python- und Java-Implementierungen arbeiten dagegen eine vorbereitete Liste leerer Zellen der Reihe nach ab. Beide Strategien durchsuchen ausschließlich legale Fortsetzungen, und Backtracking ist vollständig, weil jede zulässige Belegung irgendwann ausprobiert wird, sofern nicht vorher schon eine Lösung gefunden ist.
Ein eingebauter Prüffall verwendet ein fast vollständiges Gitter, dessen erste Zeile
$$[0,3,4,6,7,8,9,1,2]$$
lautet. Gesucht ist also \(x_{1,1}\). In Zeile 1 fehlt nur die Ziffer 5. Spalte 1 enthält
$$[0,6,1,8,4,7,9,2,3],$$
also fehlt auch dort nur die 5. Im linken oberen \(3\times 3\)-Block stehen
$$[0,3,4;\ 6,7,2;\ 1,9,8],$$
und wiederum bleibt nur die 5 übrig. Daher gilt
$$A(1,1)=\{5\},\qquad x_{1,1}=5.$$
Damit lautet die gesuchte dreistellige Zahl links oben
$$100\cdot 5+10\cdot 3+4=534.$$
Dieses kleine Beispiel zeigt genau die Denkweise des Solvers: Kandidaten entstehen durch Ausschluss in Zeile, Spalte und Block, und erzwungene Zellen werden sofort festgelegt, bevor tiefere Verzweigungen nötig werden.
Alle drei Implementierungen lesen die 50 Gitter ein, lösen jedes Gitter separat und addieren jeweils \(100x_{1,1}+10x_{1,2}+x_{1,3}\) zum Gesamtergebnis. Die Rekursion verändert das Brett direkt; schlägt ein Zweig fehl, werden die Änderungen rückgängig gemacht, bevor der nächste Kandidat versucht wird.
Jede Implementierung wandelt die neun Textzeilen eines Rätsels in ein \(9\times 9\)-Brett um. Leere Felder werden als Nullen gespeichert. Sobald eine Lösung vorliegt, werden die ersten drei Zellen der oberen Zeile gelesen und in die geforderte dreistellige Zahl umgerechnet.
Die C++-Implementierung prüft zuerst, ob die vorgegebenen Hinweise bereits gegen die Sudoku-Regeln verstoßen. Danach verwaltet sie Zeilen-, Spalten- und Blockmasken, berechnet Kandidaten per Bitoperation und wählt in jeder Rekursionstiefe die aktuell am stärksten eingeschränkte leere Zelle. Die Python- und Java-Implementierungen speichern die leeren Positionen einmalig und durchlaufen diese Liste rekursiv; die Gültigkeit eines Probedigits wird jeweils durch direktes Prüfen von Zeile, Spalte und \(3\times 3\)-Block festgestellt. Mathematisch bleibt es derselbe Backtracking-Baum, aber die C++-Variante schneidet ihn aggressiver zurück.
Hat ein Gitter \(m\) leere Zellen, dann besitzt der Suchbaum im schlimmsten Fall Verzweigungsgrad höchstens 9 und Tiefe \(m\). Damit erhält man die grobe obere Schranke \(O(9^m)\). Dieses exponentielle Verhalten ist die typische Worst-Case-Schranke für generisches Backtracking unter Sudoku-Bedingungen.
Innerhalb eines Rekursionsschritts sind die Operationen auf einem festen \(9\times 9\)-Brett konstant. In Python und Java bedeutet ein Kandidatentest höchstens 9 Prüfungen in der Zeile, 9 in der Spalte und 9 im Block. In C++ ist die Kandidatenbestimmung bitweise, dafür wird zusätzlich das Brett abgesucht, um die leere Zelle mit der kleinsten Kandidatenzahl zu finden. Der Speicherbedarf beträgt \(O(m)\) für den Rekursionsstapel plus die feste Brettrepräsentation und den zusätzlichen Zustand für Zeilen, Spalten und Blöcke.
Da die Brettgröße fest ist und nur 50 Rätsel gelöst werden müssen, bleibt die praktische Laufzeit klein, obwohl die theoretische Schranke exponentiell ist.
Girdi 50 adet klasik Sudoku ızgarasından oluşur. Her ızgara \(9 \times 9\) boyutundadır; \(0\) değeri boş hücreyi gösterir. Bir ızgara çözüldükten sonra o bulmacanın katkısı, üst satırın ilk üç hücresinden oluşan üç basamaklı sayıdır.
Tamamlanmış ızgarayı \(x_{r,c}\) ile gösterirsek \((1 \le r,c \le 9)\), tek bir bulmacanın katkısı
$$100x_{1,1}+10x_{1,2}+x_{1,3}$$
şeklindedir. Nihai sonuç, 50 çözümlü ızgara için bu değerin toplamıdır. Dolayısıyla asıl mesele son toplama değil, her kısmi ızgarayı Sudoku kurallarına sadık kalarak tamamlamaktır: her satır, her sütun ve her \(3\times 3\) kutu 1'den 9'a kadar tüm rakamları tam birer kez içermelidir.
Uygulamalar Sudoku’yu sonlu bir arama problemi olarak ele alır. Her özyinelemeli çağrıda korunan temel değişmez şudur: o ana kadar yazılmış bütün rakamlar satır, sütun ve kutu kısıtlarıyla zaten uyumludur.
Kısmen doldurulmuş bir ızgara için kullanılan rakam kümelerini
$$R_r=\{x_{r,c}\ne 0:1\le c\le 9\},\qquad C_c=\{x_{r,c}\ne 0:1\le r\le 9\}$$
ve her kutu için
$$B_b=\{x_{r,c}\ne 0:b(r,c)=b\}$$
diye tanımlayalım. Kutu indeksi
$$b(r,c)=3\left\lfloor\frac{r-1}{3}\right\rfloor+\left\lfloor\frac{c-1}{3}\right\rfloor+1$$
ile bulunur. Korunan değişmez şudur: sıfır dışındaki hiçbir rakam aynı \(R_r\), aynı \(C_c\) ya da aynı \(B_b\) içinde iki kez görünemez. Bir dal bu koşulu bozduğu anda artık devam ettirilmez.
Boş bir \((r,c)\) konumu için yazılabilecek rakamlar tam olarak
$$A(r,c)=\{1,2,\dots,9\}\setminus\bigl(R_r\cup C_c\cup B_{b(r,c)}\bigr)$$
kümesidir. Çözücünün matematiksel özü bu kümedir. Eğer \(A(r,c)=\varnothing\) ise mevcut kısmi durumdan geçerli bir tam çözüm çıkamaz. Eğer \(|A(r,c)|=1\) ise hücre zorunlu olarak doldurulmuştur. Aksi durumda algoritma \(A(r,c)\) içindeki seçenekler arasında dallanır.
C++ uygulaması kullanılan rakam kümelerini bit maskeleriyle tuttuğu için adayları bit işlemleriyle hızlıca çıkarır. Python ve Java uygulamaları ise aynı mantığı daha doğrudan uygular; denenen rakamın aynı satırda, sütunda ve kutuda bulunup bulunmadığını tarayarak kontrol eder.
\(S\) yasal bir kısmi Sudoku durumu olsun. Eğer boş hücre kalmamışsa \(S\) zaten tam çözümdür. Aksi halde boş hücrelerden biri \(u\) seçilir, \(A(u)\) hesaplanır ve her aday sırayla denenir. Mantıksal olarak arama
$$\operatorname{Solve}(S)=\bigvee_{d\in A(u)} \operatorname{Solve}(S[u\leftarrow d])$$
biçimindedir. Burada \(S[u\leftarrow d]\), \(u\) hücresine \(d\) yazıldıktan sonraki yeni durumu gösterir. Herhangi bir aşamada bir boş hücre için hiç aday kalmazsa o dal başarısız olur.
C++ sürümü bu bağıntıyı daha verimli kullanmak için her adımda aday sayısı en küçük olan boş hücreyi seçer; böylece dallanma faktörü küçülür. Python ve Java sürümleri ise boş hücre listesini baştan çıkarır ve bu listedeki sırayı izler. İki yaklaşım da yalnızca yasal tamamlamaları dener; geri izleme tamdır çünkü daha erken bir çözüm bulunmadığı sürece her izinli atama eninde sonunda incelenir.
Dahili bir kontrol örneğinde ilk satır
$$[0,3,4,6,7,8,9,1,2]$$
şeklindedir. Aranan değer \(x_{1,1}\)'dir. 1. satırda eksik olan tek rakam 5'tir. 1. sütun
$$[0,6,1,8,4,7,9,2,3]$$
olduğundan sütunda da eksik olan tek rakam 5'tir. Sol üst \(3\times 3\) kutuda ise
$$[0,3,4;\ 6,7,2;\ 1,9,8]$$
bulunur; burada da izin verilen tek rakam yine 5'tir. Demek ki
$$A(1,1)=\{5\},\qquad x_{1,1}=5.$$
Böylece sol üstteki üç basamaklı sayı
$$100\cdot 5+10\cdot 3+4=534$$
olur. Bu küçük örnek çözücünün mantığını birebir gösterir: adaylar satır, sütun ve kutu dışlamalarından doğar; zorunlu hücreler ise derin dallanmaya gerek kalmadan hemen belirlenir.
Üç uygulama da 50 ızgarayı okur, her ızgarayı bağımsız çözer ve \(100x_{1,1}+10x_{1,2}+x_{1,3}\) değerini toplam sonuca ekler. Özyineleme sırasında tahta yerinde güncellenir; bir dal başarısız olursa sonraki adayı denemeden önce yapılan atama geri alınır.
Her uygulama, bulmacanın dokuz metin satırını \(9\times 9\) bir tabloya dönüştürür. Boş hücreler sıfır olarak saklanır. Çözüm tamamlandığında üst satırın ilk üç hücresi okunur ve istenen üç basamaklı katkıya çevrilir.
C++ uygulaması önce verilen ipuçlarının Sudoku kurallarını baştan ihlal etmediğini kontrol eder. Sonra satır, sütun ve kutu durumlarını bit maskeleriyle tutar; adayları hızlı biçimde hesaplar ve her özyinelemeli seviyede aday sayısı en az olan boş hücreyi seçer. Python ve Java uygulamaları ise boş konumları bir kez listeleyip bu sırayla ilerler; her deneme için satır, sütun ve \(3\times 3\) kutu doğrudan taranarak geçerlilik sınanır. Matematiksel olarak ağaç aynı tür geri izleme ağacıdır, fakat C++ sürümü daha güçlü budama yapar.
Bir ızgarada \(m\) boş hücre varsa arama ağacının derinliği \(m\), her düğümdeki dallanma sayısı en fazla 9 olabilir. Bu nedenle kaba üst sınır \(O(9^m)\)'dir. Sudoku üzerinde genel geri izleme için beklenen teorik davranış budur.
Tek bir özyinelemeli adım içindeki işlemler sabit boyutlu \(9\times 9\) tablo üzerinde çalıştığı için sabit zamanlıdır. Python ve Java’da tek bir aday denemesi en fazla 9 satır hücresi, 9 sütun hücresi ve 9 kutu hücresinin incelenmesini gerektirir. C++ sürümünde aday hesabı bit işlemleriyle yapılır; buna karşılık en az adaylı boş hücreyi bulmak için tahta üzerinde tarama yapılır. Bellek kullanımı, özyineleme yığını için \(O(m)\) ve buna ek olarak sabit boyutlu tahta ile satır, sütun, kutu durumları kadardır.
Tahta boyutu sabit ve bulmaca sayısı yalnızca 50 olduğundan, teorik üst sınır üstel olsa bile pratik çalışma süresi küçüktür.
La entrada contiene 50 cuadrículas clásicas de Sudoku. Cada cuadrícula es un tablero de \(9 \times 9\) con dígitos entre \(0\) y \(9\), donde \(0\) representa una casilla vacía. Una vez resuelto un tablero, su contribución es el número de tres cifras formado por las tres primeras entradas de la fila superior.
Si denotamos la solución por \(x_{r,c}\) con \(1 \le r,c \le 9\), entonces una cuadrícula aporta
$$100x_{1,1}+10x_{1,2}+x_{1,3}.$$
La respuesta final es la suma de esa cantidad para los 50 Sudokus. Por tanto, la parte sustancial del problema consiste en completar correctamente cada tablero parcial respetando las reglas de Sudoku: cada fila, cada columna y cada subcuadro \(3\times 3\) deben contener exactamente una vez los dígitos del 1 al 9.
Las implementaciones tratan el Sudoku como una búsqueda finita con una invariante muy rígida: en toda llamada recursiva, el tablero parcial ya satisface todas las restricciones de filas, columnas y cajas.
Para un tablero parcialmente lleno definimos los conjuntos de dígitos ya usados
$$R_r=\{x_{r,c}\ne 0:1\le c\le 9\},\qquad C_c=\{x_{r,c}\ne 0:1\le r\le 9\},$$
y para cada caja
$$B_b=\{x_{r,c}\ne 0:b(r,c)=b\}.$$
La caja correspondiente a \((r,c)\) viene dada por
$$b(r,c)=3\left\lfloor\frac{r-1}{3}\right\rfloor+\left\lfloor\frac{c-1}{3}\right\rfloor+1.$$
La invariante fundamental es que ningún dígito no nulo puede aparecer dos veces dentro de la misma fila, la misma columna o la misma caja. En cuanto una rama viola eso, esa rama se descarta.
Para una posición vacía \((r,c)\), los únicos dígitos permitidos son
$$A(r,c)=\{1,2,\dots,9\}\setminus\bigl(R_r\cup C_c\cup B_{b(r,c)}\bigr).$$
Este conjunto es el objeto matemático central del solucionador. Si \(A(r,c)=\varnothing\), el estado parcial actual no puede extenderse hasta una solución completa. Si \(|A(r,c)|=1\), la jugada está forzada. En cualquier otro caso, el algoritmo debe ramificarse sobre los elementos de \(A(r,c)\).
La implementación en C++ representa los dígitos usados mediante máscaras de bits, de modo que el conjunto de candidatos se obtiene con operaciones bit a bit. Las implementaciones en Python y Java calculan el mismo conjunto de una forma más directa, comprobando fila, columna y caja cada vez que prueban un dígito.
Sea \(S\) un estado parcial legal. Si ya no quedan casillas vacías, \(S\) es una solución completa. En caso contrario se elige una casilla vacía \(u\), se calcula \(A(u)\) y se prueban uno a uno sus dígitos válidos. En forma lógica, la búsqueda es
$$\operatorname{Solve}(S)=\bigvee_{d\in A(u)} \operatorname{Solve}(S[u\leftarrow d]).$$
Aquí \(S[u\leftarrow d]\) es el nuevo tablero tras escribir \(d\) en la casilla \(u\). Una rama falla en cuanto alguna casilla vacía se queda sin candidatos legales.
La implementación en C++ mejora esta recurrencia eligiendo la casilla vacía con menor número de candidatos, lo que reduce el factor de ramificación. Las implementaciones en Python y Java recorren una lista prefijada de huecos. Ambas estrategias siguen siendo búsqueda con retroceso completa: si no se encuentra antes una solución, toda asignación legal termina siendo explorada.
Una comprobación interna usa un tablero casi completo cuya primera fila es
$$[0,3,4,6,7,8,9,1,2].$$
La entrada desconocida es \(x_{1,1}\). En la fila 1 solo falta el 5. La columna 1 contiene
$$[0,6,1,8,4,7,9,2,3],$$
de modo que también allí solo falta el 5. La caja superior izquierda contiene
$$[0,3,4;\ 6,7,2;\ 1,9,8],$$
y vuelve a quedar libre únicamente el 5. Por tanto,
$$A(1,1)=\{5\},\qquad x_{1,1}=5.$$
El número de tres cifras extraído es entonces
$$100\cdot 5+10\cdot 3+4=534.$$
Este ejemplo pequeño resume exactamente la lógica matemática del solucionador: los candidatos nacen por exclusión en fila, columna y caja, y las casillas forzadas se rellenan antes de cualquier ramificación profunda.
Las tres implementaciones leen las 50 cuadrículas, resuelven cada una por separado y suman \(100x_{1,1}+10x_{1,2}+x_{1,3}\) al acumulado final. La recursión modifica el tablero en sitio, y cuando una rama fracasa se deshace la asignación antes de intentar el siguiente candidato.
Cada implementación convierte las nueve líneas de texto de un rompecabezas en un tablero \(9\times 9\). Las casillas vacías se guardan como ceros. Una vez hallada la solución, las tres primeras casillas de la fila superior se leen y se transforman en la contribución pedida.
La implementación en C++ comprueba primero que las pistas iniciales no incumplen ya las reglas del Sudoku. Después mantiene máscaras de ocupación para filas, columnas y cajas, calcula candidatos rápidamente y, en cada nivel recursivo, escoge la casilla vacía con menos opciones. Las implementaciones en Python y Java almacenan una lista de posiciones vacías y avanzan recursivamente en ese orden; la legalidad de cada intento se comprueba escaneando directamente la fila, la columna y la caja \(3\times 3\). El árbol matemático de búsqueda es del mismo tipo en los tres casos, aunque la versión en C++ lo poda más.
Si una cuadrícula tiene \(m\) casillas vacías, el árbol de búsqueda tiene profundidad \(m\) y factor de ramificación a lo sumo 9, así que una cota grosera es \(O(9^m)\). Esa es la barrera exponencial normal del retroceso general sobre restricciones de Sudoku.
Dentro de un paso recursivo, el trabajo es constante porque el tablero tiene tamaño fijo \(9\times 9\). En Python y Java, comprobar un candidato implica revisar como máximo 9 posiciones de la fila, 9 de la columna y 9 de la caja. En C++, el cálculo de candidatos es bit a bit, aunque además se recorre el tablero para localizar la casilla vacía con menos candidatos. El uso de memoria es \(O(m)\) por la pila recursiva, más el tablero fijo y el estado auxiliar de filas, columnas y cajas.
Como el tamaño del tablero es fijo y solo hay 50 instancias, el tiempo real de ejecución es pequeño aunque la cota teórica sea exponencial.
输入包含 50 个标准数独。每个数独都是一个 \(9 \times 9\) 的方阵，字符 \(0\) 表示空格。每解出一张盘面，就取最上面一行前 3 个格子组成一个三位数，把这 50 个三位数全部相加。
如果把最终完成的盘面记为 \(x_{r,c}\)（其中 \(1 \le r,c \le 9\)），那么单个题目的贡献就是
$$100x_{1,1}+10x_{1,2}+x_{1,3}.$$
因此，题目的关键不在最后这一步加法，而在于如何把每个部分填充的数独完整补齐，并且始终满足数独约束：每一行、每一列、每一个 \(3\times 3\) 宫都必须恰好包含数字 1 到 9 各一次。
这些实现都把数独视为一个有限状态的回溯搜索问题。每一次递归调用都维护同一个核心不变量：当前已经填入的所有数字，仍然与所在行、所在列和所在宫的约束完全一致。
对一个部分填充的盘面，定义已经出现过的数字集合
$$R_r=\{x_{r,c}\ne 0:1\le c\le 9\},\qquad C_c=\{x_{r,c}\ne 0:1\le r\le 9\},$$
并且对每一个宫定义
$$B_b=\{x_{r,c}\ne 0:b(r,c)=b\}.$$
宫编号可以写成
$$b(r,c)=3\left\lfloor\frac{r-1}{3}\right\rfloor+\left\lfloor\frac{c-1}{3}\right\rfloor+1.$$
整个搜索过程中始终保持的事实是：任何非零数字都不能在同一行、同一列或同一宫内重复出现。一旦某个分支破坏了这个条件，这个分支就可以立刻剪掉，因为它不可能再通向合法解。
对一个空格 \((r,c)\)，允许填入的数字正好是
$$A(r,c)=\{1,2,\dots,9\}\setminus\bigl(R_r\cup C_c\cup B_{b(r,c)}\bigr).$$
这个候选集合是整个求解器最重要的数学对象。如果 \(A(r,c)=\varnothing\)，说明当前局面已经矛盾，不可能延伸成完整解。如果 \(|A(r,c)|=1\)，那么这个格子就被唯一确定。只有在 \(|A(r,c)|\ge 2\) 时，搜索才需要真正分支。
C++ 实现把行、列、宫中已经使用的数字压缩成位掩码，因此候选集合可以通过位运算快速得到。Python 和 Java 实现没有使用这种压缩表示，但本质上计算的是同一个集合：它们在尝试某个数字时，直接检查对应的行、列和 \(3\times 3\) 宫里是否已经出现过该数字。
设 \(S\) 是一个合法的部分盘面。如果已经没有空格，那么 \(S\) 就是一组完整解。否则，选取某个空格 \(u\)，求出其候选集合 \(A(u)\)，然后依次尝试每个合法数字。这个过程可以写成
$$\operatorname{Solve}(S)=\bigvee_{d\in A(u)} \operatorname{Solve}(S[u\leftarrow d]).$$
这里 \(S[u\leftarrow d]\) 表示把格子 \(u\) 填成 \(d\) 之后得到的新状态。如果在某个分支里出现了“某个空格一个候选都没有”的情况，那么这一分支立即失败并回退。
C++ 实现对这个递归又加了一层针对性优化：它不会随便挑一个空格，而是挑选候选数最少的那个空格先试。这样通常可以显著降低分支数。Python 和 Java 实现则在开始时记录所有空格，并按这份列表的顺序递归下去。两种方法的数学本质相同，都是完整的深度优先回溯；差别只在于 C++ 的分支顺序更有利于剪枝。
其中一个内置检验盘面几乎已经完成，它的第一行是
$$[0,3,4,6,7,8,9,1,2].$$
也就是说，未知位置是 \(x_{1,1}\)。第 1 行缺少的唯一数字是 5。第 1 列为
$$[0,6,1,8,4,7,9,2,3],$$
这一列缺少的也只有 5。左上角的 \(3\times 3\) 宫包含
$$[0,3,4;\ 6,7,2;\ 1,9,8],$$
其中同样只有 5 还没有出现。因此
$$A(1,1)=\{5\},\qquad x_{1,1}=5.$$
于是左上角三位数就是
$$100\cdot 5+10\cdot 3+4=534.$$
这个例子虽然很小，但和真正程序的推理完全一致：先由行、列、宫的排除关系得到候选集合，再立刻处理那些被唯一确定的格子；只有在不能再强制推进时，才进入更深的试探与回溯。
三个实现都会逐题读入这 50 张盘面，独立求解，然后把 \(100x_{1,1}+10x_{1,2}+x_{1,3}\) 累加到总和里。递归过程直接在原盘面上写入试探数字；如果某个分支失败，就把该数字撤销，再尝试下一个候选。
每个实现都先把题目的 9 行文本转成一个 \(9\times 9\) 数组，用 0 表示空格。成功求解之后，读取顶行前 3 个位置，并将它们转换成题目要求的三位数贡献。
C++ 实现会先检查初始提示本身是否已经违反数独规则。随后它维护行、列、宫的占用位掩码，用位运算快速得到候选，并在每一层递归重新寻找“候选最少”的空格。Python 和 Java 实现则预先记录空格列表，按固定顺序递归；每次尝试某个数字时，通过扫描对应行、列与 \(3\times 3\) 宫来判断是否合法。它们的数学搜索树属于同一种回溯树，只是 C++ 版本借助位掩码和选点策略能更早砍掉无效分支。
设一个盘面有 \(m\) 个空格，则搜索树深度为 \(m\)，每层最多分出 9 个子分支，所以一个粗略的最坏情况上界是 \(O(9^m)\)。这就是通用数独回溯在理论上的指数级界。
但在单个递归节点内部，操作都发生在固定大小的 \(9\times 9\) 盘面上，因此每一步的局部代价都是常数量级。Python 和 Java 在测试一个候选数字时，最多查看 9 个同行格子、9 个同列格子和 9 个同宫格子。C++ 用位运算计算候选，不过它还会额外扫描盘面来找当前候选最少的空格。空间方面，递归栈是 \(O(m)\)，再加上固定大小的盘面与行、列、宫辅助状态。
由于本题的盘面大小固定，而且只需处理 50 个实例，所以尽管理论最坏界是指数级，实际运行时间仍然很小。
Во входе даны 50 стандартных судоку. Каждая сетка имеет размер \(9 \times 9\), а цифра \(0\) обозначает пустую клетку. После решения очередной головоломки нужно взять трёхзначное число, составленное из первых трёх клеток верхней строки.
Если обозначить окончательно заполненную таблицу через \(x_{r,c}\), где \(1 \le r,c \le 9\), то вклад одной сетки равен
$$100x_{1,1}+10x_{1,2}+x_{1,3}.$$
Итоговый ответ получается суммированием этой величины по всем 50 судоку. Поэтому математическая сущность задачи состоит не в последнем сложении, а в корректном достраивании каждой частично заполненной сетки при строгом соблюдении правил: каждая строка, каждый столбец и каждый блок \(3\times 3\) должны содержать цифры от 1 до 9 ровно по одному разу.
Во всех реализациях судоку рассматривается как конечная задача поиска с жёсткой инвариантой. На каждом рекурсивном шаге текущая частичная сетка уже совместима со всеми ограничениями по строкам, столбцам и блокам.
Для частично заполненной таблицы введём множества уже использованных цифр
$$R_r=\{x_{r,c}\ne 0:1\le c\le 9\},\qquad C_c=\{x_{r,c}\ne 0:1\le r\le 9\},$$
а для каждого блока
$$B_b=\{x_{r,c}\ne 0:b(r,c)=b\}.$$
Номер блока для клетки \((r,c)\) задаётся формулой
$$b(r,c)=3\left\lfloor\frac{r-1}{3}\right\rfloor+\left\lfloor\frac{c-1}{3}\right\rfloor+1.$$
Основная инварианта такова: никакая ненулевая цифра не может встретиться дважды в одной и той же строке, одном и том же столбце или одном и том же блоке. Как только ветвь поиска нарушает это условие, её можно сразу отбрасывать.
Для пустой позиции \((r,c)\) допустимые цифры равны
$$A(r,c)=\{1,2,\dots,9\}\setminus\bigl(R_r\cup C_c\cup B_{b(r,c)}\bigr).$$
Именно это множество является центральным математическим объектом решения. Если \(A(r,c)=\varnothing\), текущий частичный расклад уже противоречив и не может быть продолжен до полного решения. Если \(|A(r,c)|=1\), значение клетки вынуждено. Во всех остальных случаях алгоритм обязан разветвиться по элементам \(A(r,c)\).
В реализации на C++ множества использованных цифр кодируются битовыми масками, поэтому множество кандидатов восстанавливается битовыми операциями. Реализации на Python и Java вычисляют тот же самый объект более прямым способом: при пробной постановке цифры они проверяют соответствующие строку, столбец и блок.
Пусть \(S\) — допустимое частичное состояние судоку. Если пустых клеток больше нет, то \(S\) уже является полным решением. Иначе выбирается пустая клетка \(u\), вычисляется \(A(u)\), и затем по очереди пробуются все допустимые цифры. Логически поиск можно записать так:
$$\operatorname{Solve}(S)=\bigvee_{d\in A(u)} \operatorname{Solve}(S[u\leftarrow d]).$$
Здесь \(S[u\leftarrow d]\) означает новое состояние после записи цифры \(d\) в клетку \(u\). Ветвь немедленно завершается неудачей, если в каком-то месте остаётся пустая клетка без единого допустимого кандидата.
Реализация на C++ делает этот процесс эффективнее, выбирая на каждом шаге пустую клетку с минимальным числом кандидатов. Это уменьшает фактор ветвления. Реализации на Python и Java идут по заранее составленному списку пустых позиций. В обоих случаях перебираются только допустимые продолжения, а полнота обеспечивается самим механизмом возврата: если решение не найдено раньше, то любая разрешённая подстановка рано или поздно будет рассмотрена.
Одна встроенная проверка использует почти решённую сетку, у которой первая строка равна
$$[0,3,4,6,7,8,9,1,2].$$
Неизвестной остаётся клетка \(x_{1,1}\). В первой строке отсутствует только цифра 5. Первый столбец равен
$$[0,6,1,8,4,7,9,2,3],$$
поэтому и там отсутствует только 5. Верхний левый блок \(3\times 3\) содержит
$$[0,3,4;\ 6,7,2;\ 1,9,8],$$
и в нём тоже недостаёт лишь 5. Следовательно,
$$A(1,1)=\{5\},\qquad x_{1,1}=5.$$
Тогда искомое трёхзначное число равно
$$100\cdot 5+10\cdot 3+4=534.$$
Этот мини-пример полностью отражает реальную логику программы: кандидаты возникают как пересечение трёх ограничений, вынужденные ходы делаются сразу, а более глубокое ветвление нужно только тогда, когда таких ходов больше нет.
Все три реализации читают 50 сеток, решают каждую независимо и прибавляют \(100x_{1,1}+10x_{1,2}+x_{1,3}\) к общему итогу. Рекурсия изменяет доску на месте; если ветвь неудачна, соответствующая постановка отменяется, после чего пробуется следующий кандидат.
Каждая реализация преобразует девять текстовых строк задачи в массив \(9\times 9\). Пустые клетки записываются нулями. После нахождения решения считываются первые три клетки верхней строки и переводятся в нужный трёхзначный вклад.
Реализация на C++ сначала явно проверяет, не нарушают ли исходные подсказки правила судоку уже в начальном состоянии. Затем она поддерживает маски занятости для строк, столбцов и блоков, быстро вычисляет кандидатов и на каждом уровне рекурсии выбирает самую ограниченную пустую клетку. Реализации на Python и Java заранее собирают список пустых позиций и идут по нему по порядку; корректность каждой пробной цифры проверяется прямым просмотром строки, столбца и блока \(3\times 3\). С математической точки зрения это один и тот же тип дерева возврата, но версия на C++ сильнее сокращает дерево поиска.
Если в сетке \(m\) пустых клеток, то глубина дерева поиска равна \(m\), а число ветвей из вершины не превосходит 9. Поэтому грубая верхняя оценка — \(O(9^m)\). Это стандартная экспоненциальная граница для общего backtracking-поиска в судоку.
Внутри одного рекурсивного шага вся работа ведётся на фиксированной доске \(9\times 9\), поэтому локальная стоимость является константной. В Python и Java проверка одного кандидата означает просмотр максимум 9 клеток строки, 9 клеток столбца и 9 клеток блока. В C++ вычисление кандидатов делается битовыми операциями, но дополнительно выполняется проход по доске для выбора пустой клетки с минимальным числом кандидатов. Память составляет \(O(m)\) для стека рекурсии плюс фиксированное место под саму сетку и вспомогательное состояние строк, столбцов и блоков.
Поскольку размер сетки фиксирован и задач всего 50, фактическое время работы остаётся небольшим, несмотря на экспоненциальную теоретическую оценку.
يتكوّن الإدخال من 50 شبكة سودوكو قياسية. كل شبكة هي مصفوفة \(9 \times 9\)، وتدل القيمة \(0\) على خانة فارغة. بعد حل كل شبكة نأخذ العدد المكوَّن من أول ثلاث خانات في الصف العلوي، ثم نجمع هذه القيم على جميع الألغاز.
إذا رمزنا إلى الشبكة المكتملة بالرمز \(x_{r,c}\) حيث \(1 \le r,c \le 9\)، فإن مساهمة لغز واحد هي
$$100x_{1,1}+10x_{1,2}+x_{1,3}.$$
إذن لبّ المسألة ليس عملية الجمع الأخيرة، بل إكمال كل شبكة جزئية مع الحفاظ الصارم على قيود السودوكو: كل صف وكل عمود وكل مربع \(3\times 3\) يجب أن يحتوي الأرقام من 1 إلى 9 مرة واحدة بالضبط.
تعامل جميع التطبيقات السودوكو بوصفه مسألة بحث منتهية مع ثابت منطقي واضح. ففي كل استدعاء تعاودي تكون الخانات التي مُلئت حتى تلك اللحظة متوافقة أصلًا مع قيود الصفوف والأعمدة والمربعات.
لشبكة مملوءة جزئيًا نعرّف مجموعات الأرقام المستخدمة
$$R_r=\{x_{r,c}\ne 0:1\le c\le 9\},\qquad C_c=\{x_{r,c}\ne 0:1\le r\le 9\},$$
ولكل مربع نعرّف
$$B_b=\{x_{r,c}\ne 0:b(r,c)=b\}.$$
ورقم المربع الذي تنتمي إليه الخانة \((r,c)\) هو
$$b(r,c)=3\left\lfloor\frac{r-1}{3}\right\rfloor+\left\lfloor\frac{c-1}{3}\right\rfloor+1.$$
الثابت الأساسي هو أن أي رقم غير صفري لا يجوز أن يظهر مرتين في الصف نفسه أو العمود نفسه أو المربع نفسه. فإذا كسرت إحدى فروع البحث هذا الشرط، فإن ذلك الفرع يُرفض مباشرة لأنه لم يعد قادرًا على الوصول إلى حل صحيح.
إذا كانت الخانة \((r,c)\) فارغة، فإن الأرقام المسموح بها فيها هي بالضبط
$$A(r,c)=\{1,2,\dots,9\}\setminus\bigl(R_r\cup C_c\cup B_{b(r,c)}\bigr).$$
هذه المجموعة هي القلب الرياضي الحقيقي للخوارزمية. إذا كان \(A(r,c)=\varnothing\)، فهذا يعني أن الحالة الجزئية الحالية متناقضة ولا يمكن تمديدها إلى حل كامل. وإذا كان \(|A(r,c)|=1\)، فالقيمة مفروضة قسرًا. أما إذا احتوت المجموعة على أكثر من عنصر، فيلزم التفرع وتجربة المرشحين.
في تطبيق C++ تُخزَّن الأرقام المستخدمة في الصفوف والأعمدة والمربعات على هيئة أقنعة بتّية، لذلك تُستخرج مجموعة المرشحين بسرعة باستخدام عمليات بتية. أما تطبيقا Python وJava فيحسبان المجموعة نفسها بطريقة مباشرة أكثر، إذ يفحصان الصف والعمود والمربع عند اختبار كل رقم تجريبي.
لتكن \(S\) حالة سودوكو جزئية مشروعة. إذا لم يبقَ أي موضع فارغ، فإن \(S\) تمثل حلًا كاملًا. وإلا نختار خانة فارغة \(u\)، ونحسب \(A(u)\)، ثم نجرّب كل رقم مسموح واحدًا بعد الآخر. ويمكن كتابة هذا البحث منطقيًا على الصورة
$$\operatorname{Solve}(S)=\bigvee_{d\in A(u)} \operatorname{Solve}(S[u\leftarrow d]).$$
وهنا يرمز \(S[u\leftarrow d]\) إلى الحالة الجديدة بعد وضع الرقم \(d\) في الخانة \(u\). ويفشل الفرع مباشرة إذا ظهرت في أي لحظة خانة فارغة لا تملك أي مرشح قانوني.
يُحسِّن تطبيق C++ هذه العلاقة باختيار الخانة الفارغة ذات أصغر عدد من المرشحين في كل مستوى تعاودي، مما يقلل عامل التفرع عادةً. أما تطبيقا Python وJava فيسيران وفق قائمة الخانات الفارغة كما جُمعت في البداية. في الحالتين يبقى البحث تراجعًا كاملًا؛ فجميع الإكمالات القانونية تُفحَص في النهاية ما لم يُعثَر على الحل قبل ذلك.
يستعمل أحد اختبارات التحقق شبكة شبه مكتملة يكون صفها الأول
$$[0,3,4,6,7,8,9,1,2].$$
إذن القيمة المجهولة هي \(x_{1,1}\). الصف الأول ينقصه الرقم 5 فقط. والعمود الأول هو
$$[0,6,1,8,4,7,9,2,3],$$
ولذلك فهو ينقصه أيضًا الرقم 5 فقط. أما المربع العلوي الأيسر \(3\times 3\) فيحتوي
$$[0,3,4;\ 6,7,2;\ 1,9,8],$$
ومن ثم لا يبقى فيه إلا الرقم 5. لهذا نحصل على
$$A(1,1)=\{5\},\qquad x_{1,1}=5.$$
وعليه يكون العدد المطلوب من أول ثلاث خانات هو
$$100\cdot 5+10\cdot 3+4=534.$$
هذا المثال الصغير يوضح المنهج كاملًا: تُستخرج المرشحات من استبعاد أرقام الصف والعمود والمربع، وتُملأ الخلايا المفروضة فورًا، ثم لا يبدأ التفرع الأعمق إلا عندما لا يبقى انتقال قسري واضح.
تقرأ التطبيقات الثلاثة الألغاز الخمسين، وتحل كل شبكة على حدة، ثم تضيف القيمة \(100x_{1,1}+10x_{1,2}+x_{1,3}\) إلى المجموع الكلي. أثناء التراجع تُعدَّل الشبكة في موضعها نفسه، وإذا فشل فرع ما تُزال المحاولة قبل تجربة المرشح التالي.
تحوّل كل نسخة السطور التسعة الخاصة باللغز إلى مصفوفة \(9\times 9\)، وتمثل الخانات الفارغة بالصفر. وبعد العثور على حل صحيح، تُقرأ أول ثلاث خانات من الصف الأعلى وتُحوَّل إلى العدد الثلاثي المطلوب.
يتحقق تطبيق C++ أولًا من أن المعطيات الابتدائية نفسها لا تكسر قواعد السودوكو. بعد ذلك يحافظ على أقنعة تمثل الأرقام المستخدمة في الصفوف والأعمدة والمربعات، ويحسب المرشحين بسرعة، ويختار في كل مستوى تعاودي الخانة الأكثر تقييدًا، أي ذات أقل عدد من المرشحين. أما تطبيقا Python وJava فيخزنان قائمة الخانات الفارغة ثم يتقدمان فيها بالترتيب؛ واختبار صحة الرقم التجريبي يتم بفحص الصف والعمود والمربع \(3\times 3\) مباشرة. الشجرة الرياضية هي شجرة التراجع نفسها في الحالات كلها، لكن نسخة C++ تقصّها بصورة أقوى.
إذا احتوت شبكة ما على \(m\) خانات فارغة، فإن عمق شجرة البحث يساوي \(m\)، وعدد الفروع من كل عقدة لا يتجاوز 9، ومن ثم فالتقدير الخام في أسوأ الأحوال هو \(O(9^m)\). وهذه هي الطبيعة الأسية المعتادة للبحث بالتراجع في مسائل السودوكو العامة.
داخل خطوة تعاودية واحدة يكون العمل ثابتًا لأن حجم الشبكة ثابت \(9\times 9\). ففي Python وJava يعني اختبار مرشح واحد فحص ما يصل إلى 9 خانات في الصف و9 في العمود و9 في المربع. وفي C++ يتم حساب المرشحين بعمليات بتية، لكن التطبيق يقوم أيضًا بمسح الشبكة لاختيار الخانة الفارغة ذات أقل عدد من المرشحين. أما الذاكرة فتبلغ \(O(m)\) لمكدس الاستدعاء التعاودي، إضافة إلى مساحة ثابتة للشبكة ولحالة الصفوف والأعمدة والمربعات.
وبما أن حجم الشبكة ثابت وعدد الألغاز 50 فقط، فإن زمن التنفيذ العملي يبقى صغيرًا رغم أن الحد النظري في أسوأ الأحوال أسي.