Resolver SUDOKUS

El SUDOKU es una cuadrícula de 9 por 9 casillas que hay que rellenar con las cifras del 1 al 9 de forma que no haya dos cifras iguales en un mismo grupo ni en una misma fila ni en una misma columna. Hay muchas formas de rellenar esta cuadrícula de forma que cumpla esas condiciones (unos cinco mil quinientos millones) por lo que en el juego aparecen ya unas cuantas casillas rellenas de forma que sólo haya una manera de completarlo. Si hay más de una forma de completarlo el Sudoku está mal planteado. Como curiosidad, a fecha de hoy se piensa que el número mínimo de cifras a fijar de entrada es 16, pero sólo se han encontrado Sudokus de 17 cifras fijas y solución única.

Colum1 Colum2 Colum3     

F	I	L		A		1
GR	UPO	1		GR	UPO	2		GR	UPO	3
F	I	L		A		3
F	I	L		A		4
GR	UPO	4		GR	UPO	5		GR	UPO	6
GR	UPO	7		GR	UPO	8		GR	UPO	9
F	I	L		A		9

Dependiendo de la dificultad en resolverlos se habla de fácil, medio, difícil y diabólico. Un ejemplo de diabólico sacado de una web que permite obtener miles de millones de sudokus distintos de cada nivel: http://www.websudoku.com

 

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

Mi experiencia es que con dos reglas básicas y otra algo más compleja, se puede resolver cualquier tipo de Sudoku. Agradecería mucho recibir algún sudoku correcto que no pueda resolverse de la manera que voy a exponer.

Regla 1: Si N números sólo pueden ir en exactamente N casillas de un grupo, fila o columna, no puede haber otros números distintos en esas casillas.

Para N=1 la regla es de Sudoku fácil: si un número X sólo puede ir en una casilla de un grupo/fila/columna, no puede haber otro número distinto en esa casilla que, por lo tanto, rellenamos con X. En el sudoku anterior es el caso del 9 rojo (ver abajo): la única casilla del grupo 4 en la que puede ir es en la que está, para no colisionar con los nueves de las filas 4 y 5 o con el de la columna 2

Regla 2: Si en N casillas de un grupo,fila o columna, solo pueden ir exactamente N números, éstos no se pueden ir en otras casillas distintas del grupo, fila o columna.

Para N=1 quiere decir obviamente que si en una casilla sólo puede ir un número X, éste ya se puede colocar en ella.

Ambas reglas son inmediatas para N=1 (es la base de los sudokus 'fáciles') y no tan fáciles de aplicar para N mayor que 1. Luego veremos un método para aplicarlo.

Aparte hay otra regla que ayuda a simplificar trabajo en muchos casos y que relaciona filas/columnas con grupos:

Regla 3: Si un número sólo puede ir dentro de un grupo en una fila o columna, no puede estar en otras casillas de esa fila o columna de otros grupos.

Esto es un poco más difícil de entender, pero tenemos un ejemplo en el sudoku anterior: En el grupo 6, el 4 sólo puede ir en la columna 7 para no coincidir con los 4´s de la columna 8 y el de la fila 4. Pues bien, en el grupo 3 el 4 sólo podrá ir en la columna 9 para no coincidir con el que forzosamente ha de ir en la 7.

Partiendo de estas reglas, vamos a ver una forma de solucionar cualquier Sudoku en varios pasos. Hay que tener en cuenta que cada vez que ponemos un número en cualquier paso se debe volver al PASO 1 otra vez.

PASO1: Aplicar la Regla 1 para N=1. Es decir, colocar todos los números que sólo puedan ir en una casilla de un grupo, fila o columna. Hay que tener en cuenta que cada vez que se coloca un número cambian las condiciones y puede ser que ahora se pueda poner otro número que antes no era posible. Igualmente aplicar la regla 2 para N=1, es decir, casillas en las que sólo puede ir un número. Lo mismo que antes, cada número nuevo exige una nueva inspección de ambas reglas.

Con el sudoku anterior, aplicando estas reglas para N=1 colocamos los números en rojo:

 

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

Con el suficiente entrenamiento y paciencia podemos aplicar las reglas para N>1mentalmente (este sería el objetivo último: resolver Sudokus de cualquier nivel sin tomar anotaciones) pero hasta conseguir esa práctica aplicamos el método de apuntar en cada casilla libre los números que pueden ir en tamaño pequeño para que quepan.

