programmation en prolog Fermé

Question

Bonjour,
j'aimerais savoir comment programmer un sudoku d'un grille de n*n en prolog.
merci de votre aide.

2aetuo2 · Answer

ba dit sur quoi tu bloque, on va pas te le faire ;)

lavoiture · Answer

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)).

Programmation en prolog

2 réponses

Discussions similaires