%% -*- mode: prolog -*-

%% Loosely based on:
%% Mark P. Jones: Solving the Snake Cube Puzzle in Haskell,
%% Journal of Functional Programming 23(2), pp. 145-160, 2013.

%% Puzzle description
cube_size(3).
segments([3,2,2,3,2,3,2,2,3,3,2,2,2,3,3,3,3]). % standard version
% segments([3,3,2,3,2,3,2,2,2,3,3,3,2,3,3,3]). % mean green version
% segments([3,2,3,2,2,4,2,3,2,3,2,3,2,2,2,2,   % king version
%           2,2,2,2,3,3,2,2,2,2,2,3,4,2,2,2,   % - requires cube_size(4)
%           4,2,3,2,2,2,2,2,2,2,2,2,4,2]).     % - slow (~2m for the 1st solution)

%% Puzzle generator - try shorter lists first (i.e., longer segments)
% segments(Ss) :- cube_size(N), N3 is N^3, between(1,N3,L), length(Ss,L), segments(Ss,N3).
% segments([],1).
% segments([S|Ss],M) :- M > 0, cube_size(N), between(2,N,S), M1 is M-S+1, segments(Ss,M1).

%% Movement in 3D
position(p(X,Y,Z)) :- cube_size(N), between(1,N,X), between(1,N,Y), between(1,N,Z).
direction(d(D,S)) :- member(D,[x,y,z]), member(S,[-1,1]).
next_dir(d(D,_),d(D1,S)) :- direction(d(D1,S)), D \== D1.
step(p(X,Y,Z),d(x,S),p(X1,Y,Z)) :- X1 is X+S.
step(p(X,Y,Z),d(y,S),p(X,Y1,Z)) :- Y1 is Y+S.
step(p(X,Y,Z),d(z,S),p(X,Y,Z1)) :- Z1 is Z+S.

%% Solver
check_move(Ps,_,1,Ps).
check_move([P|Ps],D,N,Ps1) :-
    N > 1, step(P,D,P1),
    position(P1), \+member(P1,Ps), N1 is N-1,
    check_move([P1,P|Ps],D,N1,Ps1).
solve([S],Ps,D,[D]) :- check_move(Ps,D,S,_).
solve([S|Ss],Ps,D,[D|Ds]) :-
    check_move(Ps,D,S,Ps1), next_dir(D,D1),
    solve(Ss,Ps1,D1,Ds).

%% User-friendly interface
japanese([],[]).
japanese([d(D,S)|Ds],[D1|Ds1]) :-
    (  D = x, (S = 1, D1 = 右; S = -1, D1 = 左)
     ; D = y, (S = 1, D1 = 上; S = -1, D1 = 下)
     ; D = z, (S = 1, D1 = 前; S = -1, D1 = 後) ),
    japanese(Ds,Ds1).
snake(S,P,D1,Ds1) :-
    segments(S), position(P), direction(D),
    solve(S,[P],D,Ds), japanese([D|Ds],[D1|Ds1]).

%% Standard puzzle:
%% ?- snake(Segments,StartPos,StartDir,Directions).
%% Segments   = [3,2,2,3,2,3,2,2,3,3,2,2,2,3,3,3,3],
%% StartPos   = p(1,1,1),
%% StartDir   = 右,
%% Directions = [右,上,左,前,上,後,右,前,下,左,上,後,上,前,下,右,上]

%% Generated puzzle [with minimal number of segments]:
%% ?- snake(Segments,StartPos,StartDir,Directions).
%% Segments = [2,3,3,2,3,3,3,3,3,3,3,2,3,2,3],
%% StartPos = p(1,2,2),
%% StartDir = 下,
%% Directions = [下,右,上,後,下,左,上,前,下,右,上,左,後,下,前]