PASO 2 : poner en cada casilla libre los números que pueden ir en ella en tamaño pequeño teniendo en cuenta las reglas del Sudoku (no coincidir con fila, columna o grupo). Este paso ya no va a hacer falta repetirlo, lo que vamos a hacer ahora es ir tachando los números según las reglas definidas hasta que quede una posibilidad. En el Sudoku que estamos haciendo, el resultado es:

 

1458	6	24589	2489	27	289	1245	3	12479
145	12457	2459	2469	267	3	12456	12569	8
48	2478	3	5	1	2689	246	269	24679
7	258	258	3	4	1256	9	126	126
6	3	24	12	9	7	124	8	5
9	245	1	26	8	256	246	7	3
158	158	568	12689	3	4	7	12569	1269
2	1458	4568	7	56	15689	3	1569	169
3	9	7	126	256	1256	8	4	126

PASO 3: Aplicamos la regla 3 para reducir algo los números. En este caso, hemos tachado los 4´s del grupo3 columna7 porque en el grupo6 sólo pueden ir cuatros en la columna7. Por tanto seguro que un 4 ocupará la columna7 del grupo6 y por tanto colisionaría con otro 4 del grupo3 en esa columna. Hemos tachado esos cuatros. También hemos tachado los 5´s del grupo8 columna6 por colisionar con los del grupo5 que solo pueden ir en la misma columna. Y también hemos tachado el cinco del grupo3 columna8 que colisiona con los del grupo9 que forzosamente van en la columna8.Este PASO 3 también es iterativo, cada vez que se coloca un número debe volver a repasarse a ver si se pueden seguir tachando números.

PASO 4: Ahora se trata de ver las reglas 1 y 2 para N>1. Es decir, ver si en N casillas van N números exactamente o si N números solo están en exactamente N casillas. Este es el paso más complejo y hace que los Sudokus se cataloguen como difíciles o diabólicos dependiendo de N=2 ó N=3. Nunca me he encontrado una necesidad de N=4, pero podría haber en teoría hasta N=8.

En el Sudoku que resolvemos tenemos un ejemplo de la Regla 2 para N=3. En efecto en la fila9, en las casillas 4,6 y 9 de esa fila (3 casillas) aparecen los números 1,2 y 6 exactamente 3 números para 3 casillas. Eso quiere decir obviamente que cada uno de los números va por fuerza en una de las casillas (no sabemos cual) y por tanto no pueden estar en la misma fila fuera de esas casillas pues se repetirían. Tachamos pues de la 5ª casilla el 2 y el 6 que no pueden ir y nos encontramos con la agradable sorpresa de que sólo nos queda el 5 como posible. Además al poner ese 5 fijo eliminamos todos los 5´s de sus fila,. columna y grupo y vemos que una casilla más arriba nos queda el 6 como única cifra posible, por lo que a su vez eliminamos los 6 de la fila columna y grupo.

 

 

1458	6	24589	2489	27	289	125	3	12479
145	12457	2459	2469	27	3	1256	1269	8
48	2478	3	5	1	2689	26	269	24679
7	258	258	3	4	1256	9	126	126
6	3	24	12	9	7	124	8	5
9	245	1	26	8	256	246	7	3
158	158	568	1289	3	4	7	12569	1269
2	1458	458	7	6	189	3	159	19
3	9	7	12	5	12	8	4	126

 

Volvemos al Paso1 y vemos que en la última fila, el único 6 que hay está en su casilla 9. Debe ir ahí por lo tanto y tachamos 6´s de fila,columna, grupo. y vemos (Paso1 de nuevo) que en la fila7 sólo hay 6 en la casilla 3. Repetimos proceso:

 

1458	6	24589	2489	27	289	125	3	12479
145	12457	2459	2469	27	3	1256	1269	8
48	2478	3	5	1	2689	26	269	2479
7	258	258	3	4	1256	9	126	12
6	3	24	12	9	7	124	8	5
9	245	1	26	8	256	246	7	3
158	158	6	1289	3	4	7	1259	129
2	1458	458	7	6	189	3	159	19
3	9	7	12	5	12	8	4	6

 

Siguiendo el proceso iterativo, ahora se multiplican posibilidades (suele pasar cuando se ponen las primeras cifras 'difíciles'). Por ejemplo hay un caso de la regla2 para N=2 en la columna4 casillas 5 y 9 Son dos casillas con dos números (1y2) que por tanto se borran del resto de casillas de la columna dejando el 6 de la casilla 6 como única opción. Borramos 6´s relacionados y vemos que en la fila4 solo queda el 6 de la casilla 8. Ponemos y borramos relacionados y vemos que en la columna4 solo queda el 6 de la casilla 6 y en el grupo3 solo queda un sitio para el 6 al borrar y a su vez en el mismo grupo solo queda un sitio para el 2.

 

