Hidato - Haskell

Carlos Bermudez Porto y Leynier Gutiérrez Gonzáles | 25 de octubre de 2020

Significado de Haskell

Haskell es un lenguaje de programación estandarizado multi-propósito, funcionalmente puro, con evaluación no estricta y memorizada, y fuerte tipificación estática. Su nombre se debe al lógico estadounidense Haskell Curry, debido a su aportación al cálculo lambda, el cual tiene gran influencia en el lenguaje. En Haskell, “una función es un ciudadano de primera clase” del lenguaje de programación. Como lenguaje de programación funcional, el constructor de controles primario es la función. El lenguaje tiene sus orígenes en las observaciones de Haskell Curry y sus descendientes intelectuales. [1]

Significado de Hidato

Hidato es un juego de lógica creado por el Dr. Gyora Benedek, un matemático israelí. El objetivo de Hidato es rellenar el tablero con números consecutivos que se conectan horizontal, vertical o diagonalmente. Los puzzles Numbrix , creados por Marilyn Vos Savant, son similares a Hidato excepto por los movimientos diagonales, que no están permitidos. Los nombres Numbrix e Hidato son marcas registradas. [2]

Explicación del Hidato

En el Hidato , el objetivo es rellenar el tablero con números consecutivos que se conectan horizontal, vertical o diagonalmente. En cada juego de Hidato, los números mayor y menor están marcados en el tablero. Todos los números consecutivos están adyacentes de forma vertical, horizontal o diagonal. Hay algunos números más en el tablero para ayudar a dirigir al jugador sobre cómo empezar a resolverlo y para asegurarse de que ese Hidato tiene solución única. Se suele jugar en una cuadrícula como Sudoku pero también existen tableros hexagonales u otros más irregulares con figuras como corazones, calaveras, etc. Cada puzzle de Hidato creado correctamente debe tener solución única.

Un puzzle Hidato y su solución

Modelación del Hidato

Para representar el tablero del juego Hidato se utilizó una tupla de 3 elementos (nRows, nCols, setCells). En lo adelante, cuando se haga referencia a un tablero de Hidato se hará referencia a la tupla (nRows, nCols, setCells).

nRows: x ∈ Ν. Representa la cantidad de filas del tablero

nCols: x ∈ Ν. Representa la cantidad de columnas del tablero

setCells: El conjunto S de todos los vectores 〈x, y, v〉 donde x, y ∈ Ν, 1 ≤ x ≤ nRows, 1 ≤ y ≤ nCols, v ∈ Ζ, -1 ≤ v, ∀ 〈x1, y1〉 ∈ ([1, nRows]×[1, nCols]) ∩ Z x Z el conjunto S contiene un único vector 〈x2, y2, v2〉 tal que x1 = x2 y y1 = y2, no existen 2 vectores 〈x1, y1, v1〉 ∈ S y 〈x2, y2, v2〉 ∈ S tal que x1 ≠ x2, y1 ≠ y2, v1 > 0, v2 > 0 y v1 = v2; y v ≤ nRows * nCols - |{〈x1, y1, v1〉 | 〈x1, y1, v1〉 ∈ S ∧ v1 = -1}|. Conjunto de vectores donde cada uno representa una celda en el tablero. La primera y segunda componente del vector representan la fila y columna respectivamente en la que se encuentra la celda dentro del tablero y la tercera componente representa el valor de la celda en el tablero. Estos valores son todos mayores iguales a -1 y representan lo siguiente:

• -1 representa un obstáculo, esa celda no se utiliza para el juego, de esta manera se pueden representar juegos de Hidato de la forma que se quiera utilizando obstáculos (Externamente para el usuario se representa con _'x')_
• 0 Representa una celda en blanco, la cual debe ser rellenada para solucionar el Hidato (Externamente para el usuario se representa con _'.')_
• Mayor que 0 representa una celda con un número rellenado ya sea porque estaba así en un inicio o porque fue rellenado durante el proceso de resolución del Hidato.

Ejemplo visual de un tablero de Hidato

Plantilla de Hidato válida de 5x5 e Hidato resuelto de 5x5

Se define como una plantilla de Hidato a un tablero donde setCells no contenga vectores con valores mayores que 1 en su tercera componente.

