/* Maze (rolling dice puzzle) in Picat. See the description of the problem in Kenichi Sasagawa "A Puzzle 37 Years in the Solving" https://medium.com/@kenichisasagawa/a-puzzle-37-years-in-the-making-7d54090d7c4a """ The Puzzle You’re given an 18x18 grid filled with numbers from 1 to 6. You start with a die placed in the upper-left corner. The challenge is to roll the die (not slide it) across the board to the bottom-right corner. At each square, the die’s bottom face must match the number written on the grid. ... The original puzzle author said there are four valid solutions. """ The code is a port of the N-Prolog program: https://github.com/sasagawa888/nprolog/blob/master/example/maze.pl Output from the B-Prolog program (and my Picat program rolling_dice_maze.pi): This has 116 steps. [[[17,17],3],[[16,17],6],[[16,16],5],[[16,15],1],[[16,14],2],[[15,14],4],[[14,14],5],[[13,14],3],[[13,15],1],[[14,15],5],[[15,15],6],[[15,16],4],[[15,17],1],[[14,17],5],[[13,17],6],[[13,16],4],[[13,15],1],[[12,15],2],[[12,14],3],[[11,14],6],[[10,14],4],[[9,14],1],[[8,14],3],[[8,15],2],[[8,16],4],[[9,16],1],[[9,17],5],[[8,17],4],[[7,17],2],[[7,16],1],[[6,16],3],[[6,15],5],[[5,15],6],[[4,15],2],[[4,14],4],[[4,13],5],[[4,12],3],[[5,12],6],[[5,11],2],[[5,10],1],[[4,10],3],[[3,10],6],[[2,10],4],[[2,9],5],[[2,8],3],[[3,8],6],[[3,7],2],[[3,6],1],[[3,5],5],[[4,5],4],[[5,5],2],[[6,5],3],[[6,4],6],[[6,3],4],[[6,2],1],[[5,2],2],[[5,1],3],[[5,0],5],[[6,0],1],[[7,0],2],[[8,0],6],[[8,1],3],[[9,1],5],[[10,1],4],[[11,1],2],[[11,2],1],[[11,3],5],[[11,4],6],[[11,5],2],[[12,5],3],[[13,5],5],[[13,6],1],[[13,7],2],[[12,7],3],[[12,8],6],[[11,8],5],[[10,8],1],[[10,7],3],[[10,6],6],[[10,5],4],[[10,4],1],[[9,4],2],[[8,4],6],[[8,5],4],[[8,6],1],[[8,7],3],[[7,7],5],[[6,7],4],[[6,8],6],[[7,8],5],[[8,8],1],[[9,8],2],[[9,7],4],[[9,6],5],[[8,6],1],[[7,6],2],[[6,6],6],[[6,7],4],[[5,7],5],[[4,7],3],[[3,7],2],[[2,7],4],[[2,6],6],[[1,6],5],[[0,6],1],[[0,5],3],[[0,4],6],[[1,4],5],[[1,3],4],[[2,3],1],[[3,3],3],[[3,2],2],[[2,2],1],[[2,1],4],[[2,0],6],[[1,0],5]] CPU time 0.006 seconds. Backtracks: 0 This planner model best_plan/3: 80 steps cost = 80 pos = [[[2,1],5],[[3,1],6],[[3,2],4],[[3,3],1],[[4,3],2],[[4,4],3],[[3,4],1],[[2,4],4],[[2,5],5],[[1,5],6],[[1,6],3],[[1,7],1],[[2,7],5],[[3,7],6],[[3,8],4],[[4,8],2],[[5,8],3],[[6,8],5],[[7,8],4],[[7,7],6],[[8,7],2],[[9,7],1],[[10,7],5],[[10,8],4],[[10,9],2],[[9,9],1],[[8,9],5],[[7,9],6],[[7,8],4],[[8,8],5],[[9,8],3],[[9,7],1],[[9,6],4],[[9,5],6],[[10,5],2],[[11,5],1],[[11,4],3],[[12,4],5],[[13,4],4],[[13,5],1],[[14,5],2],[[15,5],6],[[15,6],3],[[15,7],1],[[16,7],5],[[16,8],4],[[16,9],2],[[16,10],3],[[16,11],5],[[15,11],1],[[14,11],2],[[13,11],6],[[13,12],4],[[12,12],5],[[12,13],1],[[12,14],2],[[12,15],6],[[12,16],5],[[12,17],1],[[12,18],2],[[11,18],3],[[10,18],5],[[10,17],1],[[9,17],4],[[9,16],2],[[9,15],3],[[10,15],1],[[11,15],4],[[12,15],6],[[13,15],3],[[13,16],2],[[14,16],1],[[14,15],3],[[15,15],5],[[16,15],4],[[17,15],2],[[17,16],1],[[17,17],5],[[17,18],6],[[18,18],3]] pos_comparison = [[[17,17],3],[[16,17],6],[[16,16],5],[[16,15],1],[[16,14],2],[[15,14],4],[[14,14],5],[[13,14],3],[[13,15],1],[[12,15],2],[[12,14],3],[[11,14],6],[[10,14],4],[[9,14],1],[[8,14],3],[[8,15],2],[[8,16],4],[[9,16],1],[[9,17],5],[[10,17],3],[[11,17],2],[[11,16],1],[[11,15],5],[[11,14],6],[[11,13],2],[[11,12],1],[[11,11],5],[[12,11],4],[[12,10],6],[[13,10],2],[[14,10],1],[[15,10],5],[[15,9],3],[[15,8],2],[[15,7],4],[[15,6],5],[[14,6],1],[[14,5],3],[[14,4],6],[[13,4],2],[[12,4],1],[[12,3],4],[[11,3],5],[[10,3],3],[[10,4],1],[[9,4],2],[[8,4],6],[[8,5],4],[[8,6],1],[[8,7],3],[[7,7],5],[[6,7],4],[[6,8],6],[[7,8],5],[[8,8],1],[[9,8],2],[[9,7],4],[[9,6],5],[[8,6],1],[[7,6],2],[[6,6],6],[[6,7],4],[[5,7],5],[[4,7],3],[[3,7],2],[[2,7],4],[[2,6],6],[[1,6],5],[[0,6],1],[[0,5],3],[[0,4],6],[[1,4],5],[[1,3],4],[[2,3],1],[[3,3],3],[[3,2],2],[[2,2],1],[[2,1],4],[[2,0],6],[[1,0],5]] [ 1, , , ,11,12,13, , , , , , , , , , , ] [ 2, , , 9,10, ,14, , , , , , , , , , , ] [ 3, 4, 5, 8, , ,15,16, , , , , , , , , , ] [ , , 6, 7, , , ,17, , , , , , , , , , ] [ , , , , , , ,18, , , , , , , , , , ] [ , , , , , , ,19, , , , , , , , , , ] [ , , , , , ,21,30,29, , , , , , , , , ] [ , , , , , ,22,31,28, , , , , , , , , ] [ , , , ,35,34,33,32,27, , , , , ,67,66,65, ] [ , , , ,36, ,24,25,26, , , , , ,68, ,64,63] [ , , ,38,37, , , , , , , , , ,69, , ,62] [ , , ,39, , , , , , , ,55,56,57,70,59,60,61] [ , , ,40,41, , , , , ,53,54, , ,71,72, , ] [ , , , ,42, , , , , ,52, , , ,74,73, , ] [ , , , ,43,44,45, , , ,51, , , ,75, , , ] [ , , , , , ,46,47,48,49,50, , , ,76, , , ] [ , , , , , , , , , , , , , ,77,78,79,80] [ , , , , , , , , , , , , , , , , ,81] Testing with plan/3, here are another, using plan/3: [ 1, , , , 11, 12, 13, , , , , , , , , , , ] [ 2, , , 9, 10, , 14, , , , , , , , , , , ] [ 3, 4, 5, 8, , , 15, 16, 73, 74, 75, , , , , , , ] [ , , 6, 7, , 69, 70, 71, 72, , 76, , , , , , , ] [ , , , , , 68, 67, 66, 65, 64, 77, , 81, 82, 83, 84, , ] [ , , , , , , , 19, , 63, 78, 79, 80, , , 85, , ] [ , , , , , , 21, 30, 29, , 61, , , , , 86, 87, ] [ , , , , , , 22, 31, 28, , 60, 59, , , , , 88, 89] [ , , , , 35, 34, 33, 32, 27, , , 58, , , 95, 94, 93, 90] [ , , , , 36, , 24, 25, 26, , , 57, , , 96, , 92, 91] [ , , , 38, 37, , , , , , , 56, , , 97, , , ] [ , , , 39, , , , , , , , 55, , , 98, , , ] [ , , , 40, 41, , , , , , 53, 54, , , 99,100, , ] [ , , , , 42, , , , , , 52, , , ,102,101, , ] [ , , , , 43, 44, 45, , , , 51, , , ,103, , , ] [ , , , , , , 46, 47, 48, 49, 50, , , ,104, , , ] [ , , , , , , , , , , , , , ,105,106,107,108] [ , , , , , , , , , , , , , , , , ,109] Cf program rolling_dice_maze.pi This model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import planner. main => go. go ?=> dice(Dice), % Note: Here the coords are [1,1] .. [18,18] (not [0,0] .. [17,17] as in the N-Prolog program) Init = [1,1], % plan([Init,Dice],10000,Plan,Cost), % searching for alternative solution best_plan_nondet([Init,Dice],Plan,Cost), % finding the optimal solution Pos = [], T = [ [to_fstring("%3w"," ") : _ in 1..18] : _ in 1..18], Step = 1, T[1,1] := to_fstring("%3w",Step), foreach(P in Plan) Step := Step + 1, println(P), Pos := Pos ++ [P[3..4]], T[P[3,1],P[3,2]] := to_fstring("%3w",Step), end, println(cost=Cost), println(pos=Pos), println(pos_comparison=[ [[P[1,1]-1,P[1,2]-1],P[2]] : P in Pos.reverse]), foreach(Row in T) println(Row) end, nl, nl, % fail, nl. go => true. /* Here is the solution of the N-Prolog program examples/maze.pl (and my port rolling_dice_maze.pi) [ 1, , , , 11, 12, 13, , , , , , , , , , , ] [ 2, , , 9, 10, , 14, , , , , , , , , , , ] [ 3, 4, 5, 8, , , 15, 16, 73, 74, 75, , , , , , , ] [ , , 6, 7, , 69, 70, 71, 72, , 76, , , , , , , ] [ , , , , , 68, , 18, , , 77, , 81, 82, 83, 84, , ] [ 60, 61, 62, , , 67, , 19, , , 78, 79, 80, , , 85, , ] [ 59, , 63, 64, 65, 66, 21, 30, 29, , , , , , , 86, 87, ] [ 58, , , , , , 22, 31, 28, , , , , , , , 88, 89] [ 57, 56, , , 35, 34, 33, 32, 27, , , , , , 95, 94, 93, 90] [ , 55, , , 36, , 24, 25, 26, , , , , , 96, , 92, 91] [ , 54, , , 37, 38, 39, 40, 41, , , , , , 97, , , ] [ , 53, 52, 51, 50, 49, , , 42, , , , , , 98, , , ] [ , , , , , 48, , 44, 43, , , , , , 99,100, , ] [ , , , , , 47, 46, 45, , , , , , ,110,109,102,103] [ , , , , , , , , , , , , , ,111,108, ,104] [ , , , , , , , , , , , , , ,112,107,106,105] [ , , , , , , , , , , , , , ,113,114,115,116] [ , , , , , , , , , , , , , , , , ,117] */ go2 => P = [[[17,17],3],[[16,17],6],[[16,16],5],[[16,15],1],[[16,14],2],[[15,14],4],[[14,14],5],[[13,14],3],[[13,15],1],[[14,15],5],[[15,15],6],[[15,16],4],[[15,17],1],[[14,17],5],[[13,17],6],[[13,16],4],[[13,15],1],[[12,15],2],[[12,14],3],[[11,14],6],[[10,14],4],[[9,14],1],[[8,14],3],[[8,15],2],[[8,16],4],[[9,16],1],[[9,17],5],[[8,17],4],[[7,17],2],[[7,16],1],[[6,16],3],[[6,15],5],[[5,15],6],[[4,15],2],[[4,14],4],[[4,13],5],[[4,12],3],[[5,12],6],[[5,11],2],[[5,10],1],[[4,10],3],[[3,10],6],[[2,10],4],[[2,9],5],[[2,8],3],[[3,8],6],[[3,7],2],[[3,6],1],[[3,5],5],[[4,5],4],[[5,5],2],[[6,5],3],[[6,4],6],[[6,3],4],[[6,2],1],[[5,2],2],[[5,1],3],[[5,0],5],[[6,0],1],[[7,0],2],[[8,0],6],[[8,1],3],[[9,1],5],[[10,1],4],[[11,1],2],[[11,2],1],[[11,3],5],[[11,4],6],[[11,5],2],[[12,5],3],[[13,5],5],[[13,6],1],[[13,7],2],[[12,7],3],[[12,8],6],[[11,8],5],[[10,8],1],[[10,7],3],[[10,6],6],[[10,5],4],[[10,4],1],[[9,4],2],[[8,4],6],[[8,5],4],[[8,6],1],[[8,7],3],[[7,7],5],[[6,7],4],[[6,8],6],[[7,8],5],[[8,8],1],[[9,8],2],[[9,7],4],[[9,6],5],[[8,6],1],[[7,6],2],[[6,6],6],[[6,7],4],[[5,7],5],[[4,7],3],[[3,7],2],[[2,7],4],[[2,6],6],[[1,6],5],[[0,6],1],[[0,5],3],[[0,4],6],[[1,4],5],[[1,3],4],[[2,3],1],[[3,3],3],[[3,2],2],[[2,2],1],[[2,1],4],[[2,0],6],[[1,0],5]].reverse, T = [ [to_fstring("%3w"," ") : _ in 1..18] : _ in 1..18], Step = 1, T[1,1] := to_fstring("%3w",Step), foreach([[R,C],N] in P) Step := Step + 1, T[R+1,C+1] := to_fstring("%3w",Step) end, foreach(Row in T) println(Row) end, nl. data([[1,4,1,3,6,3,1,4,6,6,2,1,5,6,2,1,1,4], [5,4,2,4,5,5,5,5,5,3,2,3,5,4,2,3,5,5], [6,4,1,1,1,4,6,4,3,5,4,2,4,1,5,6,6,4], [2,4,2,3,5,5,1,2,6,2,6,5,1,2,6,3,2,2], [1,1,6,3,1,4,1,3,6,4,3,4,3,5,4,2,1,3], [5,3,2,5,1,2,5,5,1,2,1,2,6,1,3,6,6,5], [1,6,1,4,6,3,6,4,6,4,3,3,1,2,3,5,3,4], [2,2,6,5,1,2,2,5,5,5,6,5,1,2,6,2,1,2], [6,3,6,4,6,4,1,3,1,1,3,4,3,5,3,2,4,4], [5,5,5,4,2,3,5,4,2,3,1,2,6,6,1,6,1,5], [1,4,6,3,1,4,6,3,1,6,4,3,4,2,4,5,1,3], [5,2,1,5,6,2,2,4,5,3,6,5,1,2,6,5,1,2], [6,3,6,4,1,3,6,3,6,1,6,4,3,5,3,2,4,4], [2,5,2,4,2,5,1,2,5,4,2,3,6,6,3,1,4,6], [1,4,1,1,6,3,1,3,6,6,1,6,3,2,5,5,2,5], [1,5,6,3,5,3,5,4,2,3,5,4,3,1,4,6,4,1], [3,1,3,6,3,3,6,3,1,1,2,1,6,3,2,1,5,6], [6,5,1,2,6,5,1,5,1,2,6,5,5,3,2,4,5,3]]). final([[18,18],_]). % Testing other longer plans. % This only finds 108 and 80 (cost +1) % final([[18,18],_]) :- % Plan = current_plan(), % println(plan=Plan=Plan.len), % Plan.len > 110. dice([F,B,U,D,L,R],[D,U,F,B,L,R],up). dice([F,B,U,D,L,R],[U,D,B,F,L,R],down). dice([F,B,U,D,L,R],[R,L,U,D,F,B],left). dice([F,B,U,D,L,R],[L,R,U,D,B,F],right). %initial dice dice([1,6,5,2,4,3]). table action([Pos,From],To,Action,Cost) :- data(Data), dice(From,To1,Dir), pos(Pos,Dir,NewPos), Val = Data[NewPos[1],NewPos[2]], Val == To1[1], To = [NewPos,To1], Action = [From,Dir,NewPos,Val,To], Cost = 1. % Valid next position pos(Pos,up,NewPos) :- Pos[1] - 1 >= 1, NewPos = [Pos[1]-1, Pos[2] ]. pos(Pos,down,NewPos) :- Pos[1] + 1 <= 18, NewPos = [Pos[1]+1, Pos[2] ]. pos(Pos,left,NewPos) :- Pos[2] - 1 >= 1, NewPos = [Pos[1], Pos[2]-1]. pos(Pos,right,NewPos) :- Pos[2] + 1 <= 18, NewPos = [Pos[1], Pos[2]+1].