EL SUDOKU consiste en colocar

en las casillas aún vacías de

una plantilla reticular los dígitos
1 a 9, sin que aparezca repetido
ninguno de ellos en filas, colum-
nas o recuadros.
 Sudoku
Este juego no requiere la aplicación de matemática alguna,
ni siquiera de la mera aritmética.
Sin embargo, encierra en sí interesantes problemas matemáticos

Jean-Paul Delahaye

n juego de pura lógica sólo podría seducir, parece, a muy pocos:

U a matemáticos, a informáticos o a ludópatas obsesivos. El éxito

asombroso del sudoku demuestra que no es así. Este curioso
fenómeno social, un juego de razonamiento que ha invadido
en pocos meses todos los continentes, recuerda la moda del
cubo de Rubik, que hace unos veinticinco años se convirtió
en la pasión de centenares de millones de personas. Pero al contrario que
el tridimensional cubo de Rubik, una plantilla de sudoku es una retícula
cuadrada de 81 casillas dividida en 9 cuadrados menores de 9 casillas cada
uno —las tres primeras casillas de las tres primeras columnas, las tres ca-
sillas siguientes de las tres primeras columnas, las tres primeras casillas de
las tres columnas siguientes y así sucesivamente—, a los que llamaremos
recuadros. La partida empieza con una plantilla inicial donde algunas de
las casillas llevan ya inscrita una cifra.
Las reglas son de una simplicidad extrema. Hay que ir ocupando las
casillas vacías con los dígitos de 1 a 9, de modo que ninguno aparezca
repetido en una misma línea, en una misma columna y en un mismo recua-
dro. La solución, según los cánones del sudoku, debe ser única. Ninguna
operación aritmética (sea la adición, la multiplicación u otra cualquiera)
ayudará a resolver un sudoku: las cuadrículas podrían estar ocupadas por
JEN CHRISTIANSEN; FUENTE: JEAN-PAUL DELAHAYE

nueve símbolos no numéricos (letras, colores, dibujitos, etc.). No se trata,

pues, de un juego aritmético, sino combinatorio, y para resolverlo basta y
sobra con una lógica implacable y una gran tenacidad.

¿Japonés o norteamericano?
Los primeros sudokus se publicaron en mayo de 1979, en la página 6 del
número 16 de la revista estadounidense Dell Pencil Puzzles and Word Games
(de Norwalk, en Connecticut), con el nombre de Number Place, “colocación
de números”. Al parecer, su autor fue Howard Garns, arquitecto jubilado
fallecido en Indianápolis en 1989 (o en 1981, las fuentes disienten); no
pudo, pues, conocer el reciente éxito de su invento. Garns, como todos los
primeros autores de sudokus, los componía a mano.

INVESTIGACIÓN Y CIENCIA, agosto, 2006 55

 CUADRADOS LATINOS Y SUDOKUS
Los cuadrados latinos, que
recibieron ese nombre del Casilla
5 8 6 4 2 1 3 7 9
matemático del siglo XVIII
Leonhard Euler, son matrices 3 2 7 9 6 5 4 8 1
1 2 3 4
cuadradas en las que cada 9 1 4 3 7 8 6 2 5
fila y columna es una permu-
2 3 4 1
1 6 3 5 8 4 7 9 2
tación distinta de los mismos 3 4 1 2
n símbolos: ningún símbolo 2 4 5 1 9 7 8 6 3
4 1 2 3
aparece dos veces en una fila 8 7 9 6 3 2 5 1 4
o en una columna. Un sudoku Pequeño cuadrado
ya relleno es un cuadrado latino (n = 4) 7 5 8 2 1 3 9 4 6
latino de orden 9 formado por 6 3 1 7 4 9 2 5 8
permutaciones elegidas de Recuadro 4 9 2 8 5 6 1 3 7
modo que cada uno de los 9
recuadros parciales contenga Cuadrado latino que también es
los nueve dígitos de 1 a 9. un sudoku completo (n = 9) Leonhard Euler