Se define como una plantilla de Hidato válida a una plantilla de Hidato si partiendo desde ella y realizando transformaciones válidas al conjunto setCells es posible llegar a un Hidato resuelto.

Las transformaciones válidas son aquellas que a partir de un tablero de Hidato se escoge un vector del conjunto setCells tal que su tercera componente sea igual a 0 y se modifica esa componente colocando un valor diferente de 0 siempre y cuando el resultado sea un tablero de Hidato.

Se define que 2 vectores 〈x1, y1, v1〉 y 〈x2, y2, v2〉 del conjunto setCells de un tablero de Hidato son adyacentes si existe 〈x3, y3〉 ∈ ([-1, 1]×[-1, 1]) ∩ Z x Z - {〈0, 0〉} tal que 〈x1, y1〉=〈x2, y2〉+〈x3, y3〉.

Se define como un Hidato resuelto a un tablero de Hidato que no contenga vectores en setCells con la tercera componente igual a 0 y que ∀ 〈x1, y1, v1〉 ∈ setCells con v1 > 1 existe un vector 〈x2, y2, v2〉 ∈ setCells que es adyacente con 〈x1, y1, v1〉 donde v1 = v2 + 1.

Algoritmo de Solución

La idea general del algoritmo de solución es utilizar un recorrido por el grafo de posibles transformaciones válidas utilizando el algoritmo de búsqueda en profundidad o mejor conocido como DFS.

La función solve recibe un tablero, un paso y un límite (este límite es igual al mayor número posible dentro del tablero o sea el mayor v) y realiza lo siguiente:

• Si el paso es igual al límite más uno es que el tablero está rellenado completo y por tanto se resolvió completamente, por lo que devuelve una lista conteniendo al tablero.
• Si no, devuelve una lista resultante de concatenar las listas de tableros resultantes del proceso de utilizar cada tablero generado por la invocación de la función stepMatrix pasándole los argumentos del tablero actual y el paso actual como argumento de un llamado recursivo a la función solve con el paso siguiente y el mismo límite.

La función stepMatrix recibe un tablero y un paso y realiza lo siguiente:

• Si hay alguna celda con el valor igual al paso actual dentro del tablero actual y bien ese valor es 1 o la celda es adyacente con la celda que tiene el valor del paso anterior dentro del tablero actual devuelve una lista conteniendo al tablero actual.
• Si hay alguna celda con el valor igual al paso actual dentro del tablero actual y el valor NO es 1 y la celda NO es adyacente con la celda que tiene el valor del paso anterior dentro del tablero actual devuelve una lista vacía.
• Si no, devuelve una lista que contiene a los tableros resultantes del proceso de recorrer cada celda adyacente (que su valor sea diferente de 0) de la celda que tiene el valor del paso anterior dentro del tablero generando por cada una de estas celdas adyacentes un nuevo tablero con el valor de esa celda igual al paso actual.

Ejemplo de pseudo implementación en Python del algoritmo de solución.

Algoritmo de Generación

La idea general del algoritmo de generación es generar una plantilla de Hidato válida aleatoriamente a partir de una cantidad de filas, de columnas y de un porcentaje de obstáculos, resolver esta plantilla para obtener un Hidato resuelto y luego realizar un proceso de eliminación de una cantidad de celdas (según la dificultad seleccionada) cuyos valores sean mayores que 1 y menores que el máximo v en un orden aleatorio comprobando en cada paso que al eliminar no sea posible generar más de un Hidato resuelto (siendo el único posible, el Hidato resuelto desde donde se comenzó el proceso de eliminación).

