Resolución de sudokus (14)
Hilo de cometa y rectángulos eludibles
Hilo de cometa
Este método probablemente sea más sencillo de aplicar y más intuitivo que otros que hemos visto, como es rascacielos o incluso que XY-Wing. No he encontrado ningún sudoku en el que se pueda aplicar éste método que aporte información que no hayan aportado alguno de los métodos que ya hemos visto. Pero como estos patrones pueden ser más fácil de detectar que otros, lo procesaremos antes que ellos.
La idea es sencilla. Dada una pareja de candidatos en una caja, que no estén en la misma fila ni en la misma columna, si encontramos otras casillas que formen pareja con cada una de ellas en una fila y columna, la intersección de las otras dos casillas no podrá tener ese valor como candidato.
Esto es fácil de ver en el ejemplo de la derecha.
Si suponemos que en la casilla D4 hay un 3, no podrá haberlo en E6, por lo que deberá estar en I6, y podemos eliminarlo como candidato en I2.
Si por el contrario, suponemos que el 3 no está en D4, implicaría que está en D2, por lo que también podemos eliminarlo como candidato en I2.
En cualquiera de los dos casos, el valor 3 no es posible en I2.
Para facilitar la programación añadiremos varias funciones a algunas clases.
Por una parte, añadiremos el método DobleCandidato, que ya existía en las clases Fila y Columna a la clase Caja:
Pareja Caja::DobleCandidato(int v) {
int cuenta=0;
Pareja par;
for(int p=0; p<9; p++) {
if(cas[p]->Lapiz().ContieneMarca(v)) par.Asigna(cuenta++, cas[p]);
}
if(cuenta==2) return par;
return Pareja();
}
También añadiremos los métodos MismaFila y MismaColumna a la clase Pareja:
bool MismaFila() { return cas[0]->Fila() == cas[1]->Fila(); }
bool MismaColumna() { return cas[0]->Columna() == cas[1]->Columna(); }
Para implementar este método añadiremos un par de funciones a la clase Tablero:
class Tablero {
private:
...
bool ProcesarStringKite(Pareja &par, Pareja &parF, Pareja &parC, int v);
public:
...
bool StringKite();
...
};
Y la implementación:
bool Tablero::StringKite() {
Pareja par;
Pareja parF, parC;
for(int v=1; v<=9; v++) {
for(int k=0; k<9; k++) {
par = caja[k].DobleCandidato(v);
if(par.Cas(0) && !par.MismaFila() && !par.MismaColumna()) {
// Buscar par en columna par.Cas(0) y en fila par.Cas(1)
parC = columna[par.Cas(0)->Columna()].DobleCandidato(v);
parF = fila[par.Cas(1)->Fila()].DobleCandidato(v);
if(parC.Cas(0) && parF.Cas(0) && ProcesarStringKite(par, parF, parC, v)) return true;
// Buscar par en fila par.Cas(0) y en columna par.Cas(1)
parC = columna[par.Cas(1)->Columna()].DobleCandidato(v);
parF = fila[par.Cas(0)->Fila()].DobleCandidato(v);
if(parC.Cas(0) && parF.Cas(0) && ProcesarStringKite(par, parF, parC, v)) return true;
}
}
}
return false;
}
bool Tablero::ProcesarStringKite(Pareja &par, Pareja &parF, Pareja &parC, int v) {
int f, c;
if(par.Cas(0) == parC.Cas(0) || par.Cas(1) == parC.Cas(0))
f = parC.Cas(1)->Fila();
else
f = parC.Cas(0)->Fila();
if(par.Cas(0) == parF.Cas(0) || par.Cas(1) == parF.Cas(0))
c = parF.Cas(1)->Columna();
else
c = parF.Cas(0)->Columna();
if(casilla[f][c].Lapiz().EliminaMarca(v)) return true;
return false;
}
| Nombre | Fichero | Fecha | Tamaño | Contador | Descarga |
|---|---|---|---|---|---|
| Sudoku18 | sudoku18.zip | 2022-06-22 | 34800 bytes | 437 |
Pez espada con alas
Al igual que sucede con los patrones X-Wing, con los patrones pez espada también existe una variedad con alas o aletas.
Se trata del mismo patrón pez espada, en el que en una de las cajas con el candidato hay una marca extra en la misma fila o columna. En esa caja podemos combinar el candidato en la casilla extra con el patrón para eliminar candidatos.
Actuaremos de un modo parecido que para buscar patrones pez espada. Por filas o columnas para cada posible valor.
Para un patrón por filas empezaremos buscando dos filas con dos o tres candidatos, que combinadas solo presenten el candidato en tres columnas. La tercera fila del patrón tiene que que tener candidatos en al menos dos de esas columnas, y uno o dos candidatos extra en una de las cajas de las que forman el patrón.
Combinando las exclusiones de candidatos de las casillas extra con las del patrón pez espada, con suerte, podremos eliminar uno o dos candidatos de la caja con candidatos extra.
En el ejemplo de la derecha las filas H e I son nuestras dos primeras filas, que tienen candidatos en las columnas 1, 4 y 9. Por supuesto, no tienen por qué aparecer candidatos en las seis casillas.
La tercera fila tiene candidatos en las tres columnas del patrón, aunque de nuevo, no tienen por qué estar en las tres. El candidato extra, en la casilla E8 es nuestra aleta. El patrón también sería válido si el candidato estuviera en la casilla E7.
Ahora, tal como hicimos con el patrón X-Wing con aletas, tenemos dos posibilidades:
- La casilla E8 tiene el valor 1. En ese caso podemos eliminar todos los candidatos de la caja 6, pero nos fijaremos en D9.
- la casilla E8 no tiene el valor 1. En ese caso podemos aplicar el patrón pez espada, que eliminará los candidatos de las columnas 1, 4 y 9, de nuevo nos fijamos en D9.
En ambos supuestos, los candidatos en D9, y si lo hubiera, en F9, pueden eliminarse.
Explicarlo es sencillo, programar esto ya es otra cosa.
Empezaremos añadiendo algunos métodos a la clase MarcasCasillas que nos ayudarán a manejar la información para detectar estos patrones:
class MarcasCasillas {
private:
...
public:
...
MarcasCasillas operator~();
MarcasCasillas operator&(const MarcasCasillas &m1);
int Cajas();
int Casilla();
void MascaraCaja(int k);
};
El operador ~ invertirá binariamente el valor de casillas, es decir, cambiará ceros por unos y viceversa.
El operador & hará una operación AND de bits con el valor pasado como parámetro.
Cajas calculará en qué cajas hay casillas activas. Lo hará en forma de bits, si en casillas hay alguno de los tres bits de mayor peso activo, devolverá un valor con el tercer bit activo. Si en casillas hay alguno de los bits cuarto a sexto activo, devolverá un valor con el segundo bit activo. Y si en casillas hay activo alguno de los tres primeros bits, devolverá un valor con el primer bit activo. El valor de retorno estará entre 0 y 7.
Casilla devolverá el número de la primera casilla activa, o -1 si no hay ninguna.
MascaraCaja aplicará a casillas una máscara de bits con los bits correspondientes a la caja pasada como parámetro, es decir, dejará activos solo los bits correspondientes a la caja k.
La implementación es simple:
MarcasCasillas MarcasCasillas::operator~() {
MarcasCasillas res(0);
res.casillas = ~this->casillas;
return res;
}
MarcasCasillas MarcasCasillas::operator&(const MarcasCasillas &m1) {
MarcasCasillas res(0);
res.casillas = this->casillas & m1.casillas;
return res;
}
int MarcasCasillas::Cajas() {
int retval = 0;
if(casillas & 0x1c0) retval += 4;
if(casillas & 0x38) retval += 2;
if(casillas & 0x7) retval += 1;
return retval;
}
int MarcasCasillas::Casilla() {
for(int c=1; c<=9; c++) if(ContieneCasilla(c)) return c;
return -1;
}
void MarcasCasillas::MascaraCaja(int k) {
if(k <= 2)
casillas &= (7 << k*3);
}
Ahora añadiremos algunas funciones a la clase Tablero:
class Tablero {
private:
...
bool BuscaSwordFishAlasFilas(int v);
bool BuscaSwordFishAlasColumnas(int v);
bool ProcesaSwordFishAlasFilas(MarcasCasillas &CasillasFilas,
MarcasCasillas &CasillasColumnas,
MarcasCasillas &CasillasAlas,
int f3, int v);
bool ProcesaSwordFishAlasColumnas(MarcasCasillas &CasillasFilas,
MarcasCasillas &CasillasColumnas,
MarcasCasillas &CasillasAlas,
int c3, int v);
public:
...
bool SwordFishAlas();
...
};
Para buscar el patrón por filas para un determinado valor:
bool Tablero::BuscaSwordFishAlasFilas(int v) {
bool retval=false;
MarcasCasillas CasillasFilas;
MarcasCasillas CasillasColumnas;
MarcasCasillas CasillasAlas;
int caj;
for(int f1=0; f1<8; f1++) {
// Buscamos en las primeras 8 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 novena otra que tenga 2, 3 candidatos v.
for(int f2= f1+1; f2<9; f2++) {
if(!fila[f2].Presente(v) && fila[f2].CuentaCandidato(v) <= 3) {
// Si entre las dos filas, el candidato aparece en 2, 3 columnas, buscamos otra fila
// que complete un patrón pez espada con alas:
CasillasColumnas = fila[f1].Marcas(v)+fila[f2].Marcas(v);
if(CasillasColumnas.CuentaCasillas() == 3) {
// Ahora buscamos en todas las filas menos f1 y f2 otra que tenga al menos 3 candidatos v
for(int f3=0; f3<9; f3++) {
if(f3 != f1 && f3 != f2 && !fila[f3].Presente(v) &&
fila[f3].CuentaCandidato(v) >= 3 &&
(fila[f3].Marcas(v) & CasillasColumnas).CuentaCasillas() >= 2) {
CasillasAlas = fila[f3].Marcas(v) & ~CasillasColumnas;
caj = CasillasAlas.Cajas();
if(((caj & CasillasColumnas.Cajas()) == caj) &&
(caj == 1 || caj == 2 || caj == 4)) {
// CasillasColumnas tiene las columnas de casillas con el candidato
CasillasFilas.Borra();
CasillasFilas.AsignaCasilla(f1);
CasillasFilas.AsignaCasilla(f2);
CasillasFilas.AsignaCasilla(f3);
if(ProcesaSwordFishAlasFilas(CasillasFilas, CasillasColumnas, CasillasAlas, f3, v)) return true;
}
}
}
}
}
}
}
}
return retval;
}
Este código tal vez necesite algunas explicaciones.
La primera parte es bastante simple, buscamos dos filas que entre las dos tengan el candidato en tres columnas.
Para la tercera, f3 buscamos una fila que no sea f1 ni f2, que no tenga el valor asignado en ninguna columna, que el candidato aparezca en al menos tres columnas fila[f3].CuentaCandidato(v) >= 3 y que al menos dos de las casillas con el candidato coincidan con las de las otras dos columnas (fila[f3].Marcas(v) & CasillasColumnas).CuentaCasillas() >= 2.
El candidato debe aparecer en al menos tres columnas porque dos deben coincidir con el patrón y debe haber una o dos aletas.
Para verificar que la fila tiene dos candidatos coincidentes con el patrón hacemos una operación AND entre sus columnas con el candidato y las de patrón correspondientes a f1 y f2, y contaremos los bits activos.
Pero aún no hemos terminado. Ahora calcularemos qué casillas pueden ser alas CasillasAlas = fila[f3].Marcas(v) & ~CasillasColumnas;. Esto eliminará de las marcas de casillas de f3 aquellas que pertenecen al patrón pez espada, dejando solo las que pueden ser alas.
Para verificar si realmente son alas o no calculamos en qué cajas están esas casillas, caj = CasillasAlas.Cajas();.
Para que esas casillas sean un ala deben cumplir algunas condiciones:
- Que la caja en la que estén sea una de las cajas en las que están las casillas de patrón,
(caj & CasillasColumnas.Cajas()) == caj). - Que estén en una única caja,
(caj == 1 || caj == 2 || caj == 4).
Ahora tenemos un patrón correcto, solo nos queda saber si podemos eliminar algún candidato de alguna casilla.
Para ello llamamos a la función ProcesaSwordFishAlasFilas.
bool Tablero::ProcesaSwordFishAlasFilas(MarcasCasillas &CasillasFilas,
MarcasCasillas &CasillasColumnas,
MarcasCasillas &CasillasAlas,
int f3, int v) {
bool retval = false;
int ca, c2;
MarcasCasillas ck;
int caj;
caj = CasillasAlas.Cajas();
ca = CasillasAlas.Casilla();
ck = CasillasColumnas;
ck.MascaraCaja(caj >> 1);
c2 = ck.Casilla();
// Eliminar candidatos en columna de candidato que comparte caja con [f3][c]
// menos en filas f1, f2 y f3
for(int f=0; f<9; f++) {
if(!CasillasFilas.ContieneCasilla(f) && casilla[f][ca].Caja() == casilla[f3][c2].Caja()) {
retval |= casilla[f][c2].Lapiz().EliminaMarca(v);
}
}
return retval;
}
De nuevo, caj es el valor de la caja con las alas.
ca es la columna de una de las casillas con las alas.
ck es el resultado de aplicar la máscara de la caja donde están las alas, es decir, la casilla del patrón que tiene alas.
c2 es la columna de esa casilla, que es en la columna donde se podrán eliminar candidatos, si existen.
Para patrones por columnas los procedimientos son análogos.
| Nombre | Fichero | Fecha | Tamaño | Contador | Descarga |
|---|---|---|---|---|---|
| Sudoku19 | sudoku19.zip | 2022-06-22 | 36124 bytes | 451 |