Antes de convertirse en un juego nales suman lo mismo—, con el que Tantos sudokus
presente en la sección de pasatiem- no tiene otra cosa que ver que los como seres humanos
pos de diarios de todo el mundo, el dígitos y la plantilla, sino el cuadrado
sudoku llegó a Japón. Allí empezó en latino. Un cuadrado latino de lado Por definición, un sudoku completo
1984 a aparecer en una revista que n es una matriz de n2 casillas que es un cuadrado latino que verifica la
le dio ese nombre, especie de acró- hay que rellenar con n símbolos de condición adicional de que los recua-
nimo de “las cifras deben quedarse manera que nunca aparezca dos veces dros de 9 casillas han de contener
solteras”. La revista se reservó los un mismo símbolo en una misma fila los dígitos de 1 a 9; hay menos, por
derechos de la denominación “sudo- o en una misma columna (en conse- consiguiente, que cuadrados latinos
ku”; por eso, las demás publicaciones cuencia, cada uno de los n símbolos de orden 9. El cálculo de su número
japonesas que fueron publicando el se utiliza exactamente n veces). Su exacto resulta bastante difícil. Sólo
juego adoptaron el nombre original, origen se remonta a la Edad Me- mediante la conjugación del razona-
“Number Place”, o su derivado nam- dia. Fue Leonhard Euler (1707-1783) miento —para simplificar el proble-
pure. Así pues, el juego se conoce quien dio a esa disposición de cifras ma— y el ordenador —para examinar
en Occidente con un nombre japonés el nombre de cuadrado latino y la sistemáticamente los casos— se ha
y en Japón con una denominación analizó. Existen solamente 12 cuadra- conseguido contar el número exac-
occidental. dos latinos de lado 3, pero ya son 576 to de sudokus completos: 6.670.903.
La difusión mundial del pasatiem- los que tienen lado 4 y nada menos [Link].960, si se toman
po se debe a otro jubilado, el juez que [Link].[Link]. como distintas las matrices que se de-
neozelandés Wayne Gould, residente 225.600 los de lado 9. Si, conforme ducen unas de otras mediante opera-
en Hong Kong, quien escribió un pro- al espíritu de la teoría de grupos, ciones elementales (giros, simetrías,
grama de ordenador que genera auto- establecemos que los cuadrados la- permutaciones de las tres primeras
máticamente sudokus. A finales de tinos deducibles de otros por ope- columnas, de las tres primeras filas,

EMANUEL HANDMANN, 1753, PASTEL ORIGINAL EN KUNSTMUSEUM BASEL

2004, el Times aceptó su proposición raciones elementales (permutación etc.). Este resultado, obtenido no hace
de publicarlos; poco después, en ene- de líneas o de columnas) sólo han de mucho por Bertram Felgenhauer, de
ro de 2005, otro periódico inglés, el contarse una vez, el número de cua- la Universidad Técnica de Dresde, y
Daily Telegraph, también los incluía. drados latinos de lado 9 será sólo Frazer Jarvis, de la Universidad de
A partir de ese momento, docenas de [Link].258.816 (resultado Sheffield, ha sido comprobado varias
diarios de todo el mundo incorpora- establecido por Stanley E. Bammel veces (cosa importante para un resul-
ron el juego a sus páginas, llegando y Jerome Rothstein en 1975). tado obtenido de esa forma).
algunos a sacarlo en primera plana, En 1981, James. R. Nechvatal en- Si se cuentan como una sola las
como reclamo publicitario. Tras ellos contró una fórmula general bastante plantillas que se deducen unas de
llegaron las revistas y libros dedica- complicada que proporciona el nú- otras mediante operaciones simples,
dos en exclusiva al sudoku. mero de cuadrados latinos de n ca- el número de matrices completas re-
sillas de lado. Sin embargo, ni esta sulta un poco menor que el núme-
Los precursores fórmula ni otras similares permiten ro de seres humanos de la Tierra:
El precursor del sudoku no es, como deducir el valor asintótico (el orden [Link]. Este recuento debería
a veces se dice, el cuadrado mágico de magnitud cuando n se hace muy tranquilizar a los entusiastas del su-
—una retícula en la que los enteros grande) de esa cantidad, que sigue doku: aun resolviendo uno por mi-
de todas las filas, columnas y diago- siendo desconocido. nuto, aun dedicándose a ello durante