1458	6	24589	489	27	289	15	3	1479
145	12457	2459	49	27	3	6	169	8
48	478	3	5	1	6	2	9	479
7	258	258	3	4	125	9	6	12
6	3	24	12	9	7	14	8	5
9	245	1	6	8	25	4	7	3
158	158	6	89	3	4	7	1259	129
2	1458	458	7	6	189	3	159	19
3	9	7	12	5	12	8	4	6

Al poner este 2 del grupo3 en la columna7 se ponen todos los números: el 4, luego el 1 por fin el 5. Luego se termina el grupo6 poniendo el 2. También la columna8 y la fila5 y luego el grupo5. Tachamos y queda:

 

148	6	2489	489	27	289	5	3	47
45	2457	2459	49	27	3	6	1	8
48	478	3	5	1	6	2	9	47
7	58	58	3	4	1	9	6	2
6	3	4	2	9	7	1	8	5
9	2	1	6	8	5	4	7	3
158	158	6	89	3	4	7	2	19
2	148	48	7	6	89	3	5	19
3	9	7	1	5	2	8	4	6

 

Ahora es todo muy rápido. Completamos la fila9, la fila6, la fila8 (empezando por el num. 8) y el grupo9:

 

148	6	29	489	27	289	5	3	47
45	57	259	49	27	3	6	1	8
48	78	3	5	1	6	2	9	47
7	58	5	3	4	1	9	6	2
6	3	4	2	9	7	1	8	5
9	2	1	6	8	5	4	7	3
15	15	6	8	3	4	7	2	9
2	4	8	7	6	9	3	5	1
3	9	7	1	5	2	8	4	6

 

Seguimos completando el grupo8, el grupo4:

 

148	6	29	489	27	289	5	3	47
45	57	259	49	27	3	6	1	8
48	78	3	5	1	6	2	9	47
7	8	5	3	4	1	9	6	2
6	3	4	2	9	7	1	8	5
9	2	1	6	8	5	4	7	3
15	15	6	8	3	4	7	2	9
2	4	8	7	6	9	3	5	1
3	9	7	1	5	2	8	4	6

Ponemos el único 8 de la columna 2 y la completamos. Completamos también el grupo 7:

 

148	6	29	489	27	289	5	3	47
4	5	29	49	27	3	6	1	8
48	7	3	5	1	6	2	9	47
7	8	5	3	4	1	9	6	2
6	3	4	2	9	7	1	8	5
9	2	1	6	8	5	4	7	3
5	1	6	8	3	4	7	2	9
2	4	8	7	6	9	3	5	1
3	9	7	1	5	2	8	4	6

Y ya es inmediato: completamos la columna1, el grupo3, y los grupos 2 y 1:

 

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

 

De esta forma se completa el Sudoku. El resumen de los pasos a dar es:

- Rellenar en primer lugar los números que sólo pueden ir en una casilla de un grupo/fila/columna o las casillas que solo admiten un numero. Es aplicar las reglas 1 y 2 para N=1

- Poner a continuación en cada casilla los números posibles en tamaño pequeño.

- Borrar los que sobren a la luz de la regla 3

- Buscar situaciones de la regla 1 y 2 para N>1 que eliminen más números posibles (este es el punto delicado y que llevará más tiempo)

- Repetir los pasos hasta terminar el Sudoku.

Una alternativa que nunca hace falta usar es poner un número de prueba y resolver el Sudoku hasta llegar a una situación ilógica, en cuyo caso se intenta con otra cifra. Esto podría hacerse en los casos de casillas con sólo 2 números posibles. Se intenta con uno y si salen contradicciones se intenta con el otro.

El primer objetivo a conseguir sería no hacer nunca este método de prueba (se consigue con no mucho esfuerzo). El objetivo final sería no necesitar las anotaciones de números. Esto es muy complicado, requiere mucha atención y esfuerzo. Se hace centrando la atención en dónde pueden ir los números de cada fila, columna y grupo por orden buscando situaciones de la regla 1 y 2 para N>1. En los casos en que se necesita N=3 (ya he comentado que no me he encontrado nunca con casos mayores) exige un esfuerzo intelectual grande.