Estoy empezando a aprender restricciones en prolog en este momento usando SICStus Prolog. Aunque sé cómo resolver problemas simpe usando esto, tengo un ejercicio en el que debo resolver un rompecabezas. Sin embargo, no tengo idea de cómo resolver esto ya que tendré varios elementos diferentes con diferentes propiedades (piezas), ¿alguien puede darme un ejemplo de cómo hacer representar una lista de piezas en el prólogo y qué tipo de restricciones debo usar?

1
user697110 1 dic. 2011 a las 18:08
¿Puede darnos precisiones sobre el rompecabezas en sí? Los rompecabezas son una categoría bastante grande de lo que puedo ver al buscar en Google.
 – 
m09
1 dic. 2011 a las 18:13
Bueno, el rompecabezas en sí es este jaapsch.net/puzzles/rapids.htm aunque para Para mí, un ejemplo de cómo hacer un rompecabezas simple de piezas que encajen entre sí es suficiente para comenzar.
 – 
user697110
1 dic. 2011 a las 18:16
En la mayoría de los rompecabezas, la orientación de las piezas se limita a cuatro direcciones y su ubicación cae aproximadamente en una cuadrícula cartesiana. Su rompecabezas de ejemplo es un poco más restringido en el sentido de que solo se permiten dos orientaciones (hacia la izquierda o hacia la derecha) para cada pieza, y las ubicaciones están exactamente en una cuadrícula cartesiana de 3x4. El borde del rompecabezas proporciona las condiciones del borde en el ejemplo, mientras que en un rompecabezas normal, las piezas del borde deben distinguirse por sus bordes rectos (o esquinas) y ensamblarse para proporcionar las condiciones del borde para las piezas interiores.
 – 
hardmath
1 dic. 2011 a las 20:12

1 respuesta

La mejor respuesta

Para un primer intento, haría algo en este sentido:

Para cada campo, use 5 variables. La primera variable denota la pieza del rompecabezas que va al campo. Cada pieza tiene su propia identificación. En el caso del rompecabezas que mencionaste en tu comentario anterior, hay 12 piezas, por lo que cada variable tendría un dominio de {1..12}:

P #:: 1..12,

Las otras cuatro variables denotan los cuatro bordes de cada campo y si la pieza del rompecabezas colocada en el campo tiene una abolladura o una pestaña allí. En su rompecabezas, cada lado "arriba" o "abajo" tiene una pestaña y una abolladura, por lo que indica si la pestaña es izquierda o derecha. De nuevo, variables de decisión booleanas.

[EL,EU,ER,ED] #:: 0..1,

Una pieza del rompecabezas se puede codificar así:

piece(1,  [](0,1,1,0)).

Esto, por ejemplo, es la pieza A en la descripción de su rompecabezas en el sitio web que proporcionó en el comentario.

Ahora puede definir la relación de vecino entre dos campos adyacentes. Dado que tiene variables booleanas y una pestaña debe cumplir con una abolladura, establece una restricción (no una "restricción") que requiere que la suma sea uno:

R1 + L2 #= 1,

Es decir, el borde derecho de la pieza en el campo uno debe coincidir con el borde izquierdo de la pieza en el campo 2.

También establece restricciones similares para los bordes a lo largo de los bordes.

Luego establece una restricción que requiere que todos los campos deben contener piezas diferentes:

alldifferent(Fields),

(donde Fields es la lista que contiene las variables P)

Necesitas una variable que denote la orientación de las piezas del rompecabezas:

O #:: 0..1,

Solo necesitas una, ya que en tu rompecabezas todas las piezas deben estar orientadas en la misma dirección.

Finalmente, necesita restricciones que combinen las variables de pieza, orientación y borde para cada campo, de modo que cuando seleccione una pieza para un campo (y se conozca la orientación) pueda establecer las variables de borde de manera apropiada:

 once(piece(N, [](L,U,V,D))),
 ( ((P#=N) #/\ (O#=0)) #=> ((EL#=L) #/\ (EU#=  U) #/\ (ER#=R) #/\ (ED#=  D)) ),
 ( ((P#=N) #/\ (O#=1)) #=> ((EL#=R) #/\ (EU#=1-D) #/\ (ER#=L) #/\ (ED#=1-U)) ),

(la sintaxis no es para Sicstus, sino para ECLiPSe. Sin embargo, las bibliotecas de restricciones FD deberían ser lo suficientemente similares)

Tenga en cuenta que tuve que invertir la codificación para el borde inferior cuando volteé una pieza. Esto me permite mantener las restricciones de "suma es igual a uno" para los bordes arriba / abajo, pero es subóptimo, ya que me impidió propagar fácilmente la información de las variables del borde a las variables de la pieza (una pieza puede obtener la misma codificación que otro cuando se pone boca abajo). Pero fui demasiado vago para cambiar la codificación para este primer intento.

(Editar: esto debería ser fácil de arreglar invirtiendo la codificación para el borde inferior, por ejemplo: piece(1, [](0,1,1,1))., y usando restricciones que requieren que los bordes arriba y abajo de las piezas vecinas tengan el mismo valor en lugar de tener una suma uno).

Unir todos y simplemente etiquetar las variables P (después de instanciar la variable de orientación primero) da las dos soluciones:

?- rapids(S,O).
S = []([](5, 2, 8, 6), [](11, 10, 1, 4), [](3, 9, 12, 7))
O = 0
Yes (0.01s cpu, solution 1, maybe more)
S = []([](5, 3, 11, 12), [](8, 9, 7, 4), [](2, 10, 6, 1))
O = 1
Yes (0.04s cpu, solution 2, maybe more)
No (0.05s cpu)

Usé matrices en lugar de listas, para hacer más prominentes las filas del campo del rompecabezas. Las matrices también permiten un acceso más rápido a los campos vecinos en diferentes filas.

4
twinterer 2 dic. 2011 a las 00:35