56 INVESTIGACIÓN Y CIENCIA, agosto, 2006

 los próximos cien años sin parar, no “El mejor sudoku imperfecto” de- el programa coloca la cifra 1 en la
se resolvería ni siquiera un 1 por muestra que 77 datos no garantizan primera casilla vacía. Si esta elección
ciento del total. la unicidad. es compatible con las reglas bási-
Se ha de señalar que un sudoku cas, continúa con la segunda casilla
completo puede proceder de más Programas vacía, en la que coloca un 1, pasa
de una plantilla inicial. Al día de En el caso de los sudokus corrien- después a la tercera, y así sucesi-
hoy no se ha logrado contar cuántas tes (de 9 × 9), no cuesta demasiado vamente. Cuando tropieza con una
plantillas iniciales diferentes exis- escribir programas informáticos capa- incompatibilidad (lo que ocurre muy
ten. Se podría considerar que una ces de completar cualquier plantilla rápidamente), aumenta en una unidad
plantilla inicial sólo es interesante inicial válida (estos programas, como la cifra recién colocada, y continúa
en el caso de que no se pueda hacer veremos más adelante, son la esencia avanzando. Si, al querer aumentar la
“más pequeña”, es decir, cuando es de los generadores automáticos de última cifra colocada, descubre que
una plantilla mínima, en el sentido plantillas de sudoku). es un 9 (¡que no es posible reem-
siguiente: al retirarle una cifra, la Se pueden considerar diversos plazar por un 10!), retrocede más,
solución deja de ser única. No se métodos, pero el más corriente es aumenta en una unidad la penúltima
ha podido aún calcular el número el de “retroceso sistemático” (back- cifra colocada, vuelve a proseguir,
de plantillas mínimas, o lo que es tracking). La idea es la siguiente: etc. (A veces, el programa tiene que
lo mismo, el número de problemas
de sudoku diferentes.
Otra cuestión de mínimos: ¿cuál es ¿16 o 17?
el menor número de cifras que debe
colocarse en la plantilla de modo que El número mínimo de dígitos que puede darse en un sudoku de 9 × 9 sin que
la solución pueda ser única? Gordon deje de haber una solución única parece ser 17. Mostramos un ejemplo. Un
Royle, de la Universidad del Oeste cierto sudoku completo, que los aficionados al juego conocen con el nombre de
de Australia, ha recopilado más de “me suena mucho”, oculta 29 plantillas iniciales, que no son equivalentes entre
38.000 plantillas iniciales con dieci- sí, de 17 cifras. Ese 29 es una cantidad insólita, por lo elevada. Se creía que
siete números y sólo una solución; “me suena mucho” era el sudoku que con mayor probabilidad contenía una plan-
y tales, que no pueden convertirse tilla inicial de 16 dígitos con una solución única; sin embargo, una exploración
unas en otras mediante operaciones exhaustiva lo ha descartado. Se conoce, eso sí, una plantilla inicial de 16 cifras
elementales. Gary McGuire, de la que sólo puede rellenarse de dos formas. Las reproducimos aquí abajo; difieren
Universidad Nacional de Irlanda, en que ochos y nueves están intercambiados.
en Maynooth, viene buscando una
plantilla de 16 cifras que sólo puede Una plantilla inicial con 17 cifras El sudoku “me suena mucho”
rellenarse de una forma, pero hasta
ahora no la ha encontrado. 1 9 6 3 9 2 4 1 7 8 5
Parece, pues, que la respuesta es 3 8 2 8 4 7 6 5 1 9 3
17, pero no se cuenta con una de- 6 5 1 7 9 8 3 6 2 4
mostración, y según McGuire es poco
probable que se llegue a obtenerla. 1 2 4 1 2 3 8 5 7 9 4 6
Si se pudiese analizar en sólo un se- 7 3 7 9 6 4 3 2 8 5 1
gundo cada plantilla completada para
saber si incluye una plantilla inicial 5 4 5 8 6 1 9 2 3 7
de 16 cifras con solución única, se 8 6 3 4 2 1 7 8 5 6 9
JEN CHRISTIANSEN; FUENTE: GORDON ROYLE Universidad de Australia Occidental

analizarían todas en 173 años. Pero 4 8 6 1 9 4 7

2 5 3 2
ni siquiera eso está al alcance de los
ordenadores actuales. Pronto tardarán 7 5 9 7 5 3 2 6 4 1 8
un minuto por plantilla completa, con
Una plantilla inicial con 16 cifras ...que sólo se rellena de dos formas
lo que concluirían la labor en 10.380
años. Aun repartiendo el trabajo entre 5 2 4 5 6 2 3 89 9 8 4 7 1
10.000 ordenadores, llevaría un año. 8 4 9
7 1 3 9 8 7 1 6 2 5 3
Si no se aprende a reducir el espacio
de busca o no se encuentra un algo- 1 3 7 4 2 5 8 9 98 6
ritmo de búsqueda mucho mejor, el 4 6 3 5 8 9 1 98 4 6 2 7
problema quedará pendiente. 9 7 4 2 6 3 1 8 5
Se conoce, en cambio, la solu- 7 2 8 9
ción —77— del problema contra- 1 2 1 6 8 9 5 7 3 4 98
rio: “¿Cuál es el número máximo de 6 98 1 5 4 2 7 3 89
cifras que pueden darse sin que la 6 2
solución sea necesariamente única?” 3 1 7 2 5 6 3 89 9 8 1 4
Es muy fácil ver que con 80, 79 o 78 4 4 8 9 3 98 7 1 5 6 2
datos, si existe solución, será única.
Sin embargo, la plantilla del recuadro

INVESTIGACIÓN Y CIENCIA, agosto, 2006 57

 METODOS DE RESOLUCION
Vamos a examinar aquí cuatro
métodos para progresar en la a b
resolución de un sudoku.
Conviene aplicar a la vez los mé- 5 1 9 6 5 1 9 6
todos 1 y 2 (un poco de uno, un
poco del otro), que son los más 9 5 9 5
rápidos. Lo malo es que a veces 5 2 7 5 2 7
no llevan demasiado lejos. En tal
caso, pasaremos al método 3, y si 4 9 1 7 4 9 1 7
éste también resulta insuficiente, 7 Cifras 7
al método 4, que funciona siem- obligadas
pre pero es más delicado. Hay, 1 3 2 1 3 2
claro, otros métodos, descritos en
páginas especializadas de la Red,
3 4 5 9 3 4 5 9
aparte de los que usted pueda 2 8 7 1 4 Casillas 2 8 7 1 4
obligadas
inventar.
7 6 5 8 2 7 6 5 8 2

c d
5 1 9 6

9 5
5 2 7

4 9 1 7
7
1 3 2
3 4 5 9
2 8 7 1 4
7 6 5 8 2

retroceder varios pasos antes de vol- nuevas cifras que no figuren en la Las técnicas de retroceso sistemá-
ver a avanzar.) tabla. tico no son aplicables por los seres
Este método, debidamente pro- Las técnicas de retroceso siste- humanos (a menos que posean una
gramado, explora todas las hipóte- mático dan lugar a programas de paciencia verdaderamente fuera de
sis posibles sin olvidar ninguna, y resolución bastante cortos. El len- lo común). Los jugadores humanos
JEN CHRISTIANSEN; FUENTE: JEAN-PAUL DELAHAYE

