Implementación y Generación de Hidato con Haskell

Repositorio de GitHub

Significado de Haskell

Haskell es un lenguaje de programación estandarizado, multipropósito, funcionalmente puro, con evaluación no estricta y tipificación fuerte estática. Su nombre se debe al lógico estadounidense Haskell Curry, por su contribución al cálculo lambda, el cual influye en el lenguaje. En Haskell, "una función es un ciudadano de primera clase". Como lenguaje de programación funcional, el constructor de control primario es la función. El lenguaje se originó a partir de 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 llenar 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 llenar 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 adicionales en el tablero para ayudar a dirigir al jugador y asegurar que el Hidato tiene una 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 correctamente creado debe tener una 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 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. Para todo 〈x1, y1〉 en ([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 dos vectores 〈x1, y1, v1〉 ∈ S y 〈x2, y2, v2〉 ∈ S tales que x1 ≠ x2, y1 ≠ y2, v1 > 0, v2 > 0 y v1 = v2. El valor v debe ser menor o igual a nRows * nCols - |{〈x1, y1, v1〉 | 〈x1, y1, v1〉 ∈ S ∧ v1 = -1}|. Cada vector representa una celda en el tablero, donde la primera y segunda componente representan la fila y columna respectivamente, y la tercera componente representa el valor de la celda en el tablero. Estos valores son todos mayores o iguales a -1 y representan lo siguiente:

• -1 representa un obstáculo; esa celda no se utiliza para el juego, permitiendo representar juegos de Hidato de cualquier forma utilizando obstáculos (externamente se representa con 'x').

• 0 representa una celda en blanco que debe ser rellenada para solucionar el Hidato (externamente se representa con '.').

• Un número mayor que 0 representa una celda con un número ya rellenado, ya sea porque estaba así al 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 cuya 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 dos 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 para todo 〈x1, y1, v1〉 ∈ setCells con v1 > 1, exista un vector 〈x2, y2, v2〉 ∈ setCells adyacente a 〈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 mediante el algoritmo de búsqueda en profundidad (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) y realiza lo siguiente:

• Si el paso es igual al límite más uno, el tablero está completamente rellenado y, por tanto, resuelto, por lo que devuelve una lista conteniendo al tablero.

• Si no, devuelve una lista resultante de concatenar las listas de tableros generados 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 y ese valor es 1, o la celda es adyacente a la celda que tiene el valor del paso anterior, devuelve una lista conteniendo el tablero actual.

• Si hay alguna celda con el valor igual al paso actual y ese valor no es 1, y la celda no es adyacente a la celda que tiene el valor del paso anterior, devuelve una lista vacía.

• Si no, devuelve una lista que contiene los tableros resultantes de recorrer cada celda adyacente (cuyo valor sea diferente de 0) de la celda que tiene el valor del paso anterior, 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:

def solve(table, step, limit):
    if step == limit + 1:
        return [table]
    else:
        return [
            item
            for new_table in step_matrix(table, step)
            for item in solve(new_table, step + 1, limit)
        ]

def step_matrix(table, step):
    if cell_in_table(step, table):
        if get_cell_value(get_cell(table, step)) == 1 or is_adyacents(get_cell(table, step), get_cell(table, step - 1)):
            return [table]
        else:
            return []
    else:
        return [
            update_cell_in_table(table, update_value_in_cell(step, cell))
            for cell in get_adyacents(table, get_cell(table, step - 1))
            if get_cell_value(cell) == 0
        ]

Algoritmo de Generación

La idea general del algoritmo de generación es crear una plantilla de Hidato válida aleatoriamente a partir de una cantidad de filas, columnas y un porcentaje de obstáculos. Luego, resolver esta plantilla para obtener un Hidato resuelto y realizar un proceso de eliminación de celdas (según la dificultad seleccionada) cuyos valores sean mayores que 1 y menores que el máximo, en orden aleatorio, asegurando en cada paso que la eliminación no genere 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, columnas, el porcentaje de obstáculos y la dificultad, y realiza lo siguiente: Utilizando la función generateHidatoSolved, genera un Hidato resuelto que usa como argumento al llamar a la función removeCells, pasándole además una permutación aleatoria de las casillas del Hidato resuelto (generadas por generateHidatoSolved) que se pueden eliminar (aquellas cuyo valor sea mayor que 1 y menor que el máximo valor) y el número de casillas que se pueden eliminar según la dificultad, devolviendo finalmente la plantilla de Hidato.

• La función generateHidatoSolved recibe el número de filas, 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, 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 recibidas 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 está vacía o el número de casillas que se deben eliminar según la dificultad es negativo, devuelve la plantilla; si no, 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 afirmativo, 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 menor 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:

def generate(n_rows, n_cols, ratio, diff):
    hidato_solved = generate_hidato_solved(n_rows, n_cols, ratio)
    max_elem = n_rows * n_cols - count_obstacles(hidato_solved)
    cells_for_remove = random_shuffle(filter(lambda cell: get_cell_value(cell) > 1 and get_cell_value(cell) < max_elem, get_cells(hidato_solved)))
    cant_empty = floor(len(cells_for_remove) * diff)
    template = remove_cells(hidato_solved, n_rows, n_cols, cells_for_remove, cant_empty)
    return template

def generate_hidato_solved(n_rows, n_cols, ratio):
    pseudo_template = generate_random_pseudo_template(n_rows, n_cols, ratio)
    limit = n_rows * n_cols - count_obstacles(pseudo_template)
    solves = solve(pseudo_template, 0, limit)
    if solves:
        return solves[0]
    else:
        return generate_hidato_solved(n_rows, n_cols, ratio)

def generate_random_pseudo_template(n_rows, n_cols, ratio):
    cant_obs = floor(n_rows * n_cols * ratio)
    blank_template = create_blank_template(n_rows, n_cols)
    cells_for_remove = take(cant_obs, random_shuffle(get_cells(blank_template)))
    dark_template = reduce(lambda acc, cell: update_cell_in_table(acc, update_value_in_cell(-1, cell)), cells_for_remove, blank_template)
    pseudo_template = update_cell_in_table(dark_template, update_value_in_cell(1, select_random_cell(dark_template)))
    return pseudo_template

def remove_cells(template, n_rows, n_cols, cells_for_remove, cant_empty):
    if not cells_for_remove or cant_empty < 0:
        return template
    else:
        head_cell = cells_for_remove[0]
        tail_cells = cells_for_remove[1:]
        empty = update_value_in_cell(0, head_cell)
        new_template = update_cell_in_table(template, empty)
        limit = n_rows * n_cols - count_obstacles(new_template)
        solves = solve(new_template, 0, limit)
        if len(take(2, solves)) < 2:
            return remove_cells(new_template, n_rows, n_cols, tail_cells, cant_empty - 1)
        else:
            return remove_cells(template, n_rows, n_cols, tail_cells, cant_empty)

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.

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Set (Set, lookupMin, lookupMax)
import qualified Data.Set as Set

data Cell = Cell { row :: Int, column :: Int, value :: Int }
data Matrix = Matrix { rows :: Int, columns :: Int, matrix :: Set Cell }

Solucionador

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

solveAll :: Matrix -> [Int] -> [Matrix]
solveAll m = solveRecursiveDFS m 1 (Cell 0 0 0) (rows m * columns m  - countObstacles m) (buildMap m)

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.

countInMatrix :: Int -> Matrix -> Int
countInMatrix val (Matrix _ _ cells) =
                    foldl (\acc cell -> if value cell == val then acc + 1 else acc) 0 cells

countObstacles :: Matrix -> Int
countObstacles = countInMatrix (-1)

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 se utiliza posteriormente para saber si una casilla con un valor determinado se encuentra en el tablero y acceder a ella eficientemente.

buildMap :: Matrix -> Map Int Cell
buildMap ma@(Matrix r c m) = Set.foldl (\acc cell -> Map.insert (value cell) cell acc) Map.empty m

La función solveRecursiveDFS recibe 6 argumentos:

1. actualMatrix: La matriz actual, representando una plantilla de Hidato válida con posibilidades de ser un Hidato resuelto.

2. step: El paso del algoritmo, que representa el número que se está intentando rellenar, aunque puede existir ya en el tablero.

3. prevCell: La celda que tiene el valor (step -1), ya sea porque estaba en el tablero o porque se rellenó. Esta variable tiene el objetivo de disminuir la complejidad temporal del algoritmo, evitando realizar el procesamiento para obtenerla en cada paso.

4. obs: El número de casillas que no son obstáculos.

5. map: Un diccionario de enteros contra celdas, utilizado para mejorar la eficiencia.

6. seeds: Una lista de enteros infinita, utilizada como semilla para generar números pseudoaleatorios en el proceso de recorrer las casillas adyacentes en un orden no necesariamente igual.

La función comprueba si se está en el último paso (si ya se rellenaron todas las casillas posibles y se llegó a un Hidato resuelto). Si no, realiza llamados recursivos buscando las posibles soluciones.

solveRecursiveDFS :: Matrix -> Int -> Cell -> Int -> Map Int Cell -> [Int] -> [Matrix]
solveRecursiveDFS actualMatrix step prevCell obs map seeds
      | step == obs + 1 = [actualMatrix]
      | otherwise = let toAdd = stepMatrix step actualMatrix prevCell map seeds
                    in concat [ solveRecursiveDFS matrix (step + 1) prevCell obs map (tail seeds) | (matrix, prevCell) <- toAdd ]

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 se debe 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.

stepMatrix :: Int -> Matrix -> Cell -> Map Int Cell -> [Int] -> [(Matrix, Cell)]
stepMatrix step m@(Matrix rs cs ma) prevCell map seeds = if Map.notMember step map
      then [
            newMatrix | cell <- getAdjacents prevCell rs cs step seeds,
            let actCell = Set.elemAt (Set.findIndex cell ma) ma,
            value actCell == 0,
            let newMatrix = (Matrix rs cs (Set.insert cell ma), cell)
      ]
      else  let actCell = map Map.! step
            in [newMatrix | isAdjacent actCell prevCell || value actCell == 1, let newMatrix = (m, actCell)]

getAdjacents :: Cell -> Int -> Int -> Int -> [Int] -> [Cell]
getAdjacents (Cell r c v) rs cs s seeds = [
        Cell nr nc s |
        dr <- genShuffle seeds [-1, 0, 1],
        dc <- genShuffle seeds [-1, 0, 1],
        let (nr, nc) = (r + dr, c + dc),
        nr > 0,
        nr <= rs,
        nc > 0,
        nc <= cs,
        not $ dr == 0 && dc == 0
    ]

isAdjacent :: Cell -> Cell -> Bool
isAdjacent (Cell f1 c1 v1) (Cell f2 c2 v2)
            | Cell f1 c1 v1 == Cell f2 c2 v2           = False
            | abs (f1 - f2) >= 2 || abs (c1 - c2) >= 2 = False
            | v1 == (-1) || v2 == (-1)                 = False
            | otherwise                                = True

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 para generar la plantilla de Hidato válida. La función devuelve una tupla, donde la primera componente indica si se pudo generar la plantilla y la segunda componente contiene la plantilla generada (si la primera componente es False, el valor de la segunda componente no tiene significado).

generateGame :: Int -> Int -> Float -> Difficulty -> Int -> IO (Bool, Matrix)
generateGame rn cn ratio dif to = do
      maybeMatrix <- timeout to $ generateRandomGame rn cn ratio
      if isNothing maybeMatrix then do
            return (False, blankMatrix 1 1)
      else do
            let solution = maybe (blankMatrix rn cn) id maybeMatrix
            let maxElem = rn * cn - countObstacles solution
            let setForRemove = Set.filter (\x -> let v = value x in v > 1 && v < maxElem) (matrix solution) :: Set Cell
            randomCells <- genRCellFromSet setForRemove
            let total = Set.size setForRemove
            let cant_empty = floor $ fromIntegral total * emptyRatio dif
            seed <- randomIO :: IO Int
            let gen = mkStdGen seed
            let seeds = randoms gen :: [Int]
            let game = removeCells solution randomCells cant_empty seeds
            return (True, game)

La función generateGame se auxilia de generateRandomGame para obtener un Hidato resuelto. Esta operación utiliza un tiempo límite debido a la naturaleza aleatoria de generateRandomGame (no se asegura que termine, ya que puede demorar mucho o incluso realizar un ciclo infinito con una baja probabilidad).

En caso de sobrepasar el límite de tiempo, se devuelve una tupla con la primera componente en False. Si no se sobrepasa el tiempo, se realiza un proceso de eliminación (poner con valor cero varias celdas) asegurando en cada paso que la eliminación mantenga la unicidad de la solución de esa plantilla.

generateRandomGame :: Int -> Int -> Float -> IO Matrix
generateRandomGame rn cn ratio = do
      maybeTemplate <- timeout 1000000 $ generateRandom rn cn ratio
      if isNothing maybeTemplate then
            generateRandomGame rn cn ratio
      else do
            let template = maybe (blankMatrix rn cn) id maybeTemplate
            seed <- randomIO :: IO Int
            let gen = mkStdGen seed
            let seeds = randoms gen :: [Int]
            let solutions = solveAll template seeds
            if null solutions then
                  generateRandomGame rn cn ratio
            else
              return $ head solutions

El orden de las casillas a eliminar se determina mediante una permutación aleatoria del conjunto de casillas disponibles para eliminar (las que tienen un valor mayor que 1 y menor que el máximo). Luego, utilizando la función removeCells, se recorre la permutación aleatoria y se comprueba si eliminando la casilla i-ésima se mantiene la unicidad. Si es así, se elimina y se pasa a la siguiente casilla de la permutación aleatoria.

removeCells :: Matrix -> [Cell] -> Int -> [Int] -> Matrix
removeCells sol@(Matrix rn cn cs) cells n seeds =
      if    null cells || n < 0 then
            sol
      else
            let   (headCell: tailCells) = cells
                  rowCell = row headCell
                  colCell = column headCell
                  empty = Cell rowCell colCell 0
                  matrix = editMatrixCell sol empty
                  solutions = solveAll matrix seeds
                  isUnix = length (take 2 solutions) < 2
            in    if isUnix then
                        removeCells matrix tailCells (n - 1) seeds
                  else
                        removeCells sol tailCells n seeds

Después de terminar 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, que 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 instalarlo 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, ejecute stack setup, luego 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 específico 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, opcionalmente, un tiempo límite expresado en milisegundos (por defecto, 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

Agradecimientos

Este proyecto fue en coautoría con Carlos Bermudez Porto, muchas gracias por su colaboración.