Introducción

¿Qué es el Sudoku?

Sudoku es un juego matemático inventado a finales de la década de 1970 en japón.

¿Cómo se juega ?

El objetivo del sudoku es rellenar una cuadrícula de 9x9 celdas, cada una dividida en subcuadrículas de 3x3(bloques), con las cifras del 1 al 9. Algunos números ya están rellenados y no se debe repetir el mismo número en la misma fila, columna o subcuadrícula.s

Si el sudoku está bien planteado, sólo puede tener una solución, y debería tener 17 pistas iniciales, es decir, 17 números ya rellenados como mínimo.

Aquí hay un ejemplo de un sudoku sin resolver y uno resuelto:

Equivalente matemático

Matemáticamente, la solución de un sudoku es siempre un cuadrado latino, es decir, una matriz de $n\ast n$ elementos, en la que cada casilla está ocupada por uno de los n símbolos de tal manera que cada uno de ellos aparece exactamente una vez en cada columna y en cada fila.

$$\left[\begin{array}{cccc}a& b& d& c\\ b& c& a& d\\ c& d& b& a\\ d& a& c& b\end{array}\right]$$

Un cuadrado latino está reducido si la primera fila y la primera columna están en orden natural.

La cantidad de números de cuadrados latinos de $n\times n$ No tiene una fórmula sencilla, pero crece increíblemente rápido cuando aumentamos $n$. A este fenómeno se le llama explosión combinatoria. Como curiosidad, aquí tenéis una tabla con la cantidad de cuadrados latinos y cuadrados latinos reducidos desde $n=1$ hasta $n=11$:

$n$	Número de cuadrados latinos de tamaño $n\times n$
1	1
2	2
3	12
4	576
5	161280
6	812851200
7	61479419904000
8	108776032459082956800
9	5524751496156892842531225600
10	9982437658213039871725064756920320000
11	776966836171770144107444346734230682311065600000

Sin embargo, el sudoku impone una restricción adicional a los subgrupos de 3 x 3 , como si fuera un caso especial de cuadrado latino, lo que nos deja con $6,670,903,752,021,072,936,960\approx 6.67\times {10}^{21}$ soluciones posibles, pero esa cifra baja a $5,472,730,538$ si tenemos en cuenta las simetrías que puedan surgir.

Descripción matemática formal

$$\underset{\text{Matrices permutadas de}\left[\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right]}{\overset{\text{Cuadrado Latino}}{\overbrace{\left[\begin{array}{c}\left[\begin{array}{ccc}e& c& d\\ f& g& b\\ a& i& h\end{array}\right]\left[\begin{array}{ccc}f& g& h\\ a& i& e\\ c& d& b\end{array}\right]\left[\begin{array}{ccc}i& a& b\\ c& d& h\\ e& f& g\end{array}\right]\\ \left[\begin{array}{ccc}h& e& i\\ d& b& f\\ g& a& c\end{array}\right]\left[\begin{array}{ccc}g& f& a\\ h& e& c\\ i& b& d\end{array}\right]\left[\begin{array}{ccc}d& b& c\\ g& i& a\\ h& e& f\end{array}\right]\\ \underbrace{\left[\begin{array}{ccc}i& f& a\\ b& h& g\\ c& d& e\end{array}\right]\left[\begin{array}{ccc}e& c& g\\ d& a& i\\ b& h& f\end{array}\right]\left[\begin{array}{ccc}b& h& d\\ f& c& e\\ a& g& i\end{array}\right]}\end{array}\right]}}}$$

Esto sería el equivalente matemático de un sudoku, y su definición formal sería:

Descripción matemática de un Sudoku

Un Sudoku es una matriz $A\in \{1...9{\}}^{9\times 9}$ tal que:

• Para todo $i$, la fila $A_{i,1},A_{i,2}...A_{i,9}$ es una permutación de $\{1...9\}$.
• Para todo $j$, la columna $A_{j,1},A_{j,2}...A_{j,9}$​ es una permutación de $\{1...9\}$.
• Para cada bloque 3×3, los 9 elementos dentro forman también una permutación de $\{1...9\}$.

Es decir, un cuadrado latino de 9×9 dividido en cuadrados de 3x3 cuyos componentes son una combinación de 9 números.