por consiguiente acaba por encontrar guaje Prolog, inventado por Alain utilizan reglas más variadas y sagaces
la solución, si es que existe. Si hay Colmerauer y Philippe Roussel, de y sólo proceden por tanteo (método
varias (un sudoku imperfecto), las la Universidad de Marsella, en los equivalente al retroceso sistemático)
encontrará también. años setenta resulta particularmente como último recurso.
Caben perfeccionamientos que adecuado para redactar programas de Cuando nació el juego, las planti-
aceleran el descubrimiento de la resolución de sudokus, pues contie- llas iniciales se preparaban a mano,
solución o soluciones. Tenemos, en ne entre sus mecanismos básicos un pero ahora prácticamente todas se
particular, la “propagación de res- algoritmo de “retroceso sistemático”. obtienen mediante programas inspi-
tricciones”: cada vez que se coloca Existen programas en Prolog de un rados en la idea siguiente: se sitúan
una cifra, el programa actualiza la centenar de líneas que resuelven con cifras al azar en el retículo y se aplica
tabla de posibilidades restantes para bastante eficacia todos los sudokus un algoritmo de resolución (de re-
cada casilla vacía y no considera de 9 × 9. troceso sistemático, por ejemplo). Si

58 INVESTIGACIÓN Y CIENCIA, agosto, 2006

