%
% Solver for 3D puzzle described at
% http://www.jaapsch.net/puzzles/woodntdie.htm
%
% A die (3x3 cube) has to be assembled from 9 3x1 bars.
% The bars have 21 dots in given locations. The resulting die must
% have the usual markings, such that opposite sides add up to 7.
%
% This gives 8 solution, of which 4 are different:
%
%  a d b  f g h  c f e  [vertical, vertical, vertical]
%  a d b  f g h  c f e  [vertical, horizontal, vertical]
%  a d b  h g f  c f e  [vertical, vertical, vertical]
%  a d b  h g f  c f e  [vertical, horizontal, vertical]
%
% Sample run:
% ?- solve.
%
%    top  1 0 1
%         0 0 0
%         1 0 1
%  west   south  east   north
%  1 1 1  0 0 1  0 0 0  1 0 1
%  0 0 0  0 0 0  0 1 0  0 1 0
%  1 1 1  1 0 0  0 0 0  1 0 1
% 
%         1 0 0
%         0 1 0
%    bot  0 0 1
% 
% a d b f1 g h c f2 e [vertical, vertical, vertical]
% Yes (0.04s cpu, solution 1, maybe more)
% ...
%
% Author: Joachim Schimpf
% This code may be freely used for any purpose.
%

solve :-

        BarsGiven = [
            a-[1,0, 1,0,1, 1,0,1],
            b-[1,1, 1,0,1, 0,0,1],
            c-[1,1, 1,0,1, 0,0,0],
            d-[0,0, 1,0,1, 0,0,0],
            e-[1,0, 1,0,0, 0,0,0],
            f1-[0,0, 0,1,0, 0,0,0],
            f2-[0,0, 0,1,0, 0,0,0],
            g-[1,0, 0,0,0, 0,0,0],
            h-[0,0, 0,0,0, 0,0,0]],

        % A die is a list of 6 faces
        Die = [West,East,North,South,Top,Bot],

        % The face values we require (some have 2 orientations)
        One   = [0,0,0,
                 0,1,0,
                 0,0,0],
        TwoA  = [1,0,0,
                 0,0,0,
                 0,0,1],
        TwoB  = [0,0,1,
                 0,0,0,
                 1,0,0],
        ThreeA= [1,0,0,
                 0,1,0,
                 0,0,1],
        ThreeB= [0,0,1,
                 0,1,0,
                 1,0,0],
        Four  = [1,0,1,
                 0,0,0,
                 1,0,1],
        Five  = [1,0,1,
                 0,1,0,
                 1,0,1],
        SixA  = [1,1,1,
                 0,0,0,
                 1,1,1],
        _SixB = [1,0,1,
                 1,0,1,
                 1,0,1],
        
        % Enumerate the possible Face arrangements
        % Allow both chiralities plus different orientations of 2 and 3
        West = SixA, East = One,        % fix the east and west faces
        (
            % Western/right-handed/counterclockwise markings
            Top = Four, (Bot = ThreeA ; Bot = ThreeB),  % Bot/Top is symmetric
            (
                South = Five, (North = TwoA ; North = TwoB)
            ;
                North = Five, (South = TwoA ; South = TwoB)
            )
        ;
            % Chinese/left-handed/clockwise markings
            Top = Five, (Bot = TwoA ; Bot = TwoB),      % Bot/Top is symmetric
            (
                South = Four, (North = ThreeA ; North = ThreeB)
            ;
                North = Four, (South = ThreeA ; South = ThreeB)
            )
        ),

        % Map die to bars
        die_to_bars(Die, BarsInCube, Orientation),

        % Place a permutation of the given bars into the cube
        listut:perm(BarsInCube, BarsGiven),

        % print result
        print_die(Die),
        ( foreach(BarName-_Bar,BarsInCube) do printf("%w ", [BarName]) ),
        writeln(Orientation).


% Map the spot locations on the die to corresponding locations on the bars.
% This gives multiple solutions, according to the orientation
% (vertical/horizontal) and the direction of the bars.

