Prólogo: Aprendiendo por ejemplo

Question

Estoy tratando de aprender un poco sobre swi-prolog (más allá de los programas básicos e inútiles).

¿Alguien puede explicar (tal vez en pseudocódigo) qué están haciendo este sudoku solver y las funciones relacionadas? Si necesita más referencia, se encuentra en el paquete CLP (FD) de swi-prolog.

Gracias!

:- use_module(library(clpfd)). 
sudoku(Rows) :-             
     length(Rows, 9), maplist(length_(9), Rows),     
     append(Rows, Vs), Vs ins 1..9,        
     maplist(all_distinct, Rows),        
     transpose(Rows, Columns), maplist(all_distinct, Columns), 
     Rows = [A,B,C,D,E,F,G,H,I],         
     blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).   


length_(L, Ls) :- length(Ls, L).         

blocks([], [], []).             
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-     
     all_distinct([A,B,C,D,E,F,G,H,I]),       
     blocks(Bs1, Bs2, Bs3).          


problem(1, [[_,_,_,_,_,_,_,_,_],         
      [_,_,_,_,_,3,_,8,5],         
      [_,_,1,_,2,_,_,_,_],         
      [_,_,_,5,_,7,_,_,_],         
      [_,_,4,_,_,_,1,_,_],         
      [_,9,_,_,_,_,_,_,_],         
      [5,_,_,_,_,_,_,7,3],         
      [_,_,2,_,1,_,_,_,_],         
      [_,_,_,_,4,_,_,_,9]]). 

Answer 1

sudoku/1 describe básicamente las limitaciones de una solución Sudoku debe satisfacer, en donde la junta se representa como una lista de nueve listas de longitud nueve. problema/2 asigna una placa parcialmente instanciada a un número de problema. Para usarlo debe hacer

? - problema (1, Junta), sudoku (Junta).

Debe leer los predicados utilizados en the documentation.

Answer 2

Prolog es una forma diferente de pensar acerca de los programas: tiene que pensar lógicamente.

Primero de todos A :- B, C, D significa A es verdadero (exitoso) si B AND C AND D son verdaderos.

El fragmento de código que envió cheques por la exactitud de un Sudoku, hay tres condiciones:

• elementos son todos diferentes por filas
• elementos son todos diferentes por columnas
• elementos son todos diferentes por 3x3 bloques

¿Cómo funciona?

sudoku (filas) es verdadero si:

1. length(Rows, 9) -> hay 9 elementos en filas
2. maplist(_length(9), Rows) ->maplist cheques el predicado (primer parámetro) en cada elemento de la lista (segundo parámetro). Esto significa que cada fila debe ser de longitud 9.
3. maplist(all_distinct, Rows) -> igual que antes, pero verificamos si cada fila tiene elementos distintos (no iguales por pares).
4. transpose(Rows, Columns), maplist(all_distinct, Columns) -> transponemos las filas en columnas para comprobar si son todos distintos también seleccionándolos en la forma vertical,
5. Rows = [A,B,C,D,E,F,G,H,I] -> divide la lista de filas y colocar cada uno en una variable diferente A, B, C, D ... así que A será la primera fila, B la segunda uno y así sucesivamente
6. blocks(A, B, C), blocks(D, E, F), blocks(G, H, I) -> este predicado debe ser verdadero para los tríos de filas.

Hablemos de la parte blocks, es bastante divertido de entender. Queremos verificar que cada bloque 3x3 contenga valores distintos. ¿Cómo podemos hacer eso?

Supongamos que tiene 3 filas, la condición debe ser verdadera para los primeros tres elementos de cada fila (primer bloque 3x3), para los elementos 4º a 6º (segundo bloque) y 7º-9º (tercer bloque).

Así que podemos pensar de forma recursiva: blocks([],[],[]) es trivialmente cierto, tenemos listas vacías.

El caso blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3]) se elige cuando se invoca el predicado blocks con parámetros enumerados con AL MENOS 3 elementos. Entonces podemos verificar si A, B, C, D, E, F, G, H, I son distintos, luego llamamos blocks recursivamente usando como parámetros las listas restantes (sin los primeros tres elementos). ¡De esto se trata Prolog!

Así que blocks se llamará primero con tres filas de 9 elementos, comprobará que los primeros 3 de cada fila sean distintos y se llame a sí mismo con 3 listas de 6 elementos, verifíquelo nuevamente y llámese con 3 listas de 3 elementos , revíselo nuevamente y llámese con tres listas vacías (el caso trival que siempre sucede).

Answer 3

sobre "append (filas, VS), Vs ins 1..9"

http://www.swi-prolog.org/pldoc/man?predicate=append%2F2

Esto significa que todos los elementos de la lista de listas deben estar en el dominio 1..9.