METODO 1: la casilla obligada METODO 2: la cifra obligada
Se toma una casilla fija. Al examinar los dígitos Ahora se considera una cifra fija; el 5, por ejemplo. En las columnas 1 y 3 ya hay cincos; no
presentes en su columna, su fila y su recuadro, tal lo hay, en cambio, en la columna 2, en la que ha de figurar uno. ¿Cuál será su puesto? No
vez se descubra que sólo existe una posibilidad. puede estar en las tres primeras casillas de la columna 2, porque el recuadro situado a su
En tal caso, se consigna en la casilla. Claro está izquierda y arriba ya contiene un 5. Tampoco estará en las tres últimas casillas de la columna
que si hay varias posibilidades, todavía no se 2, porque el recuadro inferior izquierdo ya tiene un 5. Así que el 5 de la columna estará en
puede llenar la casilla en cuestión. una de las casillas 4, 5 o 6. Sólo una está vacía: el 5 corresponde a la quinta casilla.
Ejemplos: En la figura b, las casillas señaladas en Ejemplos: Las casillas con números azules en la figura b corresponden a cifras obligadas por
rojo son las casillas obligadas de la plantilla. razonamientos como el anterior.

METODO 3: simplificación de series de posibilidades METODO 4: tanteos (prueba y error)

