/* Rotation puzzle in Picat. From GAP mailing list http://www-groups.dcs.st-and.ac.uk/~gap/ForumArchive/Harris.1/Bob.1/Re__GAP_.59/1.html """ Since you asked about what the puzzle actually is, the fellow who posted it at rec.puzzles (Kevin Buzzard ) had found it on his nokia cell phone. It is called "rotation" at Nokia's web site http://www.nokia.com/games I think this variant is level 5. The puzzle is a 4x4 square of numbers. There are four operations, each of which involves rotating the numbers in a 3x3 square clockwise. So, in the diagram below, one move is the cycle (1,2,3,7,11,10,9,5). The numbers maintain orientation-- they don't rotate; if they did, that would add another layer of complexity for the solver. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Anyone who's interested in an archive of the discussion ofthis puzzle (it's about a 40K byte text file), let me know. The discussion focuses primarily on finding minimal move sequences to swap two given tiles. There's a very well done java applet for a similar puzzle at http://www.microprizes.com/mp52.htm """ This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ % import util. import cp. % See http://www.hakank.org/picat/bplan.pi import bplan. main => go. go => % One 1-rotation: % Init = [2,3,7,4,1,6,11,8,5,9,10,12,13,14,15,16], % 2,1 % Init = [2,7,4,8,1,3,11,12,5,6,9,10,13,14,15,16], % 1,2,1 % Init = [7,4,11,8,2,3,9,12,1,5,6,10,13,14,15,16], % 1,2,3 % Init = [3,4,11,8,1,2,10,12,6,5,7,15,9,13,14,16], % 1,2,3,2,2,3 % Init = [8,12,7,15,1,4,2,10,3,6,11,14,5,9,13,16 ], % 4,4,4,1,2,3,2,2,3 Init = [8,12,7,15,1,14,16,13,3,10,11,9,5,2,4,6 ], % Random puzzle % Init = [2,4,16,11,15,7,12,1,8,9,14,3,10,5,13,6], % swap 15<->16 (GAP says 53 moves,but that's probably not optimal ) % Init = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,15 ], time(once(bplan(Init, L))), % time(bplan(Init, L)), writeln(L), Len=length(L), writeln(len=Len), nl. % Using bplan.plan2 go2 => % One 1-rotation: % Init = [2,3,7,4,1,6,11,8,5,9,10,12,13,14,15,16], % 2,1 % Init = [2,7,4,8,1,3,11,12,5,6,9,10,13,14,15,16], % 1,2,1 % Init = [7,4,11,8,2,3,9,12,1,5,6,10,13,14,15,16], % 1,2,3 % Init = [3,4,11,8,1,2,10,12,6,5,7,15,9,13,14,16], % 1,2,3,2,2,3 % Init = [8,12,7,15,1,4,2,10,3,6,11,14,5,9,13,16 ], % 4,4,4,1,2,3,2,2,3 Init = [8,12,7,15,1,14,16,13,3,10,11,9,5,2,4,6 ], % Random puzzle % Init = [2,4,16,11,15,7,12,1,8,9,14,3,10,5,13,6], % swap 15<->16 (GAP says 53 moves,but that's probably not optimal ) % Init = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,15 ], time(plan2(Init, L,Cost)), writeln(L), writeln(len=L.length), writeln(cost=Cost), nl. goal_state(Goal) => Goal=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]. % table % 1, 2, 3, 7, 11, 10, 9, 5, % move 1 (around 6) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To) ?=> M=1, To=[M5,M1,M2,M4,M9,M6,M3,M8,M10,M11,M7,M12,M13,M14,M15,M16]. % 2, 3, 4, 8, 12, 11, 10, 6, % move 2 (around 7) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To) ?=> M=2, To=[M1,M6,M2,M3,M5,M10,M7,M4,M9,M11,M12,M8,M13,M14,M15,M16]. % 5, 6, 7, 11, 15, 14, 13, 9, % move 3 (around 10) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To) ?=> M=3, To=[M1,M2,M3,M4,M9,M5,M6,M8,M13,M10,M7,M12,M14,M15,M11,M16]. % 6, 7, 8, 12, 16, 15, 14, 10, % move 4 (around 11) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To) => M=4, To=[M1,M2,M3,M4,M5,M10,M6,M7,M9,M14,M11,M8,M13,M15,M16,M12]. % % For bplan.plan2/3 % % table % 1, 2, 3, 7, 11, 10, 9, 5, % move 1 (around 6) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To, Cost) ?=> M=1, To=[M5,M1,M2,M4,M9,M6,M3,M8,M10,M11,M7,M12,M13,M14,M15,M16], Cost=1. % 2, 3, 4, 8, 12, 11, 10, 6, % move 2 (around 7) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To,Cost) ?=> M=2, To=[M1,M6,M2,M3,M5,M10,M7,M4,M9,M11,M12,M8,M13,M14,M15,M16],Cost=1. % 5, 6, 7, 11, 15, 14, 13, 9, % move 3 (around 10) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To,Cost) ?=> M=3, To=[M1,M2,M3,M4,M9,M5,M6,M8,M13,M10,M7,M12,M14,M15,M11,M16],Cost=1. % 6, 7, 8, 12, 16, 15, 14, 10, % move 4 (around 11) legal_move([M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12,M13,M14,M15,M16],M, To,Cost) => M=4, To=[M1,M2,M3,M4,M5,M10,M6,M7,M9,M14,M11,M8,M13,M15,M16,M12], Cost=1. % % CP approach % go_cp => % One 1-rotation: % Init = [2,3,7,4,1,6,11,8,5,9,10,12,13,14,15,16], % 2,1 % Init = [2,7,4,8,1,3,11,12,5,6,9,10,13,14,15,16], % 1,2,1 % Init = [7,4,11,8,2,3,9,12,1,5,6,10,13,14,15,16], % 1,2,3 % Init = [3,4,11,8,1,2,10,12,6,5,7,15,9,13,14,16], % 1,2,3,2,2,3 % Init = [8,12,7,15,1,4,2,10,3,6,11,14,5,9,13,16 ], % 4,4,4,1,2,3,2,2,3 Init = [8,12,7,15,1,14,16,13,3,10,11,9,5,2,4,6 ], % Random puzzle % Init = [2,4,16,11,15,7,12,1,8,9,14,3,10,5,13,6], % swap 15<->16 (GAP says 53 moves,but that's probably not optimal ) % Init = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,16,15 ], rotation_cp(Init, Moves), writeln(Moves), nl. % The permutation from A <-> B using the permutation P permutation3(A,P,B) => foreach(I in 1..A.length) % B[I] #= A[P[I]] PI #= P[I], BI #= B[I], element(PI, A, BI) end. % CP approach % % Using indomain(Len) find the shortest solution. % rotation_cp(Init, Moves) => N = 16, Len :: 2..100, indomain(Len), writeln(len=Len), Moves = new_list(Len-1), Moves :: 1..4, X = new_array(Len, N), X :: 1..N, % The valid moves Permutations = [ [5,1,2,4,9,6,3,8,10,11,7,12,13,14,15,16], % move 1 [1,6,2,3,5,10,7,4,9,11,12,8,13,14,15,16], % move 2 [1,2,3,4,9,5,6,8,13,10,7,12,14,15,11,16], % move 3 [1,2,3,4,5,10,6,7,9,14,11,8,13,15,16,12] % move 4 ], % init foreach(J in 1..N) X[1,J] #= Init[J] end, % the moves foreach(Move in 2..Len) all_different([X[Move,J] : J in 1..N]), permutation3([X[Move-1,J] : J in 1..N], [P : J in 1..N, matrix_element(Permutations, Moves[Move-1],J,P)], [X[Move,J] : J in 1..N]) end, % the goal foreach(J in 1..N) X[Len,J] #= J end, Vars = Moves ++ X.to_list(), solve([split], Vars), foreach(Row in X) writeln(Row.to_list()) end, writeln(moves=Moves), nl. % matrix_element(X, I, J, Val) => % nth(I, X, Row), % element(J, Row, Val). %matrix_element(X, I, J, Val) => % element(I, X, Row), % nth(J, Row, Val). %matrix_element(X, I, J, Val) => % nth(I, X, Row), % nth(J, Row, Val). %matrix_element(X, I, J, Val) => % freeze(I, (nth(I, X, Row),freeze(J,nth(J,Row,Val)))). matrix_element(X, I, J, Val) => freeze(I, (element(I, X, Row),freeze(J,element(J,Row,Val)))). % matrix_element(X, I, J, Val) => % freeze(I, (element(I, X, Row),freeze(J,nth(J,Row,Val)))).