Honestidad académica y copias

Un trabajo práctico es un examen, por lo que debe realizarse de manera individual. La discusión y el intercambio de información de carácter general con los compañeros se permite (e incluso se recomienda), pero NO AL NIVEL DE CÓDIGO. Igualmente el remitir código de terceros, OBTENIDO A TRAVÉS DE LA RED o cualquier otro medio, se considerará plagio.

Cualquier plagio o compartición de código que se detecte, significará automáticamente la calificación de CERO EN LA ASIGNATURA para TODOS los alumnos involucrados. Por tanto, a estos alumnos NO se les conservará, para futuras convocatorias, ninguna nota que hubiesen obtenido hasta el momento, SIN PERJUICIO DE OTRAS MEDIDAS DE CARÁCTER DISCIPLINARIO QUE SE PUDIERAN TOMAR.

Resolución deductiva del Hitori en CLIPS

Hitori es uno de los pasatiempos lógicos popularizados por la revista japonesa Nikoli. El objetivo del juego consiste en, dada una cuadrícula con cifras, determinar cuales hay que quitar para conseguir que no haya elementos repetidos ni en las filas ni en las columnas. También hay otras restricciones sobre la forma en que se pueden eliminar estos elementos y las veremos un poco más adelante.

En concreto vamos a considerar cuadrículas de tamaño 9x9 con cifras del 1 al 9 como la siguiente:

El puzle resuelto es el siguiente:

Se deben cumplir dos restricciones adicionales sobre los elementos eliminados:

1. No pueden eliminarse elementos en celdas colindantes horizontal o verticalmente. Esta restricción impide que se puedan hacer cosas como esta:
2. Todas las celdas cuyo valor se mantiene deben formar una única componente conectada horizontal o verticalmente. Esta restricción impide que se puedan hacer cosas como esta:

También es importante tener en cuenta que el puzle tiene solución única, algo que puede ayudar a obtener dicha solución.

Para evaluar el sistema se proporciona un fichero de ejemplos que contiene 50 puzles Hitori con solución única de tamaño 9x9 representados como una única línea en la que también se indica la solución. Si se transcribe esta línea separando las 9 filas tendríamos lo siguiente:

     w2 w9 w8 b7 w4 w6 b4 w7 b6 
     w7 b4 w9 w2 w8 b3 w4 w3 w5 
     w4 w7 b5 w3 b6 w5 b6 w6 b5 
     b6 w1 w3 b7 w6 w9 w7 w2 w4 
     w1 w3 b3 w7 w2 w8 w6 w5 b1 
     w9 w8 w6 b2 w3 b8 w5 b5 w2 
     w8 b4 w7 w9 b3 w3 w2 w1 w6 
     w6 w2 b4 w1 w7 w4 b4 w9 w3 
     b8 w4 w1 b3 w5 b1 w9 w8 b1 

También se proporciona un fichero base hitori.clp en el que se definen los siguientes constructores.

• Una plantilla celda para almacenar la información sobre las celdas del tablero.

  (deftemplate celda
    (slot fila)
    (slot columna)
    (slot valor)
    (slot estado
  	(allowed-values desconocido asignado eliminado)
  	(default desconocido)))
  

  1. Los campos fila y columna sirven para almacenar los números de fila y columna en las que se encuentra la celda.
  2. El campo valor sirve para almacenar el valor numérico de la celda.
  3. El campo estado sirve para almacenar el estado de la celda. Puede ser desconocido, que indica que todavía no se ha tomado ninguna decisión sobre la celda; asignado, que incida que el valor de la celda se mantiene en la solución; y eliminado, que indica que el valor de la celda es eliminado en la solución. El valor por defecto es desconocido.
• Las funciones procesa-datos-ejemplo, lee-puzle y procesa-ejemplos sirven para leer los puzles Hitori desde el fichero ejemplos.txt, almacenarlos como un conjunto de hechos correspondientes a la plantilla celda y evaluar las estrategias de resolución. La función lee-puzle actúa sobre un puzle concreto que se indica con un número de 1 a 50 y la función procesa-ejemplos actúa sobre todos los ejemplos uno tras otro.

  (deffunction procesa-datos-ejemplo (?datos)
    (loop-for-count
     (?i 1 9)
     (loop-for-count
      (?j 1 9)
      (bind ?s1 (* 2 (+ ?j (* 9 (- ?i 1)))))
      (bind ?v (sub-string ?s1 ?s1 ?datos))
      (assert (celda (fila ?i) (columna ?j) (valor ?v))))))
  
  (deffunction lee-puzle (?n)
    (open "ejemplos.txt" data "r")
    (loop-for-count (?i 1 (- ?n 1))
                    (readline data))
    (bind ?datos (readline data))
    (reset)
    (procesa-datos-ejemplo ?datos)
    (run)
    (close data))
  
  (deffunction procesa-ejemplos ()
    (open "ejemplos.txt" data "r")
    (bind ?datos (readline data))
    (bind ?i 1)
    (while (neq ?datos EOF)
     (reset)
     (procesa-datos-ejemplo ?datos)
     (printout t "ejemplos.txt :" ?i crlf)
     (run)
     (bind ?datos (readline data))
     (bind ?i (+ ?i 1)))
    (close data))
  