El método siguiente es de gran potencia, pero exige proveerse de lápiz y goma de borrar. A veces es necesario proceder por tanteo, método
Se anotan en cada caso las cifras que todavía son posibles (véase la figura c). Hay ju- bastante incómodo y que exige, bien (a) una gran
gadores que prefieren poner en las casillas puntitos que representan, según su ubicación, concentración, bien (b) muchos lápices de diferentes
las cifras del 1 a 9: el 1 estará representado por un punto arriba a la derecha, el 2 por colores, bien (c) utilizar papel de calco, bien (d) un
un punto en lo alto y al centro, y así sucesivamente. programa de ayuda para la resolución de sudokus
Ahora tenemos a mano toda suerte de razonamientos, cuyo principio se podrá compren- que permita poner marcas en las casillas y borrarlas.
der mediante un ejemplo. Los sudokus diabólicos exigen a menudo una fase
Ejemplo: En la tercera columna, la serie de posibilidades es {2, 3, 6, 7}, {3, 6, 9}, {2, 6}, de exploración por tanteo. Cuando una incertidumbre
{2, 6} y {6, 7} que corresponden, respectivamente, a las posibilidades de las casillas 2, persiste —por ejemplo, entre dos casillas de la mis-
3, 4, 5 y 6. La columna ha de contener un 2 y un 6, que estarán necesariamente en las ma línea cuyas posibilidades son {2, 6}, {2, 6}—, se
dos casillas cuyas posibilidades son {2, 6}. En consecuencia, el 2 y el 6 no se encuentran prueba a colocar el 6 en la primera casilla, para ver
en ningún otro lugar (de esta columna) y pueden borrarse de las otras casillas. La serie lo que sale. Aplicando los otros métodos —incluso el
de posibilidades de la columna queda simplificada a: {3, 7}, {3, 9}, {2, 6}, {2, 6}, {7}. Pero tanteo de nuevo, utilizado dentro de sí mismo— se
eso no es todo. Al venir obligada la colocación del 7, también se fuerza la del 3 y la del deducen todas las consecuencias posibles. Si
9. Las posibilidades, finalmente, se reducen a: {3}, {9}, {2, 6}, {2, 6}, {7}. Sólo persiste una tropezamos con una imposibilidad, es que el 6 no
incertidumbre: la colocación del 2 y del 6. se encuentra donde hemos intentado situarlo. Habrá,
Cuando se utilice el método de simplificación de posibilidades no se ha de olvidar que por lo tanto, que colocar un 2, la única posibilidad
la serie de la que se parte puede ser, o bien la serie de posibilidades de las casillas que queda.
de una misma columna, o bien la de las casillas de una fila, o bien las de un recuadro. Si no se descubre ninguna imposibilidad, es que
Claro está, esas simplificaciones interactúan unas con otras. hemos acertado con la solución (dado que es única).
La formulación de la regla general de simplificación de una serie de posibilidades es la El método de tanteo se funda en el principio de
siguiente: si en la serie de posibilidades (de una línea, de una columna o de un recua- reducción al absurdo.
dro) se pueden encontrar m cifras y m conjuntos de posibilidades correspondientes a m La dificultad práctica de aplicar este método se debe
casillas que no utilizan más que estas m cifras (aunque no necesariamente todas ellas en a que a veces es necesario realizar varios tanteos
cada una de esas casillas), entonces estas m cifras pueden suprimirse de los conjuntos seguidos y volver atrás en caso de imposibilidad.
de posibilidades de las demás casillas. La idea del método de tanteo es la misma que la em-
Puede ejercitarse simplificando lo más posible estas series de posibilidades: pleada por los algoritmos de retrogradación sistemática
A {1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4, 5}, {1, 2, 4} (solución: {1}, {2}, {3}, {5}, {4}) (backtracking), procedimiento que los programas
B {2, 3}, {2, 5}, {3, 5}, {2, 3, 5, 7, 8, 9}, {7, 9}, {2, 5, 7} (solución: {2, 3}, {2, 5}, {3, 5}, realizan fácilmente, pero que a la memoria humana
{8}, {9}, {7}) le resulta muy costoso.
Provisto de los tres primeros métodos y de las interacciones que se puedan descubrir Llama la atención que el mejor método para una
entre ellos, le será posible resolver una buena proporción de plantillas de sudoku, entre máquina sea el último para la inteligencia humana.
ellas algunas clasificadas como difíciles o diabólicas.

