## Thursday, 21 August 2008

### Unscrambling with Prolog

`%% I'm playing this Oxyd game (inside Enigma [link])%% One of the puzzles is this scrambled configurationstarting(([-,⌋,⌊]         ,[-,  ⌈]         ,[⌉,|,|])).%% And you've to hit against the sides to unscramble it into:solution(([⌈,-,⌉]         ,[|,  |]         ,[⌊,-,⌋])).%% Then it explodes and you win a spring%% The moves you can do are:move(top_left,    ([A,B,C]    ,[D,  E]    ,[F,G,H]) --> ([B,C,A]                  ,[D,  E]                  ,[F,G,H])).move(left_down,    ([A,B,C]    ,[D,  E]    ,[F,G,H]) --> ([F,B,C]                  ,[A,  E]                  ,[D,G,H])).move(right_down,    ([A,B,C]    ,[D,  E]    ,[F,G,H]) --> ([A,B,H]                  ,[D,  C]                  ,[F,G,E])).move(bottom_left,    ([A,B,C]    ,[D,  E]    ,[F,G,H]) --> ([A,B,C]                  ,[D,  E]                  ,[G,H,F])).%% I want Prolog to solve this automatically for me though,%% My first attempt is to use recursion like so,%: solve(Win,[]) :- solution(Win).%: solve(State,[Move|Moves]) :- move(Move,State --> Next), solve(Next,Moves).%! ?- starting(State), solve(State,Moves).%! ERROR: Out of local stack%% Since Prolog searches depth first, this just kept trying top_left,%% again and again, getting nowhere, infact it seeing the same config.%% so I can pass along a list of seen configurations now, and fail when%% the same one is seen twice.%: solve(Win,[],_) :- solution(Win).%: solve(State,[Move|Moves],Seen) :- move(Move,State --> Next), not(member(Next,Seen)), solve(Next,Moves,[State|Seen]).%! ?- starting(State), solve(State,Moves,[State]).%! State = ([-, '⌋', '⌊'], [-, '⌈'], ['⌉', ('|'), ('|')]),%! Moves = [top_left, top_left, left_down, top_left, top_left, left_down, ...]%% I got a solution this time... but it's thousands of moves, I think the puzzle can be solved%% Within at least 10 moves, so Prolog should fail if it gets into a branch in the search tree that deepsolve(Win,[],_,_) :- solution(Win).solve(State,[Move|Moves],Seen,Limit) :- move(Move,State --> Next), not(member(Next,Seen)), succ(LowerLimit,Limit), solve(Next,Moves,[State|Seen],LowerLimit).solve(Solution) :- starting(State), solve(State,Solution,[State],10).%! ?- solve(Moves).%! Moves = [top_left, top_left, bottom_left, bottom_left, left_down, right_down, bottom_left,%!          bottom_left, left_down, right_down].`