• La función generate recibe el número de filas, de columnas, el porcentaje de obstáculos y la dificultad y realiza lo siguiente: Utilizando la función generateHidatoSolved genera un Hidato resuelto que utiliza como argumento al llamar a la función removeCells pasándole además como argumento a esta una permutación aleatoria de las casillas del Hidato resuelto (generado por la función generateHidatoSolved ) que se pueden eliminar (aquellas que el valor sea mayor que 1 y menor que el máximo valor) y el número de casillas que se puede eliminar según la dificultad devolviendo finalmente la plantilla de Hidato.
• La función generateHidatoSolved recibe el número de filas, de columnas y el porcentaje de obstáculos y realiza lo siguiente: Comprueba si la pseudo plantilla de Hidato generada aleatoriamente por la función generateRandomPseudoTemplate es una plantilla de Hidato válida (que es posible a partir de ella llegar a un Hidato resuelto), si lo es, devuelve esa plantilla, si no, lo intenta nuevamente.
• La función generateRandomPseudoTemplate recibe el número de filas, de columnas y el porcentaje de obstáculos y realiza lo siguiente: Devuelve una pseudo plantilla (plantilla que no se ha comprobado que sea una plantilla de Hidato válida) con la cantidad de filas y columnas recibida como argumentos y con una cantidad de casillas (según el porcentaje de obstáculos) marcadas como obstáculos aleatoriamente.
• La función removeCells recibe una plantilla, una permutación aleatoria de las casillas que se pueden eliminar y el número de casillas que se deben eliminar según la dificultad y realiza lo siguiente: Si la permutación aleatoria de las casillas que se pueden eliminar es vacía o el número de casillas que se debe eliminar según la dificultad es negativo se devuelve la plantilla si no se genera una nueva plantilla modificando el valor (poniéndolo en 0) de la casilla correspondiente (según la permutación aleatoria de las casillas) a partir de la plantilla recibida como argumento, con esta nueva plantilla comprueba si se generan más de un Hidato resuelto, en caso de ser así devuelve el resultado de aplicar un llamado recursivo a removeCells pasándole la plantilla recibida como argumento, la cola de la permutación aleatoria de las casillas que se pueden eliminar y el mismo número de casillas que se deben eliminar (pues en ese paso no es posible eliminar la casilla porque genera más de un Hidato resuelto), en caso de generar solamente un Hidato resuelto devuelve el resultado de aplicar un llamado recursivo a removeCells pasándole la nueva plantilla, la cola de la permutación aleatoria de las casillas que se pueden eliminar y un número menos de casillas que se deben eliminar (pues en ese paso es posible eliminar la casilla porque genera solamente un Hidato resuelto).

Ejemplo de pseudo implementación en Python del algoritmo de generación.

Implementación en Haskell

Para la implementación en Haskell se utilizaron cuatro estructuras fundamentales, dos implementadas por defecto en Haskell y dos implementadas por los autores.

Solucionador

La “cara pública” del solucionador es la función solveAll la cual mediante la característica llamada currying de Haskell que permite una aplicación parcial de una función, en este caso la función solveAll realiza una aplicación parcial de la función solveRecursiveDFS convirtiéndose la función solveAll en una función que recibe dos argumentos, una Matrix y una lista de enteros.

En el llamado a la función solveRecursiveDFS se utilizan dos funciones countObstacles y buildMap.

La función countObstacles calcula la cantidad de celdas con valor igual a -1 auxiliándose de la función countInMatrix que permite contar la cantidad de celdas con valor igual a un número dado. Esta función se utiliza para contar la cantidad de casillas que no son obstáculos.

La función buildMap genera un mapa o diccionario a partir de las celdas de una matriz, utilizando como llaves los valores de las celdas y como valores las celdas. Este diccionario es utilizado posteriormente para saber si una casilla con un valor determinado se encuentra en el tablero y de ser así acceder a ella eficientemente.

La función solveRecursiveDFS recibe 6 argumentos.

1. actualMatrix : En la matriz actual, representando una plantilla de Hidato válida con posibilidades de ser un Hidato resuelto.
2. step : Es el paso del algoritmo y representa el número que se está intentando rellenar, pero puede existir ya en el tablero.
3. prevCell : Es la celda que tiene el valor (step -1), ya sea porque estaba en el tablero o porque se rellenó, este variable tiene el objetivo de disminuir la complejidad temporal del algoritmo evitando tener que realizar el procesamiento para obtener en cada paso.
4. obs : Es el número de casillas que NO son obstáculos.
5. map : Es un diccionario de entero contra celdas, en la explicación sobre la función buildMap se puede leer más sobre su objetivo.
6. seeds : Una lista de enteros infinita, su objetivo es ser utilizada como semilla para generar número pseudo aleatorios utilizados en el proceso de recorrer las casillas adyacentes haciendo en cada paso del algoritmo en un orden no necesariamente igual.

