I'm making a 8-puzzle solver in prolog, and I'm having a hard time figuring out how to program the rules of the game. The initial state of the game is represented as a list-of-lists, like: [[2,8,3,],[1,6,4],[7,0,5]]. I need to make the program move the 0 to another position that is adjacent to its initial position, and I have no idea how to do it. I know how to manipulate lists using nth0, select, append, etc. But have no idea on how to manipulate a matrix(list-of-lists) in prolog.
I would appreciate any help, thanks!
I've tried using chatGPT, but it didint help.
line_matching([], [], []).
line_matching([X|Y], [X|Z], S):- line_matching(Y, Z, S).
line_matching([X|Y], [W|Z], [X|K]):- line_matching(Y, Z, K).
list_count([], 0).
list_count([X|Y], R):- list_count(Y, R2), R is R2 + 1.
wrong_position(Line, 1, Y):- line_matching(Line, [1, 2, 3], Z), list_count(Z,Y).
wrong_position(Line, 2, Y):- line_matching(Line, [8, 0, 4], Z), list_count(Z,Y).
wrong_position(Line, 3, Y):- line_matching(Line, [7, 6, 5], Z), list_count(Z,Y)
I dont know if they are useful for this kind of problem, I'm completely lost.
Another possible solution (which does not need additional libraries):
% left/right movements
lr([[0,A,B], L2, L3], [[A,0,B], L2, L3]).
lr([[A,0,B], L2, L3], [[A,B,0], L2, L3]).
lr([L1, [0,A,B], L3], [L1, [A,0,B], L3]).
lr([L1, [A,0,B], L3], [L1, [A,B,0], L3]).
lr([L1, L2, [0,A,B]], [L1, L2, [A,0,B]]).
lr([L1, L2, [A,0,B]], [L1, L2, [A,B,0]]).
% up/down movements
ud([[0,A,B], [C,D,E], L3], [[C,A,B], [0,D,E], L3]).
ud([[A,0,B], [C,D,E], L3], [[A,D,B], [C,0,E], L3]).
ud([[A,B,0], [C,D,E], L3], [[A,B,E], [C,D,0], L3]).
ud([L1, [0,A,B], [C,D,E]], [L1, [C,A,B], [0,D,E]]).
ud([L1, [A,0,B], [C,D,E]], [L1, [A,D,B], [C,0,E]]).
ud([L1, [A,B,0], [C,D,E]], [L1, [A,B,E], [C,D,0]]).
% all movements
mv(rt, Old, New) :- lr(Old, New).
mv(lt, Old, New) :- lr(New, Old).
mv(up, Old, New) :- ud(New, Old).
mv(dn, Old, New) :- ud(Old, New).
% Tests
test(N) :-
board(N, Old),
forall(mv(Action, Old, New),
format('~w --(~w)--> ~w\n', [Old, Action, New])).
board(1, [[2, 8, 3],
[1, 6, 4],
[7, 0, 5]]).
board(2, [[1, 2, 3],
[4, 0, 5],
[6, 7, 8]]).
Examples:
?- test(1).
[[2,8,3],[1,6,4],[7,0,5]] --(rt)--> [[2,8,3],[1,6,4],[7,5,0]]
[[2,8,3],[1,6,4],[7,0,5]] --(lt)--> [[2,8,3],[1,6,4],[0,7,5]]
[[2,8,3],[1,6,4],[7,0,5]] --(up)--> [[2,8,3],[1,0,4],[7,6,5]]
true.
?- test(2).
[[1,2,3],[4,0,5],[6,7,8]] --(rt)--> [[1,2,3],[4,5,0],[6,7,8]]
[[1,2,3],[4,0,5],[6,7,8]] --(lt)--> [[1,2,3],[0,4,5],[6,7,8]]
[[1,2,3],[4,0,5],[6,7,8]] --(up)--> [[1,0,3],[4,2,5],[6,7,8]]
[[1,2,3],[4,0,5],[6,7,8]] --(dn)--> [[1,2,3],[4,7,5],[6,0,8]]
true.