% % 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.