Programmation en prolog

lavoiture -  
lavoiture Messages postés 8 Statut Membre -
Bonjour,
j'aimerais savoir comment programmer un sudoku d'un grille de n*n en prolog.
merci de votre aide.
Configuration: Windows XP
Firefox 3.5.5

2 réponses

  1. 2aetuo2 Messages postés 39 Statut Membre 1
     
    ba dit sur quoi tu bloque, on va pas te le faire ;)
    0
  2. lavoiture Messages postés 8 Statut Membre
     
    j'ai le code suivant mais il ne fonctionne pas bien:
    D'abord mon editeur me signale une erreur au niveau de la constrain_values
    et mes tests ne donnent pas les reponses voulues
    %?- findall(X,sudoku([1,_X,_,_,_,_,_,1,_,_,1,_,_,1,_,_]),_L),length(_L,N).
    %_L = [],
    %N = 0.
    %sudoku([_,7,_,_,6,_,_,2,_,_,_,3,2,9,7,5,_,_,_,_,6,5,_,4,3,_,_,_,6,8,_,_,_,7,1,_,1,_,7,_,_,_,9,_,5,_,9,5,_,_,_,2,8,_,_,_,4,8,_,2,1,_,_,_,_,1,3,5,6,4,_,_,_,5,_,_,1,_,_,3,_]).
    %false

    :- use_module(library(lists)).
    :- use_package(fd).

    % Main function call for the constraint version.

    sudoku(P) :- get_n(P,N),
    constrain_values(N,P),
    check_rows(N,P),
    check_cols(N,P),
    check_blks(N,P),
    labeling(P),
    nl,
    _B = round(sqrt(N)),
    print_pretty(N,_B,_B,N,_B,P).

    sudoku_noprint(P) :- get_n(P,N),
    constrain_values(N,P),
    check_rows(N,P),
    check_cols(N,P),
    check_blks(N,P),
    labeling(P).

    print_pretty(_,_,_,_,_,[]) :- nl.
    print_pretty(C,_,A,N,SqrtN,R) :- C =:= 0, A > 1, A1 = A - 1, C1 = N,
    nl, print_pretty(C1,SqrtN,A1,N,SqrtN,R).
    print_pretty(C,_,A,N,SqrtN,R) :- C =:= 0, A =:= 1, C1 = N,
    nl, nl, print_pretty(C1,SqrtN,SqrtN,N,SqrtN,R).
    print_pretty(C,B,A,N,SqrtN,[H|T]) :- C > 0, B =:= 1, C1 = C - 1,
    write(H), write(' '), print_pretty(C1,SqrtN,A,N,SqrtN,T).
    print_pretty(C,B,A,N,SqrtN,[H|T]) :- C > 0, B > 1,
    C1 = C - 1, B1 = B - 1,
    write(H), write(' '), print_pretty(C1,B1,A,N,SqrtN,T).

    constrain_values(_, []).
    constrain_values(N,[H|T]) :-
    N > 0,N1 is N-1, H in 1..N,
    constrain_values(N,T).

    check_rows(_,[]).
    check_rows(N,S) :- grab_rows(N,N,S).

    % grab_rows/3 takes the sudoku instance (a list), extracts each
    % row and then checks to see if it is a permutation of the symbol
    % list V. grab_cols/4 and grab_blks/4 work similarly.

    grab_rows(N,_,[]) :- N =:= 0.
    grab_rows(N,Len,S) :- N > 0, build_row(Len,S,Srest,Row),
    all_different(Row), N1 = N - 1,
    grab_rows(N1,Len,Srest).

    build_row(Len,T,T,[]) :- Len =:= 0.
    build_row(Len,[H|T],Srest,[H|R]) :- Len > 0, Len1 = Len - 1,
    build_row(Len1,T,Srest,R).

    % Trivial examples of build_row/4 working as desired.

    check_cols(_,[]).
    check_cols(N,S) :- grab_cols(N,N,S).

    grab_cols(N,_,_) :- N =:= 0.
    grab_cols(N,Len,S) :- N > 0, build_col(N,Len,Len,S,Col),
    all_different(Col), N1 = N - 1,
    grab_cols(N1,Len,S).

    build_col(Oset,Spcr,Len,[_|T],R) :- Oset > 1, Oset1 = Oset - 1,
    build_col(Oset1,Spcr,Len,T,R).
    build_col(Oset,Spcr,Len,[H|T],[H|R]) :- Oset =:= 1,
    Len1 = Len - 1, Oset1 = Spcr,
    build_col(Oset1,Spcr,Len1,T,R).
    build_col(Oset,_,Len,_,[]) :- Oset =:= 1, Len =:= 0, !.
    build_col(_,_,_,[],[]).

    % grab_cols/3 can certainly complete partially solved constraints
    %
    % ?- grab_cols(4,4,[X,Y,3,4,2,Z,4,W,3,4,1,2,4,1,2,3]).
    %

    check_blks(_,[]).
    check_blks(N,S) :- grab_blks(N,N,S).

    grab_blks(N,_,_) :- N =:= 0.
    grab_blks(N,Len,S) :- N > 0, _B is round(sqrt(Len)),
    _K is _B*(N - floor((N-1)/_B)*_B - 1) + 1 + _B*Len*floor((N-1)/_B),
    build_blk(_K,_B,Len,_B,Len,S,Blk),
    all_different(Blk), N1 = N - 1,
    grab_blks(N1,Len,S).

    build_blk(Oset,Tset,Len,SqrtN,N,[_|T],B) :- Oset > 1, Oset1 = Oset - 1,
    build_blk(Oset1,Tset,Len,SqrtN,N,T,B).
    build_blk(Oset,Tset,Len,SqrtN,N,[H|T],[H|B]) :- Oset =:= 1, Tset > 0,
    Tset1 = Tset - 1, Len1 = Len - 1,
    build_blk(Oset,Tset1,Len1,SqrtN,N,T,B), !.
    build_blk(Oset,Tset,Len,SqrtN,N,[_|T],B) :- Oset =:= 1, Tset =:= 0,
    Oset1 = N - (SqrtN), Tset1 = SqrtN,
    build_blk(Oset1,Tset1,Len,SqrtN,N,T,B).
    build_blk(Oset,_,Len,_,_,_,[]) :- Oset =:= 1, Len =:= 0, !.

    % --------------------------------------------------------------

    % These predicates derive the set of symbols that must appear in
    % each row / col / blk.

    get_n(S,N) :- length(S,N2), int_sqrt(N,N2).

    int_sqrt(A,B) :- A is round(sqrt(B)).
    0