Mathadonf de D. Strainchamps

Accueil > Cours magistraux > Solution du solitaire à 45 alvéoles (45 peg-solitaire) en prolog

Solution du solitaire à 45 alvéoles (45 peg-solitaire) en prolog

lundi 30 mars 2009

Pour résoudre le solitaire à 45 alvéoles j’utilise le langage prolog, et la distribution ciao-prolog.

S = [deplacement(_,60,69,78),deplacement(_,67,68,69),deplacement(_,49,58,67),

deplacement(_,76,67,58),deplacement(_,47,48,49),deplacement(_,29,38,47),

deplacement(_,46,47,48),deplacement(_,49,48,47),deplacement(_,28,37,46),

deplacement(_,46,47,48),deplacement(_,78,69,60),deplacement(_,51,60,69),

deplacement(_,53,52,51),deplacement(_,35,44,53),deplacement(_,54,53,52),

deplacement(_,36,45,54),deplacement(_,51,52,53),deplacement(_,33,42,51),

deplacement(_,40,41,42),deplacement(_,54,53,52),deplacement(_,51,52,53),

deplacement(_,42,43,44),deplacement(_,53,44,35),deplacement(_,22,31,40),

deplacement(_,24,23,22),deplacement(_,6,15,24),deplacement(_,13,22,31),

deplacement(_,31,30,29),deplacement(_,48,39,30),deplacement(_,29,30,31),

deplacement(_,35,34,33),deplacement(_,4,5,6),deplacement(_,40,31,22),

deplacement(_,24,33,42),deplacement(_,50,59,68),deplacement(_,77,68,59),

deplacement(_,58,59,60),deplacement(_,69,60,51),deplacement(_,51,42,33),

deplacement(_,33,32,31),deplacement(_,31,22,13),deplacement(_,13,14,15),

deplacement(_,6,15,24)]

Le programme

% Solution of 45-peg solitaire

76 77 78

67 68 69

58 59 60

46 47 48 49 50 51 52 53 54

37 38 39 40 41 42 43 44 45

28 29 30 31 32 33 34 35 36

22 23 24

13 14 15

4 5 6

 :- use_module(library(lists)).

 :- use_module(library(numlists)).

 :- use_module(library(aggregates)).

 :- use_module(library(sort)).

 :- use_module(library(random)).

initial_state(sol,sol([4,5,6,13,14,15,22,23,24,

28,29,30,31,32,33,34,35,36,

37,38,39,40,41,42,43,44,45,

46,47,48,49,50,51,52,53,54,

58,59,60,67,68,69,76,77],[78])).

final_state(sol([_,_,_,_,_,_,_,_,_,_,_,_,_],[_,_,_,_,_,_,_,_,_,

_,_,_,_,_,_,_,_,_,

_,_,_,_,_,_,_,_,_,

_,_,_,_,_])).

deplacement(3,X,Y,Z) :-

Z=\=46,

Z=\=47,

Z=\=37,

Z=\=38,

Y is Z - 1,

X is Z - 2.

deplacement(1,X,Y,Z) :-

Y is Z - 9,

X is Z - 18.

deplacement(2,X,Y,Z) :-

Y is Z + 9,

X is Z + 18.

deplacement(4,X,Y,Z) :-

Z=\=45,

Z=\=44,

Z=\=36,

Z=\=35,

Y is Z + 1,

X is Z + 2.

move(sol(V,W),deplacement(_,X,Y,Z)) :-

member(Z,W),

deplacement(_,X,Y,Z),

member(X,V),

member(Y,V).

update(sol(V,W),deplacement(_,X,Y,Z),sol(V1,W1)) :-

delete(V,X,V2),

delete(V2,Y,V3),

V4 = Z,

sort(V4,V1),

delete(W,Z,W2),

W3=X,Y,

sort(W3,W1).

value(4,1).

value(5,1).

value(32,1).

value(40,1).

value(58,1).

value(13,2).

value(14,2).

value(31,2).

value(34,2).

value(39,2).

value(50,3).

value(59,3).

value(78,3).

value(22,4).

value(42,4).

value(45,4).

value(47,4).

value(77,4).

value(29,5).

value(30,5).

value(35,5).