La función lo que hace es comprobar si se está en el último paso (que ya se rellenaron todas las casillas posibles y se llegó a un Hidato resuelto) o por lo contrario realizar los llamados recursivos buscando las posibles soluciones. (La explicación del algoritmo se encuentra en la sección Algoritmo de Solución).

La función stepMatrix calcula las posibles matrices o plantillas de Hidato válidas partiendo de una plantilla recibida como argumento y el número que tiene que rellenar en la matriz. Esto lo hace utilizando prevCell y map para mejorar la complejidad temporal y realizar menos cálculos además de la utilización de otras funciones como getAdjacents e isAdjacent.

Generador

La “cara pública” del generador es la función generateGame , esta recibe la cantidad de filas y columnas, el porcentaje de obstáculos, la dificultad y un límite de tiempo que tendrá en generador para generar la plantilla de Hidato válida (más adelante se explicará con más detalles este límite de tiempo y porque es necesario). La función devuelve una tupla, en la primera componente significa si se puedo generar la plantilla y en la segunda componente la plantilla generada (notar que si la primera componente es igual a False, el valor de la segunda componente no tiene significado).

La función generateGame se auxilia de la función generateRandomGame para obtener un Hidato resuelto. Para realizar esta operación se utiliza un tiempo límite, debido a la naturaleza aleatoria de generateRandomGame (no se asegura que termine, porque puede dependiendo de los parámetros demorar mucho o incluso con una bajísima probabilidad realizar un ciclo infinito).

En caso de sobrepasar el límite de tiempo es devuelto una tupla con la primera componente en False. En caso de no sobrepasar el tiempo, se realiza un proceso de "eliminación" (poner con valor cero varias celdas) comprobando en cada paso que al hacerlo se mantenga la unicidad de la solución de esa plantilla (que los posibles Hidato resueltos es solamente uno).

El orden de las casillas escogidas para eliminar se realiza con una permutación aleatoria del conjunto de casillas disponibles para eliminar (las que tengan como valor mayor que 1 y menor que el máximo). Luego utilizando la función removeCells que lo que realiza es recorrer la permutación aleatoria y comprobar si eliminando la casilla i-ésima se mantiene la unicidad, en caso de ser así se elimina y se pasa la siguiente casilla dentro de la permutación aleatoria.

Luego de terminado el proceso de eliminación, ya sea porque se acabaron las casillas disponibles en la permutación aleatoria o porque se llegó al número de casillas que se debían eliminar, se retorna la plantilla de Hidato válida resultante.

Manual para usuarios

Es necesario instalar Stack , este se puede instalar en la mayoría de los sistemas operativos similares a Unix , incluido macOS , y en Windows.

Para la mayoría de los sistemas operativos Unix, la forma más sencilla de instalar es ejecutar:

curl -sSL https://get.haskellstack.org/ | sh

o:

wget -qO- https://get.haskellstack.org/ | sh

En Windows , puede descargar e instalar el instalador de Windows de 64 bits.

Para otros sistemas operativos y descargas directas, consulte la guía de instalación y actualización. [3]

Lo siguiente es clonar el repositorio de GitHub utilizando Git o descargar el .zip y descomprimirlo.

Luego, dentro de la carpeta del proyecto ejecutar stack setup, después stack build y por último stack exec hidato-exe para ejecutar el proyecto.

https://github.com/codestrange/declarative-programing-hidato-project

Los comandos disponibles del Hidato son 4.

• help: Para ver la ayuda, también es posible ver la ayuda de un comando especifico utilizando help comando
• generate: Para generar una plantilla de Hidato, los argumentos son cantidad de filas, cantidad de columnas, la razón de la cantidad de obstáculos respecto al tamaño del tablero, la dificultad, el nombre del fichero donde se guardará la plantilla de Hidato y, por último, opcionalmente un tiempo límite expresado en millonésimas de segundos, por defecto es un minuto. Por ejemplo: generate 5 5 0.2 Normal hidato.txt. Las dificultades son Easy, Normal y Hard.
• solve: Para resolver un Hidato, recibe como argumento la dirección del fichero donde se encuentra la plantilla del Hidato a resolver. Por ejemplo: solve hidato.txt
• exit: Para salir del programa

Referencias

1. Página sobre Haskell en la Wikipedia
2. Página sobre Hidato en la Wikipedia
3. Documentación de Haskell Stack

Publicado originalmente en https://leynier.github.io.