Prolog: Imparare con l'esempio

Question

Sto cercando di imparare un po 'su swi-prolog (oltre ai programmi di base, inutili).

Qualcuno può spiegare (forse in pseudocodice) cosa sta facendo questo risolutore di sudoku e le funzioni correlate? Se hai bisogno di più riferimenti, si trova nel pacchetto CLP (FD) di swi-prolog.

Grazie!

:- 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 descrive sostanzialmente i vincoli di una soluzione Sudoku deve soddisfare, in cui il consiglio è rappresentato come una lista di nove liste di lunghezza nove. problema/2 assegna una scheda parzialmente istanziata a un numero di problema. Per usarlo dovresti fare

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

È necessario leggere i predicati utilizzati in the documentation.

Answer 2

Prolog è un modo diverso di pensare ai programmi: devi pensare in modo logico.

Prima di tutto A :- B, C, D significa A è vero (esito positivo) se B AND C AND D sono veri.

Il frammento di codice che hai postato controlli per la correttezza di un puzzle Sudoku, ci sono tre condizioni:

• elementi sono tutti diversi da filari
• elementi sono tutti diversi da colonne
• elementi sono tutto diverso da blocchi 3x3

Come funziona?

sudoku (righe) è vero se:

1. length(Rows, 9) -> ci sono 9 elementi in righe
2. maplist(_length(9), Rows) ->maplist controlli il predicato (primo parametro) su ogni elemento della lista (secondo parametro). Ciò significa che ogni riga deve essere di lunghezza 9.
3. maplist(all_distinct, Rows) -> uguale a prima, ma controlliamo se ogni riga ha elementi distinti (non uguali a coppie).
4. transpose(Rows, Columns), maplist(all_distinct, Columns) -> trasponiamo le righe in colonne per verificare se sono tutti distinti anche selezionandoli in modo verticale
5. Rows = [A,B,C,D,E,F,G,H,I] -> divide elenco righe e posizionare ognuno in una variabile diversa A, B, C, D ... quindi A sarà la prima riga, B la seconda e così via
6. blocks(A, B, C), blocks(D, E, F), blocks(G, H, I) -> questo predicato deve essere vero per le terzine di righe.

Parliamo della parte blocks, che è piuttosto divertente da capire. Vogliamo verificare che ogni blocco 3x3 contenga valori distinti. Come possiamo farlo?

Supponiamo di avere 3 righe, la condizione deve essere vera per i primi tre elementi di ogni riga (primo blocco 3x3), per elementi da 4 a 6 (secondo blocco) e 7 ° -9 ° (terzo blocco).

Quindi possiamo pensare in modo ricorsivo: blocks([],[],[]) è banalmente vero, abbiamo liste vuote.

Il caso blocks([A,B,C|Bs1],[D,E,F|Bs2],[G,H,I|Bs3]) viene scelto quando si chiama il predicato blocks con parametri che sono elencati con ALMENO 3 elementi. Quindi possiamo controllare se A, B, C, D, E, F, G, H, I sono tutti distinti, quindi chiamiamo blocks in modo ricorsivo usando come parametri gli elenchi rimanenti (senza i primi tre elementi). Questo è ciò di cui parla Prolog!

Quindi blocks verrà chiamato prima con tre righe di 9 elementi, controllerà che i primi 3 di ogni riga siano distinti e si chiami con 3 elenchi di 6 elementi, ricontrollalo e chiamino con 3 elenchi di 3 elementi , controlla di nuovo e chiama se stesso con tre liste vuote (il caso trival che si verifica sempre).

Answer 3

su "Aggiungi (righe, VS), Vs ins 1..9"

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

Ciò significa che tutti gli elementi della lista di liste devono essere di dominio 1..9.