value(51,5).

value(54,5).

value(67,5).

value(6,6).

value(15,6).

value(24,6).

value(37,6).

value(49,7).

value(76,7).

value(33,8).

value(36,8).

value(44,8).

value(48,8).

value(23,9).

value(38,9).

value(43,9).

value(60,9).

value(69,9).

value(28,10).

value(41,10).

value(46,10).

value(52,10).

value(53,10).

value(68,10).

produce_value(X) :-

random(1,4,Value),

assertz(value(X,Value)).

produce_all_values([]).

produce_all_values(X) :-

produce_value(X),

produce_all_values(Xs).

evaluate([],[]).

evaluate(Boule,V) :-

value(Boule,V),

evaluate(Board,Value).

evaluate_board(sol(Board,_),Value) :-

evaluate(Board,ListValue),

sum_list(ListValue,Value).

inserts(Value,frontier,frontier1) :-

insert(Value,frontier,frontier0),

inserts(Values,frontier0,frontier1).

inserts([],frontier,frontier).

insert(State,[],[State]).

insert(State,State1,State,State1) :-

lesseq_value(State,State1).

insert(State,State1,State) :-

equals(State,State1).

insert(State,State1,State1) :-

greater_value(State,State1),

insert(State,States,States1).

equals(state(S,_,V),state(S,_,V)).

lesseq_value(state(S1,_,V1),state(S2,_,V2)) :- nocontainsx([S2],S1),V2>=V1.

greater_value(state(_,_,V1),state(_,_,V2)) :-V1>V2.

update_frontier(M,State,Path,History,,1) :-

update(State,M,State1),

evaluate_board(State1,Value),

+ member(State1,History),

insert(state(State1,M,Value),,0),

update_frontier(Ms,State,Path,History,0,1).

update_frontier([],_,_,_,,).

solve_best(state(State,Path,_),_,Moves) :-

final_state(State),

reverse(Path,[],Moves).

solve_best(state(State,Path,_),History,inalPath) :-

findall(M,move(State,M),Moves),

update_frontier(Moves,State,Path,History,frontier,frontier1),

solve_best(rontier1,State,inalPath).

test_bfs(Problem,Moves) :-

initial_state(Problem,State),

solve_best([state(State,[],[])],[State],Moves).

board(Xs,Ynew) :-

board10(deplacement(_,X1,X2,X3),Y), !,

delete(Y,X1,Y1),

delete(Y1,X2,Y2),

Y3 = X3,

sort(Y3,Ynew).

board(Xs,Ynew) :-

board(deplacement(_,X1,X2,X3),Y),

delete(Y,X1,Y1),

delete(Y1,X2,Y2),

Y3 = X3,

sort(Y3,Ynew).

jeu(Y,Z,[Move]) :-

member(X3,Z),

deplacement(_,X1,X2,X3),

member(X1,Y),

member(X2,Y),

delete(Y,X1,Y1),

delete(Y1,X2,Y2),

Y3 = X3,

length(Y3,1),

Move = deplacement(_,X1,X2,X3).

jeu(Y,Z,Move) :-

member(X3,Z),

deplacement(_,X1,X2,X3),

member(X1,Y),

member(X2,Y),

delete(Y,X1,Y1),

delete(Y1,X2,Y2),

Y3 = X3,

sort(Y3,Y4),

delete(Z,X3,Z1),

Z2 = X1,X2,

sort(Z2,Z3),

Move = deplacement(_,X1,X2,X3),

jeu(Y4,Z3,Moves).

main(S) :-

test_bfs(sol,X),

retractall(board10(_,_)),

assertz(board10(X,[4,5,6,13,14,15,22,23,24,

28,29,30,31,32,33,34,35,36,

37,38,39,40,41,42,43,44,45,

46,47,48,49,50,51,52,53,54,

58,59,60,67,68,69,76,77])),

board([],Y),

difference([4,5,6,13,14,15,22,23,24,

28,29,30,31,32,33,34,35,36,

37,38,39,40,41,42,43,44,45,

46,47,48,49,50,51,52,53,54,

58,59,60,67,68,69,76,77,78],Y,Z),

jeu(Y,Z,Moves),

append(X,Moves,S).