esa plantilla tiene solución única, el que haya que aplicar para completar casillas de la columna de la casilla en
programa termina. Si no tiene solu- la plantilla, se califica a ésta como cuestión), con 8 más (correspondien-
ción, se elimina uno de sus dígitos y fácil, medianamente difícil, difícil y tes a la fila de la casilla) y con aún
se vuelve a empezar. Si, en cambio, diabólica. 4 más (las otras 8 del recuadro de
posee varias, se elige una y se le Es de señalar que el problema de la casilla, pero descontando las 4 ya
añaden tantas cifras nuevas como sea completar una plantilla de Sudoku incluidas en la columna y en la fila),
necesario para que al final no haya equivale al de colorear con nueve co- es decir, con otros 8 + 8 + 4 nodos,
más que una solución. lores un grafo (una figura donde pun- lo que da un total de (20 × 81)/2
Hay escritos varios programas que tos, o nodos, están unidos por rayas, pares de nodos —810— unidos por
tratan de seguir más o menos de cerca o aristas) de manera que dos nodos una arista.
los métodos humanos. Aunque más conectados por una arista no tengan Esta equivalencia con el coloreado
largos que los otros, también son efi- el mismo color. El grafo equivalente de grafos tiene un significado mate-
caces. Estos programas que remedan constaría de 81 nodos, algunos de mático, pues liga el sudoku a una
el razonamiento humano son útiles los cuales se habrían coloreado ya importante clase de problemas, los
para graduar la dificultad de las antes de empezar. Cada nodo (que problemas NP-completos. Estos pro-
plantillas propuestas, y en función correspondería a una casilla) estaría blemas no pueden resolverse en un
de los principios de razonamiento conectado con otros 8 (las otras ocho tiempo razonable. Un ejemplo bien

INVESTIGACIÓN Y CIENCIA, agosto, 2006 59

VARIANTES DEL SUDOKU
En los ejemplos que siguen, las re-
a b
glas del sudoku se aplican, pero con
algunos cambios. En a, se emplean N 5
letras en vez de números y los recua-
I 2
dros internos ya no son cuadrados, 9 3
sino de formas irregulares. En (b), que
T R 3 6
contiene seis recuadros triangulares, 5
las filas y las columnas inclinadas R E 6 4 7
pueden interrumpirse en el centro, y
cuando una fila o columna sólo cuenta A N
1 6
con ocho casillas, la casilla contigua M D 8
que es punta de la “estrella” vale 4 5 8
como novena casilla. En c, la suma R 9
de los números de tres cifras de los
primeros recuadros en las filas marca- A 3 1 2
das con el signo + suman el número G
de tres cifras del tercer recuadro. En
d, los signos de mayor y menor indi-
can la relación entre los dígitos. En
e, las fichas de dominó inferiores han
c d
de colocarse en las casillas vacías >
del retículo. En f, se superponen tres + 9 = 6 > > > > >

> >

>
> >
>
> >
>
> >
> >
>
sudokus simples. > >
6 5 8 2 > > > >

>
>
>

>
+ 4 = 9 > >
>
>
>
>
>
>
> > >
6 1 8 5 7 >

>
>
>

> >
> >

> >
> >
> >
>
>
>
>
5 + = 8 > > >

>
>
>

>
> > >
> > >
8 1 4 5 6
> >
>
>
>
>
PARA LAS SOLUCIONES 5 + 9 =

> >
> >

>
> >
>

>
> >
> >
> >
>
> > > >
DE ESTOS Y OTROS PROBLEMAS 8 7 1 6 >

>
>
>
QUE APARECEN EN EL ARTICULO, > > >
> >
>
VISITESE: 7 +3 =
[Link]

LEFTOVERS. A K PETERS LTD (en prensa) (a); © NONZERO/OLGA LEONTIEVA (b); ED PEGG, JR. (c);
conocido es el de la determinación de Universidad de Seta, han demostrado un problema NP-completo: el tiempo

JEN CHRISTIANSEN; FUENTE: BOB HARRIS EN THE GRAND TIME SUDOKU AND THE LAW OF
la posibilidad de colorear con tres co- hace poco que la resolución de su- requerido para que un programa com-
lores los nodos de un grafo de modo dokus generalizados —es decir, con pletase las plantillas iniciales aumen-
que no haya dos nodos unidos por una retículos de n2 x n2, para cualquier taría vertiginosamente con n. Ya se
arista pintados con el mismo color. valor de n y no sólo 3, y n2 símbo- conjeturaba que así era, pero resulta
Takayuki Yato y Takahiro Seta, de la los diferentes para rellenarlos— es satisfactorio saber que se ha obtenido
una demostración formal.
EL MEJOR SUDOKU IMPERFECTO Métodos humanos de resolución
y variantes
Que la plantilla inicial 12 2 1 La resolución a mano de los sudokus
presente 77 casillas
3 3 4 5 6 7 8 9
se ha convertido en la obsesión de
rellenas no basta 4 5 6 4 5 6 7 8 9 1 2 3 millones de entusiastas. Es deseable
para que la solución 7 8 9 7 8 9 1 2 3 4 5 6
sea única. Aunque
descubrir las mañas por uno mismo y
21 1 2 4 4 3 9 8 5 6 7 no consultar recetas hasta haber expe-
esta de aquí sólo
tiene cuatro casillas 8 6 5 2 7 3 9 4 rimentado un buen rato con el juego.
1
© NONZERO/CIHAN ALTAY (d)

vacías, hay dos so- No obstante, pensando en quienes no

luciones: en las pri- 9 3 7 6 4 5 8 1 2 sepan cómo empezar, he aquí dos
meras dos columnas, 3 4 1 8 6 2 9 7 5 principios elementales. El primero
el 1 y el 2 que faltan 5 7 2 9 1 6 3 8 consiste en buscar las casillas vacías
son intercambiables.
4
que tengan mayores condicionantes;
6 9 8 5 3 7 2 4 1 se trata, obviamente, de las que perte-
necen a una fila, columna o recuadro

60 INVESTIGACIÓN Y CIENCIA, agosto, 2006

e f

1 9
5 2 8
6 4 3 7
7 6
8 7 5
9 5 4
9 3
5 2
6 1
7 3 4
6 5 9
2 7 8
5 1
8 2
9 3
6 4 1
7 5 2
2 9
3 1 7 6
5 8 1
9 3

que estén bastante llenos. Con un borrar. Los hay que señalan vínculos
poco de suerte, las imposibilidades entre casillas. No es necesario pro- El autor
acumuladas (del tipo “la casilla no hibirse el uso de estos programas, Jean-Paul Delahaye es profesor de
puede contener un 1, un 3 o un 7, que al eliminar tareas fastidiosas informática de la Universidad de Lille.
porque ya hay un 1, un 3 y un 7 en (como el borrado de los errores)
su misma columna”) pueden deter- nos permiten una mayor sutileza y Bibliografía complementaria
minar unívocamente su valor. virtuosismo en los razonamientos
El segundo principio consiste en combinatorios. SUDOKU. Enciclopedia Wikipedia, 2005:
buscar en qué lugar puede estar una Cuando se canse de las plantillas [Link]
determinada cifra dada en una co- tradicionales, podrá buscar varian- SUDOKU VARIANT, 2005: [Link]
lumna, fila o recuadro dados (por tes del sudoku. Son innumerables: [Link]/techiques, 2005.
ejemplo, el 3 en la fila 4). A veces se superponen varias plantillas, se
A VARIETY OF SUDOKU VARIANTS, 2005:
esta pregunta tiene una sola respuesta sustituyen los cuadrados por otras [Link]
posible. estructuras y se utilizan colores. El php?t=995
Es fácil encontrar en Internet pro- interés de estas variantes es que obli-
gramas que generan plantillas de la gan a efectuar razonamientos nuevos. [Link]
dificultad que se desee y nos ayudan Y gracias a las versiones gigantes [Link]
en la búsqueda de soluciones (pero del sudoku, los expertos a quienes HOW TO SOLVE? 2005: [Link]
ED PEGG, JR. (e y f)

no completan la plantilla, claro está). una plantilla tradicional sólo les dure com/[Link]
Algunos permiten, por ejemplo, ano- un cuarto de hora podrán sumergirse EXPLORING THE MATHEMATICS OF SUDOKU.
tar marcas provisionales en las ca- durante un día entero en las deli- Sourendu Gupta, 2005. [Link]
sillas y borrarlas, sin que haya que cias de las combinaciones de cifras [Link]/ffsgupta/sudoku/
valerse, pues, de lápices y gomas de y casillas.

INVESTIGACIÓN Y CIENCIA, agosto, 2006 61