• Las reglas imprime-solucion e imprime-fila sirven para visualizar el estado del puzle, una vez aplicadas todas las reglas que implementan las estrategias de resolución. Estas reglas tienen prioridad -10 ((declare (salience -10))) para que sean las últimas en aplicarse.

  (defrule imprime-solucion
    (declare (salience -10))
    =>
    (printout t " Original           Solución " crlf)  
    (printout t "+---------+        +---------+" crlf)
    (assert (imprime 1)))
  
  (defrule imprime-fila
    (declare (salience -10))
    ?h <- (imprime ?i&:(<= ?i 9))
    (celda (fila ?i) (columna 1) (valor ?v1) (estado ?s1))
    (celda (fila ?i) (columna 2) (valor ?v2) (estado ?s2))
    (celda (fila ?i) (columna 3) (valor ?v3) (estado ?s3))
    (celda (fila ?i) (columna 4) (valor ?v4) (estado ?s4))
    (celda (fila ?i) (columna 5) (valor ?v5) (estado ?s5))
    (celda (fila ?i) (columna 6) (valor ?v6) (estado ?s6))
    (celda (fila ?i) (columna 7) (valor ?v7) (estado ?s7))
    (celda (fila ?i) (columna 8) (valor ?v8) (estado ?s8))
    (celda (fila ?i) (columna 9) (valor ?v9) (estado ?s9))
    =>
    (retract ?h)
    (bind ?fila1 (sym-cat ?v1 ?v2 ?v3 ?v4 ?v5 ?v6 ?v7 ?v8 ?v9))
    (bind ?w1 (if (eq ?s1 asignado) then ?v1
  	      else (if (eq ?s1 eliminado) then " " else "?")))
    (bind ?w2 (if (eq ?s2 asignado) then ?v2
  	      else (if (eq ?s2 eliminado) then " " else "?")))
    (bind ?w3 (if (eq ?s3 asignado) then ?v3
  	      else (if (eq ?s3 eliminado) then " " else "?")))
    (bind ?w4 (if (eq ?s4 asignado) then ?v4
  	      else (if (eq ?s4 eliminado) then " " else "?")))
    (bind ?w5 (if (eq ?s5 asignado) then ?v5
  	      else (if (eq ?s5 eliminado) then " " else "?")))
    (bind ?w6 (if (eq ?s6 asignado) then ?v6
  	      else (if (eq ?s6 eliminado) then " " else "?")))
    (bind ?w7 (if (eq ?s7 asignado) then ?v7
  	      else (if (eq ?s7 eliminado) then " " else "?")))
    (bind ?w8 (if (eq ?s8 asignado) then ?v8
  	      else (if (eq ?s8 eliminado) then " " else "?")))
    (bind ?w9 (if (eq ?s9 asignado) then ?v9
  	      else (if (eq ?s9 eliminado) then " " else "?")))
    (bind ?fila2 (sym-cat ?w1 ?w2 ?w3 ?w4 ?w5 ?w6 ?w7 ?w8 ?w9))
    (printout t "|" ?fila1 "|        |" ?fila2 "|" crlf)
    (if (= ?i 9)
        then (printout t "+---------+        +---------+" crlf)
      else (assert (imprime (+ ?i 1)))))
  

  Para cualquier puzle se muestra a la izquierda el estado inicial del tablero y a la derecha la situación a la que se llega tras aplicar todas las estrategias de resolución. En el tablero de la derecha, las celdas que tienen un estado asignado contienen el valor numérico asociado, las celdas que tienen un estado eliminado contienen un espacio en blanco y las celdas con el estado desconocido contienen un símbolo ?.

  Objetivos del trabajo

  El trabajo consiste en desarrollar un conjunto de reglas para resolver un Hitori de forma deductiva, es decir, determinando si el valor de cada celda debe ser eliminado o asignado.

  El fichero de ejemplos proporcionado está organizado de menor a mayor dificultad, en bloques de 10. De esta forma los 10 primeros son los más fáciles y los 10 últimos los más difíciles. Estos ejemplos han sido tomados de la aplicación "Real Hitori" para Android. El sistema de producción resultante debe ser capaz de resolver la mayor cantidad posible de estos ejemplos.

  El trabajo se podrá enviar a través de la aplicación Web disponible a tal efecto hasta la fecha indicada en la propia aplicación Web. Se enviará en ficheros de texto (con extensión CLP) con la identificación (nombre y dni) del autor del trabajo, la descripción y justificación de las reglas deductivas implementadas (comentada al estilo CLIPS) y el código CLIPS de la implementación. También se puede acompañar el envío con un fichero PDF describiendo las reglas deductivas implementadas.

  Criterios de evaluación

  Los criterios de evaluación serán los siguientes:

  • El número y la corrección de las reglas deductivas implementadas
  • El número de ejemplos resueltos
  • Claridad y buen estilo de programación CLIPS
  • Documentación del trabajo
  • Presentación del trabajo realizado (sólo si es necesario)