Si colocas las fichas al azar, Shisen-Sho (dos giros como máximo) puede quedar en una disposición en la que no se pueden quitar todas hagas lo que hagas. En la app Shisen-Sho, todas las disposiciones se crean para que siempre se puedan quitar todas las fichas. En este artículo te explicamos con sencillez cómo se hace.
La idea: colocar en el orden inverso al de quitar
Para crear una disposición que se pueda completar, basta con decidir primero «cómo se quita» y recorrerlo al revés.
- Se prepara un tablero vacío.
- Se coloca primero la última pareja que se quitará.
- Después se coloca la penúltima pareja que se quitará.
- Se sigue así hasta la primera pareja que se quitará.
Cuando colocas una pareja, las fichas ya colocadas son fichas que todavía estarán en el tablero en el momento de quitar esa pareja. Las casillas que aún no se han usado son casillas que, en ese momento, ya estarán libres porque sus fichas ya se habrán quitado. Así que las fichas colocadas cuentan como pared y las casillas todavía vacías, como espacio libre, y solo se coloca la pareja en dos casillas que se puedan unir con una línea de dos giros como máximo.
Cuando ya has colocado todas, recorriendo el orden de colocación al revés, todas las parejas se unen con una línea. Ese orden es, tal cual, la solución de la disposición.
Ejemplo: un tablero de 4×4
Con este método creamos un tablero pequeño de 16 fichas (4 tipos × 4).
La última pareja que se colocó son las dos fichas de abajo de la segunda columna desde la izquierda (2 de Caracteres). Por eso esta pareja se puede quitar la primera (línea dorada). Si recorres al revés el orden de colocación y quitas 4 parejas, el tablero queda así. La quinta pareja que se quita es la de 6 de Caracteres.
Si sigues quitando las 8 parejas en orden, se quitan todas las fichas.
Cómo evitar quedarse sin sitio donde colocar
Este método tiene una trampa. Si en algún momento ninguna pareja de las casillas que quedan se puede unir con una línea, ya no se puede seguir colocando.
Para que no pase, la app usa esta propiedad:
- Dos casillas contiguas siempre se unen (la línea tiene longitud 1, así que nada la bloquea).
- Por eso, se mantiene siempre un estado en el que las casillas todavía vacías se pueden repartir exactamente en parejas de casillas contiguas.
Si se pueden repartir así, en el peor de los casos siempre se puede colocar la pareja en dos casillas contiguas y seguir adelante. Si se puede repartir o no lo comprueba enseguida el ordenador, como el problema de emparejar casillas blancas y negras contiguas al pintar el tablero como un tablero de ajedrez (en matemáticas se llama emparejamiento perfecto de un grafo bipartito). Por esta propiedad, las dos casillas de una pareja siempre son de distinto color en el tablero de ajedrez.
Que no todo sean casillas contiguas
Si todas las parejas fueran contiguas, la respuesta se vería a simple vista. Por eso, para colocar se buscan primero dos casillas lo más alejadas posible.
Al crear 2000 tableros de 48 fichas con el mismo método que la app, las parejas de dos casillas contiguas dentro de la solución fueron aproximadamente un 28 %. El otro 70 % son parejas alejadas que se quitan con líneas en L o en U.
Barajar usa el mismo método
El barajado cuando ya no quedan parejas usa el mismo método. Las fichas que quedan se vuelven a colocar, en el orden inverso al de quitarlas, en las casillas en las que ahora hay fichas. Por eso, después de barajar, también se pueden quitar siempre todas las fichas.
Eso sí, este método solo garantiza que «existe al menos una solución». Si te equivocas en el orden en que quitas las fichas, puedes quedarte bloqueado. Qué hacer entonces se resume en qué hacer cuando te quedas sin parejas: barajar.
