Resolución de sudokus (19)
Rectángulos de solución única ocultos
En su estado actual, nuestro programa resuelve casi el 95% de los 60000 sudokus probados. Seguiremos centrándonos en los que aún no puede resolver a ver si podemos incorporar nuevos métodos para eliminar candidatos.
Evidentemente, los sudokus que aún no podemos resolver podríamos catalogarlos como muy difíciles, de modo que los métodos que se deben aplicar para resolverlos serán cada vez más complejos, tanto para detectarlos como para explicar su funcionamiento y, a menudo, también para implementar sus algoritmos.
Reconozco que la lógica detrás de los métodos que vamos a usar a continuación me resulta poco intuitiva, pero funcionan.
Empecemos con el sudoku de la imagen de la derecha, que es uno de los de 27 pistas que aún no podemos resolver.
El patrón estará formado por cuatro casillas formando un rectángulo, ocupando dos cajas diferentes.
Nuestro punto de partida es la casilla con dos candidatos, en este ejemplo es la casilla A7, con los candidatos 4 y 6.
Las otras tres casillas deben tener también esos dos candidatos, y algunos más, cuyos valores en este método son irrelevantes.
Esas tres casillas determinan una fila y una columna. En este ejemplo la fila D y la columna 9.
Es determinante que en esa fila y columna uno de los candidatos, el 4 o el 6, sólo aparezca en las dos casillas que forman el patrón.
En este ejemplo, el candidato 6, en la fila D sólo aparece en las casillas D7 y D9, y en la columna 9 en las casillas A9 y D9.
En este caso, ese patrón puede esconder un rectángulo de solución única con la pareja de candidatos 4 y 6.
Explicación
Si se cumplen las condiciones anteriores podremos aplicar esta técnica, que nos permitirá eliminar un candidato en una de las casillas.
Tenemos este patrón, formado por las casillas A7, A9, D7 y D9 y los candidatos 4 y 6.
Nos centraremos en la casilla opuesta a la que sólo tiene dos candidatos, en este ejemplo D9. Con respecto al candidato 6, podemos plantear dos situaciones posibles:
- La casilla D9 tiene el valor 6, en cuyo caso podremos que eliminar el 6 como candidato en A9 y D7. En A7 quedarían como candidatos el 4 y el 6.
- La casilla D9 no tiene el valor 6. En ese caso, el 6 tendrá que estar en las casillas A9 y D7, dejando como único valor posible para la casilla A7 el 4.
Un caso particular de la opción 2 es que el valor de D9 sea el 4. De nuevo, el valor 6 tendrá que estar en las casillas A9 y D7, pero eso implica que en A7 debe haber un 4. En ese caso estaríamos ante un patrón en el que se podrían intercambiar los valores 4 y 6, similar al patrón de solución única que vimos en el artículo 10.
Por lo tanto, el candidato 4 no puede ser una solución para D9.
En este sudoku hay otro patrón similar, en las casillas C4, C6, F4 y F6, con los candidatos 1 y 7. En este caso podemos eliminar como candidato el 7 en F6.
Lamentablemente, en este ejemplo eliminar estos dos candidatos tampoco hace que nuestro programa pueda resolver este sudoku concreto, tan sólo nos acerca un poco más a la solución.
Algoritmo
Veamos el algoritmo para detectar estos patrones:
- Empezaremos por buscar una casilla con dos candidatos. Casilla Q1, en fila f1, columna c1, con los candidatos a y b.
- En la fila f1 buscaremos una casilla que también tenga esos candidatos. Casilla Q2 en f1, c2.
- Si en la columna c2 uno de los candidatos a o b aparece sólo en dos casillas:
- Determinamos el valor del candidato que sólo aparece en dos casillas de la columna.
(Sólo puede ser uno de los candidatos, a o b, ya que si fuesen los dos estaríamos ante un par oculto)
Al valor que sólo aparece en dos casillas lo llamaremos d, y al otro e.
- La casilla Q3, en f2, c2 debe tener los candidatos a y b, y será la única otra casilla con el candidato d en esa columna.
- Si en la casilla Q4, en f2, c1 contiene los dos candidatos a y b, y el candidato d sólo aparece en las columnas c1 y c2.
- Si las cuatro casillas ocupan sólo dos cajas
- Procesamos el patrón.
- Buscar en otra columna Q2.
- Buscar otra casilla con dos candidatos
El procedimiento para implementar este algoritmo no es muy complicado:
bool Tablero::BuscaRectanguloSolucionUnicaOculto() {
int f1, f2, c1, c2, a, b, d, e;
for(f1=0; f1<9; f1++) {
for(c1=0; c1<9; c1++) {
if(casilla[f1][c1].Lapiz().CuentaMarcas() == 2) {
a = casilla[f1][c1].Lapiz().ValorMarca(1);
b = casilla[f1][c1].Lapiz().ValorMarca(2);
// Buscar en la misma fila f1, un casilla con las dos marcas a y b
for(c2=0; c2<9; c2++) {
d=e=0;
// Verificar si a o b sólo aparecen dos veces en la columna c2
if(c2!=c1) {
if(columna[c2].CuentaCandidato(a) == 2) { d=a; e=b; }
else if(columna[c2].CuentaCandidato(b) == 2) { d=b; e=a; }
if(d!=0 && (casilla[f1][c1].Lapiz() & casilla[f1][c2].Lapiz()) == casilla[f1][c1].Lapiz()) {
for(int f=0; f<9; f++) {
if(f!=f1 && casilla[f][c2].Lapiz().ContieneMarca(d)) f2=f;
}
// Verificar c1,f2
if(fila[f2].CuentaCandidato(d) == 2 &&
(casilla[f2][c1].Lapiz() & casilla[f1][c1].Lapiz()) == casilla[f1][c1].Lapiz() &&
(f1/3 == f2/3 || c1/3 == c2/3)) { // El patrón ocupa dos cajas
if(ProcesarRectanguloSolucionUnicaOculto(f1, f2, c1, c2, e)) return true;
}
}
}
}
}
}
}
return false;
}
Una vez localizado el patrón, para procesarlo tan solo hay que eliminar como candidato el valor e de la casilla opuesta a Q1, es decir de f2, c2.
Patrón de rectángulo de solución única oculto tipo B
Existen otras variantes de este patrón en las que dos de las casillas del patrón tienen sólo dos candidatos, en una misma fila o columna. Por ejemplo, en el sudoku de la izquierda dos de las casillas en la columna 9 en cajas diferentes tienen sólo dos candidatos. Otra posible variante es que las casillas con dos candidatos estén en la misma caja.
Este patrón equivale a dos patrones superpuestos del tipo anterior, y puede, potencialmente, eliminar dos candidatos en dos casillas diferentes, por lo que en general resultará más útil.
Procesaremos ambas variantes usando un nuevo algoritmo, ya que no podemos procesarlas como dos del tipo A, pues si se elimina uno de los candidatos en una casilla, el patrón deja de existir, y no sería posible eliminar el otro candidato.
- Buscaremos un par desnudo en una fila o columna.
- Si el par está en una fila, buscaremos otra fila en la que las casillas en las mismas columnas tengan los mismos candidatos.
- Si se cumple que el patrón ocupa dos cajas, y que al menos uno de los candidatos sólo aparece dos veces en una de las columnas
- Procesaremos el patrón.
- Si el par está en una columna, buscaremos otra columna en la que las casillas en las mismas columnas tengan los mismos candidatos.
- Si se cumple que el patrón ocupa dos cajas, y que al menos uno de los candidatos sólo aparece dos veces en una de las filas
- Procesaremos el patrón.
A la hora de procesar el patrón tenemos que tener en cuenta el caso de este ejemplo.
Partimos del par desnudo 4, 8, en las casillas C9 y F9.
A continuación verificamos que en la fila C, el candidato 8 sólo aparece en dos casillas, esto nos permite eliminar como candidato el valor 4 en F8.
Luego verificaremos que en la fila F, el candidato 4 sólo aparece en dos casillas, esto nos permite eliminar como candidato el valor 8 en C8.
Pero previamente hemos eliminado el candidato 4 en F8, de modo que en realidad, en la fila F el 4 sólo aparece en una casilla.
Ante esta situación tenemos dos opciones:
- Marcar el valor final en la casilla que contiene el único candidato, en este caso, e 4 en F8.
- Recordar que hemos eliminado un candidato en la fila, y tenerlo en cuenta al verificar sí ese candidato aparece sólo dos veces en la fila.
En el programa hemos optado por la segunda opción.
bool Tablero::BuscaRectanguloSolucionUnicaOcultoB() {
int f1, c1, f2, c2, a, b;
for(f1=0; f1<9; f1++) {
for(c1=0; c1<9; c1++) {
f2=c2=-1;
if(casilla[f1][c1].ParDesnudoFila() || casilla[f1][c1].ParDesnudoColumna()) {
if(casilla[f1][c1].ParDesnudoFila())
c2 = casilla[f1][c1].ParDesnudo(Casilla::enfila)->Columna();
else
f2 = casilla[f1][c1].ParDesnudo(Casilla::encolumna)->Fila();
a = casilla[f1][c1].Lapiz().ValorMarca(1);
b = casilla[f1][c1].Lapiz().ValorMarca(2);
if(f2==-1) { // Buscar en otra columna dos casillas con los candidatos a y b
for(f2=0; f2<9; f2++) {
if(f2!=f1 && (f1/3==f2/3 || c1/3 == c2/3) && // Sólo en dos cajas
(casilla[f2][c1].Lapiz() & casilla[f1][c1].Lapiz()) == casilla[f1][c1].Lapiz() &&
(casilla[f2][c2].Lapiz() & casilla[f1][c2].Lapiz()) == casilla[f1][c2].Lapiz()) {
if(columna[c1].CuentaCandidato(a) == 2 || columna[c1].CuentaCandidato(b) == 2 ||
columna[c2].CuentaCandidato(a) == 2 || columna[c2].CuentaCandidato(b) == 2) {
if(ProcesarRectanguloSolucionUnicaOcultoBf(f1, f2, c1, c2, a, b)) return true;
}
}
}
}
else
if(c2==-1) { // Buscar en otra fila dos casillas con los candidatos a y b
for(c2=0; c2<9; c2++) {
if(c2!=c1 && (f1/3==f2/3 || c1/3 == c2/3) && // Sólo en dos cajas
(casilla[f1][c2].Lapiz() & casilla[f1][c1].Lapiz()) == casilla[f1][c1].Lapiz() &&
(casilla[f2][c2].Lapiz() & casilla[f2][c1].Lapiz()) == casilla[f2][c1].Lapiz()) {
if(fila[f1].CuentaCandidato(a) == 2 || fila[f1].CuentaCandidato(b) == 2 ||
fila[f2].CuentaCandidato(a) == 2 || fila[f2].CuentaCandidato(b) == 2) {
if(ProcesarRectanguloSolucionUnicaOcultoBc(f1, f2, c1, c2, a, b)) return true;
}
}
}
}
}
}
}
return false;
}
Para facilitar la tarea añadiremos tres métodos a la clase Casilla:
bool ParDesnudoFila() {return ParDesnudo(enfila)!=nullptr;}/**< Devuelve true si la casilla forma parte de un par desnudo en fila */
bool ParDesnudoColumna() { return ParDesnudo(encolumna)!=nullptr;}/**< Devuelve true si la casilla forma parte de un par desnudo en columna */
bool ParDesnudoCaja() { return ParDesnudo(encaja)!=nullptr;}/**< Devuelve true si la casilla forma parte de un par desnudo en caja */
Bibliografía
La página del SudokuWiki contiene una explicación de este método en la sección Hidden_Unique_Rectangles.
| Nombre | Fichero | Fecha | Tamaño | Contador | Descarga |
|---|---|---|---|---|---|
| Sudoku 24 | sudoku24.zip | 2025-12-16 | 50736 bytes | 22 |