Resolución de sudokus (9)
Pez espada.
Pez espada
Este método es una generalización del X-Wing. Consiste en encontrar tres filas o columnas en las que solo aparezca un candidato en tres casillas de esas tres filas y columnas en las mismas columnas o filas.
En el caso ideal se trataría de un patrón en el que el candidato aparezca en las nueve casillas, como en la imagen, en el que el candidato 2 solo aparece en las columnas segunda, quinta y novena de las filas segunda, cuarta y octava.
En este caso podemos eliminar como candidato el valor 2 en las columnas segunda, quinta y novena de todas las filas excepto la segunda, cuarta y octava.
La explicación es simple. Por ejemplo, para la segunda fila tenemos tres posibilidades para colocar el 2:
- En la segunda columna. Esto nos deja un patrón X-Wing en las filas cuarta y octava, que nos permite eliminar como candidato el 2 en la casilla de la sexta fila y quinta columna, y cualquier candidato de las columnas quinta y novena.
- En la quinta columna. Esto nos deja un patrón X-Wing en las filas cuarta y octava, que nos permite eliminar como candidato el 2 en la casilla de la quinta fila y segunda columna. Y cualquier candidato de las columnas segunda y novena.
- En la novena columna. Esto nos permitiría eliminar cualquier candidato de las columnas segunda y quinta.
El razonamiento es el mismo para los candidatos de las filas cuarta y octava.
Sin embargo, es muy raro que que el patrón pez espada aparezca completo, con el candidato en las nueve casillas. Pero, análogamente a lo que ocurre con los trios desnudos, donde no era imprescindible que los tres candidatos apareciesen en las tres casillas, en este método no es necesario que el candidato aparezca en las tres casillas de cada fila o columna, siempre que no aparezca en ninguna otra.
En la imagen del ejemplo 1 tenemos un patrón pez espada incompleto en un sudoku real.
En las filas segunda, quinta y novena, el candidato 9 solo aparece en las filas tercera, cuarta y sexta, aunque está ausente de una casilla en cada fila.
Sin embargo, este patrón nos permite eliminar como candidato el 9 en las casillas marcadas en rojo.
Ahora de nuevo se trata de diseñar un algoritmo para buscar patrones pez espada.
Buscaremos filas o columnas con dos o tres candidatos de un valor determinado, y verificaremos si están en las mismas tres columnas o filas, respectivamente.
No todas las combinaciones de dos candidatos son posibles. Por ejemplo, si las dos filas del patrón tienen dos casillas con el candidato en las mismas columnas, en la tercera, la casilla que completa el patrón estará sola en esa columna, y será un valor final.
Deberemos asegurarnos de que hemos detectado esos valores antes de buscar el patrón de pez espada.
Por lo tanto, en peor caso, en que las tres filas o columnas tengan dos casillas con el candidato cada una, el candidato solo faltará en una casilla de cada columna.
Añadiremos una nueva clase a nuestro programa. MarcasCasillas se encargará de almacenar mediante bits las casillas que contienen una marca de lápiz determinada. Esto nos ayudará a comparar y verificar si diferentes filas o columnas cumplen un patrón de pez espada:
class MarcasCasillas {
private:
unsigned int casillas;
public:
MarcasCasillas(unsigned int c=0) : casillas(c) {}
MarcasCasillas(const MarcasCasillas &m) { casillas = m.casillas; }
void AsignaCasilla(int c);
int CuentaCasillas();
bool ContieneCasilla(int c);
MarcasCasillas &operator=(const MarcasCasillas &m1) { casillas = m1.casillas; return *this; };
MarcasCasillas operator+(const MarcasCasillas &m1);
};
Como hicimos anteriormente con la clase MarcasLapiz, también hemos sobrecargado el constructor copia y los operadores de asignación y suma. Tenemos una función para asignar casillas, otra para contar las casillas asignadas y una tercera para saber si una casilla contiene la marca.
La implementación es muy simple:
void MarcasCasillas::AsignaCasilla(int c) {
casillas |= 1<<c;
}
int MarcasCasillas::CuentaCasillas() {
int cuenta=0;
for(int c=0; c<9; c++) if(ContieneCasilla(c)) cuenta++;
return cuenta;
}
bool MarcasCasillas::ContieneCasilla(int c) {
return (casillas & 1<<c);
}
MarcasCasillas MarcasCasillas::operator+(const MarcasCasillas &m1) {
MarcasCasillas res(0);
res.casillas = this->casillas | m1.casillas;
return res;
}
Con la ayuda de esta clase, el procedimiento para localizar patrones pez espada se simplifica.
También añadiremos dos funciones a las clases Fila y Columna, CuentaCandidato para contar las veces que aparece un candidato, y Marcas, que devolverá en un objeto MarcasCasillas con las casillas que tengan con un candidato concreto:
class Fila {
private:
...
public:
...
int CuentaCandidato(int v);
MarcasCasillas Marcas(int v);
};
La implementación es simple:
int Fila::CuentaCandidato(int v) {
int cuenta = 0;
for(int c=0; c<9; c++) {
if(cas[c]->Lapiz().ContieneMarca(v)) cuenta++;
}
return cuenta;
}
MarcasCasillas Fila::Marcas(int v) {
MarcasCasillas m;
for(int c=0; c<9; c++) {
if(cas[c]->Lapiz().ContieneMarca(v)) m.AsignaCasilla(c);
}
return m;
}
Esto nos ayudará a simplificar mucho las funciones para detectar patrones.
Para buscar patrones pez espada en filas, nuestra función queda así:
bool Tablero::BuscaSwordFishFilas(int v) {
bool retval=false;
MarcasCasillas CasillasFilas;
MarcasCasillas CasillasColumnas;
for(int f1=0; f1<7; f1++) {
// Buscamos en las primeras 7 filas en las que no aparezca v
// y esté como candidato en 2, 3 columnas:
if(!fila[f1].Presente(v) && fila[f1].CuentaCandidato(v) <= 3) {
// Ahora buscamos las filas f1+1 a septima otra que tenga 2, 3 candidatos v.
for(int f2= f1+1; f2<8; f2++) {
if(!fila[f2].Presente(v) && fila[f2].CuentaCandidato(v) <= 3) {
// Si entre las dos filas, el candidato aparece en 3 columnas, buscamos otra fila
CasillasColumnas = fila[f1].Marcas(v)+fila[f2].Marcas(v);
if(CasillasColumnas.CuentaCasillas() == 3) {
// Ahora buscamos las filas f2+1 a novena otra que tenga 2, 3 candidatos v en las
// mismas columnas que las anteriores.
for(int f3=f2+1; f3<9; f3++) {
if(!fila[f3].Presente(v) && fila[f3].CuentaCandidato(v) <= 3) {
CasillasColumnas = fila[f1].Marcas(v)+fila[f2].Marcas(v)+fila[f3].Marcas(v);
if(CasillasColumnas.CuentaCasillas() == 3) {
// Tenemos una medusa.
CasillasFilas.AsignaCasilla(f1);
CasillasFilas.AsignaCasilla(f2);
CasillasFilas.AsignaCasilla(f3);
if(ProcesaSwordFishFilas(CasillasFilas, CasillasColumnas, v)) return true;
}
}
}
}
}
}
}
}
return retval;
}
La función para buscar y procesar patrones pez espada por columnas es análoga.
Tenemos que procesar los patrones detectados, eliminando los candidatos correspondientes, si los hay.
bool Tablero::ProcesaSwordFishFilas(MarcasCasillas fils, MarcasCasillas cols, int v) {
bool retval = false;
for(int f=0; f<9; f++) {
if(!fils.ContieneCasilla(f)) {
for(int c=0; c<9; c++) {
if(cols.ContieneCasilla(c)) {
retval |= casilla[f][c].Lapiz().EliminaMarca(v);
}
}
}
}
return retval;
}
También añadiremos la función equivalente para patrones pez espada en columnas.
Finalmente, la función ProcesaSwordFish, que busca y procesa todas las filas y columnas para cada valor:
bool Tablero::ProcesaSwordFish() {
bool retval=false;
for(int v=1; v<=9; v++) {
retval |= BuscaSwordFishFilas(v);
retval |= BuscaSwordFishColumnas(v);
}
return retval;
}
| Nombre | Fichero | Fecha | Tamaño | Contador | Descarga |
|---|---|---|---|---|---|
| Sudoku10 | sudoku10.zip | 2022-06-22 | 27928 bytes | 414 |