Master Sudoku, de Marcelo Calniquer.
Esta semana recibí un correo electrónico de un amable lector de este blog, Marcelo Calniquer. Es un ingeniero de sistemas que desarrolló un software para jugar sudokus, que sirve también como solucionador de sudokus y generador de sudokus. Su sitio en internet es www.mastersudoku.com.ar, desde donde pueden bajar gratis el software.
Para solucionar los sudokus ocupa las técnicas explicadas en este blog. Tiene una apariencia similar a como si uno estuviera solucionando un sudoku con lápiz y papel, con las ayudas lógicas de un programa computacional como por ejemplo resolver paso a paso o mostrar en forma destacada los dígitos que a uno le interesa explorar. Además es posible ver el registro de los desarrollos que hace el programa cuando resuelve un puzzle. Es muy interesante. Hoy lo he probado con un sudoku extremadamente difícil publicado en un foro de internet por MattM.
El software de Marcelo lo resolvió en un par de segundos. Les copio el registro para que lo examinen paso a paso.
+---+---+---+
|230|005|010|
|010|800|092|
|000|000|000|
+---+---+---+
|390|080|600|
|000|907|000|
|001|060|028|
+---+---+---+
|000|000|000|
|850|002|070|
|060|700|043|
+---+---+---+
<<<>>>
1) Sencillo Descubierto {5} en f4c8
2) Sencillo Descubierto {3} en f5c8
3) Sencillo Oculto {9} en f6c7
4) Sencillo Descubierto {1} en f8c7
5) Sencillo Descubierto {4} en f5c7
6) Sencillo Descubierto {1} en f5c9
7) Sencillo Descubierto {7} en f4c9
8) Pares Descubiertos {4,6} en f1c4 f1c9
-> Se excluyó el candidato 4 de la posición f1c3
-> Se excluyó el candidato 6 de la posición f1c3
-> Se excluyó el candidato 4 de la posición f1c5
9) X-Wing {6} en f1c4 f8c4 f1c9 f8c9
-> Se excluyó el candidato 6 de la posición f3c4
-> Se excluyó el candidato 6 de la posición f7c4
-> Se excluyó el candidato 6 de la posición f3c9
-> Se excluyó el candidato 6 de la posición f7c9
10) XYZ-Wing {4} en f2c6 f1c4 f6c6
-> Se excluyó el candidato 4 de la posición f3c6
11) Cadena XY {1} en f4c6 f4c3 f9c3 f9c1
-> Se excluyó el candidato 1 de la posición f9c6
12) Cadena XY {9} en f1c5 f1c7 f3c8 f1c9 f3c9 f7c9
-> Se excluyó el candidato 9 de la posición f7c5
13) Cadena Inferencia Alterna Débil {2} 2[f5c3]-2[f5c5]=5[f5c5]-5[f9c5]=5[f9c7]-2[f9c7]=2[f9c3]-2[f5c3]
-> Se excluyó el candidato 2 de la posición f5c3
14) Cadena Inferencia Alterna Continua {2} 2[f4c3]-2[f9c3]=2[f9c7]-5[f9c7]=5[f9c5]-5[f5c5]=2[f5c5]-2[f5c2]=2[f4c3]
-> Se excluyó el candidato 2 de la posición f7c3
-> Se excluyó el candidato 8 de la posición f9c7
15) Sencillo Oculto {8} en f9c6
16) Rectángulos Vacios {9} en f1c3 f1c5 f7c3 f7c6 f8c5 f9c5
-> Se excluyó el candidato 9 de la posición f7c3
17) XY-Wing {9} en f9c7 f7c9 f9c3
-> Se excluyó el candidato 9 de la posición f7c1
18) Rectángulos Vacios {9} en f1c5 f1c3 f9c5 f8c3 f9c1 f9c3
-> Se excluyó el candidato 9 de la posición f9c5
19) Candidato Bloqueado {9} en f9c1 f9c3
-> Se excluyó el candidato 9 de la posición f8c3
20) Cadena Inferencia Alterna Débil {1} 1[f7c6]-9[f7c6]=9[f3c6]-9[f3c1]=9[f9c1]-1[f9c1]=1[f9c5]-1[f7c6]
-> Se excluyó el candidato 1 de la posición f7c6
21) Cadena Inferencia Alterna Continua {5} 5[f9c5]-5[f5c5]=2[f5c5]-2[f5c2]=2[f7c2]-2[f7c7]=2[f9c7]-5[f9c7]=5[f9c5]
-> Se excluyó el candidato 5 de la posición f7c5
22) Cadena Inferencia Alterna Continua {6} 6[f7c6]-9[f7c6]=9[f7c9]-9[f8c9]=6[f8c9]-6[f1c9]=6[f1c4]-6[f8c4]=6[f7c6]
-> Se excluyó el candidato 3 de la posición f7c6
-> Se excluyó el candidato 4 de la posición f7c6
23) Cadena Inferencia Alterna Débil {3} 3[f3c6]-9[f3c6]=9[f7c6]-9[f7c9]=5[f7c9]-5[f7c4]=5[f6c4]-3[f6c4]=3[f6c6]-3[f3c6]
-> Se excluyó el candidato 3 de la posición f3c6
24) Cadena Inferencia Alterna Débil {5} 5[f3c1]-9[f3c1]=9[f9c1]-9[f9c3]=2[f9c3]-2[f9c7]=5[f9c7]-5[f7c9]=5[f3c9]-5[f3c1]
-> Se excluyó el candidato 5 de la posición f3c1
25) Cadena Inferencia Alterna Débil {6} 6[f3c1]-9[f3c1]=9[f9c1]-1[f9c1]=1[f9c5]-5[f9c5]=5[f5c5]-5[f5c1]=6[f5c1]-6[f3c1]
-> Se excluyó el candidato 6 de la posición f3c1
26) Cadena Inferencia Alterna Débil {7} 7[f7c2]-2[f7c2]=2[f7c7]-2[f9c7]=2[f9c3]-2[f4c3]=4[f4c3]-4[f6c2]=7[f6c2]-7[f7c2]
-> Se excluyó el candidato 7 de la posición f7c2
27) Cadena Inferencia Alterna Débil {9} 9[f3c3]-9[f3c6]=9[f7c6]-9[f7c9]=5[f7c9]-5[f9c7]=2[f9c7]-2[f9c3]=9[f9c3]-9[f3c3]
-> Se excluyó el candidato 9 de la posición f3c3
28) Cadena Inferencia Alterna Débil {9} 9[f3c5]-2[f3c5]=2[f3c4]-2[f4c4]=2[f4c3]-2[f9c3]=9[f9c3]-9[f9c1]=9[f3c1]-9[f3c5]
-> Se excluyó el candidato 9 de la posición f3c5
El puzzle se resolvió por fuerza bruta
-> Sencillo Descubierto: 6
-> Sencillo Oculto: 2
-> Candidatos Bloqueados: 1
-> Pares Descubiertos: 1
-> X-Wing: 1
-> Rectángulos Vacíos: 2
-> XY-Wing: 1
-> XYZ-Wing: 1
-> Cadenas XY: 2
-> Cadena Inferencia Alterna: 11
+---+---+---+
|238|495|716|
|514|876|392|
|976|231|584|
+---+---+---+
|392|184|657|
|685|927|431|
|741|563|928|
+---+---+---+
|427|319|865|
|853|642|179|
|169|758|243|
+---+---+---+
¡Brillante, le bastaron sólo 28 pasos para resolverlo! Excelente programa Marcelo. Felicitaciones. Aún no he probado el generador de sudokus; ya lo comentaré una vez que haya hecho algunas pruebas.|230|005|010|
|010|800|092|
|000|000|000|
+---+---+---+
|390|080|600|
|000|907|000|
|001|060|028|
+---+---+---+
|000|000|000|
|850|002|070|
|060|700|043|
+---+---+---+
<<<>>>
1) Sencillo Descubierto {5} en f4c8
2) Sencillo Descubierto {3} en f5c8
3) Sencillo Oculto {9} en f6c7
4) Sencillo Descubierto {1} en f8c7
5) Sencillo Descubierto {4} en f5c7
6) Sencillo Descubierto {1} en f5c9
7) Sencillo Descubierto {7} en f4c9
8) Pares Descubiertos {4,6} en f1c4 f1c9
-> Se excluyó el candidato 4 de la posición f1c3
-> Se excluyó el candidato 6 de la posición f1c3
-> Se excluyó el candidato 4 de la posición f1c5
9) X-Wing {6} en f1c4 f8c4 f1c9 f8c9
-> Se excluyó el candidato 6 de la posición f3c4
-> Se excluyó el candidato 6 de la posición f7c4
-> Se excluyó el candidato 6 de la posición f3c9
-> Se excluyó el candidato 6 de la posición f7c9
10) XYZ-Wing {4} en f2c6 f1c4 f6c6
-> Se excluyó el candidato 4 de la posición f3c6
11) Cadena XY {1} en f4c6 f4c3 f9c3 f9c1
-> Se excluyó el candidato 1 de la posición f9c6
12) Cadena XY {9} en f1c5 f1c7 f3c8 f1c9 f3c9 f7c9
-> Se excluyó el candidato 9 de la posición f7c5
13) Cadena Inferencia Alterna Débil {2} 2[f5c3]-2[f5c5]=5[f5c5]-5[f9c5]=5[f9c7]-2[f9c7]=2[f9c3]-2[f5c3]
-> Se excluyó el candidato 2 de la posición f5c3
14) Cadena Inferencia Alterna Continua {2} 2[f4c3]-2[f9c3]=2[f9c7]-5[f9c7]=5[f9c5]-5[f5c5]=2[f5c5]-2[f5c2]=2[f4c3]
-> Se excluyó el candidato 2 de la posición f7c3
-> Se excluyó el candidato 8 de la posición f9c7
15) Sencillo Oculto {8} en f9c6
16) Rectángulos Vacios {9} en f1c3 f1c5 f7c3 f7c6 f8c5 f9c5
-> Se excluyó el candidato 9 de la posición f7c3
17) XY-Wing {9} en f9c7 f7c9 f9c3
-> Se excluyó el candidato 9 de la posición f7c1
18) Rectángulos Vacios {9} en f1c5 f1c3 f9c5 f8c3 f9c1 f9c3
-> Se excluyó el candidato 9 de la posición f9c5
19) Candidato Bloqueado {9} en f9c1 f9c3
-> Se excluyó el candidato 9 de la posición f8c3
20) Cadena Inferencia Alterna Débil {1} 1[f7c6]-9[f7c6]=9[f3c6]-9[f3c1]=9[f9c1]-1[f9c1]=1[f9c5]-1[f7c6]
-> Se excluyó el candidato 1 de la posición f7c6
21) Cadena Inferencia Alterna Continua {5} 5[f9c5]-5[f5c5]=2[f5c5]-2[f5c2]=2[f7c2]-2[f7c7]=2[f9c7]-5[f9c7]=5[f9c5]
-> Se excluyó el candidato 5 de la posición f7c5
22) Cadena Inferencia Alterna Continua {6} 6[f7c6]-9[f7c6]=9[f7c9]-9[f8c9]=6[f8c9]-6[f1c9]=6[f1c4]-6[f8c4]=6[f7c6]
-> Se excluyó el candidato 3 de la posición f7c6
-> Se excluyó el candidato 4 de la posición f7c6
23) Cadena Inferencia Alterna Débil {3} 3[f3c6]-9[f3c6]=9[f7c6]-9[f7c9]=5[f7c9]-5[f7c4]=5[f6c4]-3[f6c4]=3[f6c6]-3[f3c6]
-> Se excluyó el candidato 3 de la posición f3c6
24) Cadena Inferencia Alterna Débil {5} 5[f3c1]-9[f3c1]=9[f9c1]-9[f9c3]=2[f9c3]-2[f9c7]=5[f9c7]-5[f7c9]=5[f3c9]-5[f3c1]
-> Se excluyó el candidato 5 de la posición f3c1
25) Cadena Inferencia Alterna Débil {6} 6[f3c1]-9[f3c1]=9[f9c1]-1[f9c1]=1[f9c5]-5[f9c5]=5[f5c5]-5[f5c1]=6[f5c1]-6[f3c1]
-> Se excluyó el candidato 6 de la posición f3c1
26) Cadena Inferencia Alterna Débil {7} 7[f7c2]-2[f7c2]=2[f7c7]-2[f9c7]=2[f9c3]-2[f4c3]=4[f4c3]-4[f6c2]=7[f6c2]-7[f7c2]
-> Se excluyó el candidato 7 de la posición f7c2
27) Cadena Inferencia Alterna Débil {9} 9[f3c3]-9[f3c6]=9[f7c6]-9[f7c9]=5[f7c9]-5[f9c7]=2[f9c7]-2[f9c3]=9[f9c3]-9[f3c3]
-> Se excluyó el candidato 9 de la posición f3c3
28) Cadena Inferencia Alterna Débil {9} 9[f3c5]-2[f3c5]=2[f3c4]-2[f4c4]=2[f4c3]-2[f9c3]=9[f9c3]-9[f9c1]=9[f3c1]-9[f3c5]
-> Se excluyó el candidato 9 de la posición f3c5
El puzzle se resolvió por fuerza bruta
-> Sencillo Descubierto: 6
-> Sencillo Oculto: 2
-> Candidatos Bloqueados: 1
-> Pares Descubiertos: 1
-> X-Wing: 1
-> Rectángulos Vacíos: 2
-> XY-Wing: 1
-> XYZ-Wing: 1
-> Cadenas XY: 2
-> Cadena Inferencia Alterna: 11
+---+---+---+
|238|495|716|
|514|876|392|
|976|231|584|
+---+---+---+
|392|184|657|
|685|927|431|
|741|563|928|
+---+---+---+
|427|319|865|
|853|642|179|
|169|758|243|
+---+---+---+
Volviendo un poco al sudoku del ejemplo, podemos resolverlo de una manera sencilla de la siguiente manera. Primero resolvemos todos los singles, como por ejemplo el 5 de la sexta caja. El sudoku queda de la siguiente manera:
Ahora vemos que existen gemelas [4,6] en la primera fila. Resolviendo la fila, el puzzle queda como sigue:
Aquí es donde sacamos nuestro as de la manga de la camisa. El diagrama siguiente muestra una cadena de implicancias al modo mostrado el 25 de noviembre de 2007.
Siguiendo esta cadena en azul, se deduce que si {f5,c3}=8 entonces {f5,c2}=8. Pero no pueden haber dos 8 en la quinta fila, luego {f5,c3} no puede ser 8. Al eliminar el 8 de la celda {f5,c3}, el sudoku se convierte en un sudoku trivial en el que siempre es posible encontrar un único candidato posible para alguna celda, o una única celda para algún candidato. Lo difícil, por no decir lo imposible, era aquí encontrar la dichosa cadena de implicancias mostrada en azul.
Bueno, todo esto me ha animado a buscarme el tiempo para continuar con el plan trazado en este blog el 15 de julio de 2007, y que por escasez de tiempo precisamente me he visto forzado a no continuar. Pero quedan varias técnicas aún por describir.
Hasta la próxima.
No hay comentarios.:
Publicar un comentario