die_to_bars([West,East,North,South,Top,Bot], BarsInCube, Orientation) :-

        West  = [WNT,WMT,WST,
                 WNM,WMM,WSM,
                 WNB,WMB,WSB],

        East  = [ENT,EMT,EST,
                 ENM,EMM,ESM,
                 ENB,EMB,ESB],

        North = [NWT,NMT,NET,
                 NWM,NMM,NEM,
                 NWB,NMB,NEB],

        South = [SWT,SMT,SET,
                 SWM,SMM,SEM,
                 SWB,SMB,SEB],

        Top   = [TNW,TNM,TNE,
                 TMW,TMM,TME,
                 TSW,TSM,TSE],

        Bot   = [BNW,BNM,BNE,
                 BMW,BMM,BME,
                 BSW,BSM,BSE],

        BarsInCube = [
            _-BarWNT, _-BarWMM, _-BarWSB,
            _-BarMNT, _-BarMMM, _-BarMSB,
            _-BarENT, _-BarEMM, _-BarESB],

        % A bar is represented as an 8-element list:
        % [Top,Bot,FrontTop,FrontMiddle,FrontTop,SideTop,SideMiddle,SideBot]

        % The possible orientations of the bars in the cube
        Orientation = [vertical, MOrientation, EOrientation],

        % let the west-face bars be fixed vertically
        edge(BarWNT,   [TNW,BNW, NWT,NWM,NWB, WNT,WNM,WNB]),
        center(BarWMM, [TMW,BMW, WMT,WMM,WMB, 0,0,0]),
        edge(BarWSB,   [TSW,BSW, WST,WSM,WSB, SWT,SWM,SWB]),

        % the middle bars can be vertical or horizontal
        (
            MOrientation = vertical,
            center(BarMNT, [TNM,BNM, NMT,NMM,NMB, 0,0,0]),
            center(BarMMM, [TMM,BMM, 0,0,0,       0,0,0]),
            center(BarMSB, [TSM,BSM, SMT,SMM,SMB, 0,0,0])
        ;
            MOrientation = horizontal,
            center(BarMNT, [NMT,SMT, TNM,TMM,TSM, 0,0,0]),
            center(BarMMM, [NMM,SMM, 0,0,0,       0,0,0]),
            center(BarMSB, [NMB,SMB, BNM,BMM,BSM, 0,0,0])
        ),

        % the east-face bars can be vertical or horizontal
        (
            EOrientation = vertical,
            edge(BarENT,   [TNE,BNE, ENT,ENM,ENB, NET,NEM,NEB]),
            center(BarEMM, [TME,BME, EMT,EMM,EMB, 0,0,0]),
            edge(BarESB,   [TSE,BSE, SET,SEM,SEB, EST,ESM,ESB])
        ;
            EOrientation = horizontal,
            edge(BarENT,   [SET,NET, EST,EMT,ENT, TSE,TME,TNE]),
            center(BarEMM, [SEM,NEM, ESM,EMM,ENM, 0,0,0]),
            edge(BarESB,   [SEB,NEB, BSE,BME,BNE, ESB,EMB,ENB])
        ).


% edge bars can be flip-rotated
edge(Bar, Bar).
edge(Bar, Out) :-
        Bar = [A,D,B1,B2,B3,C1,C2,C3],
        Out = [D,A,C3,C2,C1,B3,B2,B1],
        Out \== Bar.	% avoid repeated solutions

% center bars can be plain flipped
center(Bar, Bar).
center(Bar, Out) :-
        Bar = [A,D,B1,B2,B3,0,0,0],
        Out = [D,A,B3,B2,B1,0,0,0],
        Out \== Bar.	% avoid repeated solutions


print_die([[WNT,WMT,WST, WNM,WMM,WSM, WNB,WMB,WSB],
           [ENT,EMT,EST, ENM,EMM,ESM, ENB,EMB,ESB],
           [NWT,NMT,NET, NWM,NMM,NEM, NWB,NMB,NEB],
           [SWT,SMT,SET, SWM,SMM,SEM, SWB,SMB,SEB],
           [TNW,TNM,TNE, TMW,TMM,TME, TSW,TSM,TSE],
           [BNW,BNM,BNE, BMW,BMM,BME, BSW,BSM,BSE]]) :-
        
        % print as a "foldable" pattern
        nl,
        printf("   top  %d %d %d%n", [TNW,TNM,TNE]),
        printf("        %d %d %d%n", [TMW,TMM,TME]),
        printf("        %d %d %d%n", [TSW,TSM,TSE]),
        printf(" west   south  east   north%n", []),
        printf(" %d %d %d  %d %d %d  %d %d %d  %d %d %d%n", [WNT,WMT,WST,SWT,SMT,SET,EST,EMT,ENT,NET,NMT,NWT]),
        printf(" %d %d %d  %d %d %d  %d %d %d  %d %d %d%n", [WNM,WMM,WSM,SWM,SMM,SEM,ESM,EMM,ENM,NEM,NMM,NWM]),
        printf(" %d %d %d  %d %d %d  %d %d %d  %d %d %d%n", [WNB,WMB,WSB,SWB,SMB,SEB,ESB,EMB,ENB,NEB,NMB,NWB]),
        nl,
        printf("        %d %d %d%n", [BSW,BSM,BSE]),
        printf("        %d %d %d%n", [BMW,BMM,BME]),
        printf("   bot  %d %d %d%n", [BNW,BNM,BNE]),
        nl.