/* Frog circle in Picat. From https://www.cantorsparadise.com/flex-your-problem-solving-skills-with-this-viral-math-puzzle-cad27f6bffef """ Cards numbered 1 to 12 are arranged in a circle. A frog jumps on card 1, then jumps to the card 1 place clockwise around the circle. Then, from card k, he jumps directly to the card k places clockwise around the circle. The frog continues jumping in this way forever. Find an arrangement of cards that allows the frog to jump on every card. ... This problem appeared (with a slightly different context) in the "2021 Pan-American Girls Mathematical Olympiad" https://artofproblemsolving.com/community/c2499895_2021_panamerican_girls_mathematical_olympiad """ For N = 12 there are 382 solutions: Here are some solutions with nice symmetries: x = [1,2,3,4,5,6,12,7,8,9,10,11] pos = [1,2,4,8,3,6,12,11,9,5,10,7] visited = [1,2,4,7,3,6,11,10,8,5,9,12] 1 11 2 10 3 9 4 8 5 7 6 12 x = [1,10,8,6,4,2,12,11,9,7,5,3] pos = [1,2,12,3,11,4,10,5,9,6,8,7] visited = [1,10,3,8,5,6,7,4,9,2,11,12] 1 3 10 5 8 7 6 9 4 11 2 12 The second solution is also the imperative version in frog_circle2(N,X). It is also the proposed solution for the puzzle in the article (op.cit). Note that 12 (in general N) must be the last visited card: when the frog reach the card with k=N then it loops in a cycle. Se go2/0 for couting the number of solutions: N #sols -------- 1 = 1 2 = 1 4 = 1 6 = 1 8 = 4 10 = 43 12 = 382 14 = 7582 16 = 195252 18 = 6524755 * Visiting in the order 1..N (Uncomment this line in frog_circle/2: % Visited #= 1..N, ) For some N the visited values are in exact order order 1..N: 1,2,4,8,16,32,64, 2^I Here is the (unique) solutions for N=16 and N=32 x = [1,2,12,3,9,7,4,11,16,15,5,14,8,10,13,6] pos = [1,2,4,7,11,16,6,13,5,14,8,3,15,12,10,9] visited = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 1 6 2 13 12 10 3 8 9 14 7 5 4 15 11 16 x = [1,2,12,3,9,26,4,22,17,15,5,19,25,10,13,6,32,31,21,30,24,7,29,11,16,18,28,14,8,23,20,27] pos = [1,2,4,7,11,16,22,29,5,14,24,3,15,28,10,25,9,26,12,31,19,8,30,21,13,6,32,27,23,20,18,17] visited = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32] 1 27 2 20 12 23 3 8 9 14 26 28 4 18 22 16 17 11 15 29 5 7 19 24 25 30 10 21 13 31 6 32 Which is not really a complex pattern: each value K is K steps (modulo N) apart from K-1. This model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. go ?=> nolog, N=12, println(n=N), frog_circle(N,X,Pos,Visited), println('x '=X), println('pos '=Pos), println(visited=Visited), print_clock(N,X), nl, fail. go => true. % % Number of solutions for N=1..18, (1 or N even) % N #sols % ------- % 1 = 1 % 2 = 1 % 4 = 1 % 6 = 1 % 8 = 4 % 10 = 43 % 12 = 382 % 14 = 7582 % 16 = 195252 % 18 = 6524755 % go2 ?=> nolog, foreach(N in 1..20,N mod 2 == 0) Count = count_all(frog_circle(N,_X,_Pos,_Visited)), println(N=Count) end, nl. go2 => true. /* "Imperative" solution using frog_circle2/2: x = [1,2] x = [1,2,4,3] x = [1,4,2,6,5,3] x = [1,6,4,2,8,7,5,3] x = [1,8,6,4,2,10,9,7,5,3] x = [1,10,8,6,4,2,12,11,9,7,5,3] x = [1,12,10,8,6,4,2,14,13,11,9,7,5,3] x = [1,14,12,10,8,6,4,2,16,15,13,11,9,7,5,3] x = [1,16,14,12,10,8,6,4,2,18,17,15,13,11,9,7,5,3] x = [1,18,16,14,12,10,8,6,4,2,20,19,17,15,13,11,9,7,5,3] x = [1,20,18,16,14,12,10,8,6,4,2,22,21,19,17,15,13,11,9,7,5,3] x = [1,22,20,18,16,14,12,10,8,6,4,2,24,23,21,19,17,15,13,11,9,7,5,3] x = [1,24,22,20,18,16,14,12,10,8,6,4,2,26,25,23,21,19,17,15,13,11,9,7,5,3] x = [1,26,24,22,20,18,16,14,12,10,8,6,4,2,28,27,25,23,21,19,17,15,13,11,9,7,5,3] x = [1,28,26,24,22,20,18,16,14,12,10,8,6,4,2,30,29,27,25,23,21,19,17,15,13,11,9,7,5,3] */ go3 ?=> member(N,1..30), N mod 2 == 0, println(n=N), frog_circle2(N,X), println(x=X), print_clock(N,X), get_visited(N,X,Visited), all_different(Visited), % Check the solution println(visited=Visited), println(N=ok), nl, fail, nl. go3 => true. % % Print the clock (in a stylistic form :-)) % print_clock(N,X) => printf(" %2d\n",X[1]), foreach(I in 2..(N) div 2) printf(" %2d %2d\n",X[N-I+2], X[I]) end, printf(" %2d\n",X[1+N div 2]), nl. % % Order of the visited values % get_visited(N,X,Visited) => XV = 1, Visited1 = [XV], PosV = 1, foreach(_ in 2..N) PosV := 1+(PosV + XV-1) mod N, XV := X[PosV], Visited1 := Visited1 ++ [XV] end, Visited = Visited1. % % Solve the Frog Circle puzzle (CP). % frog_circle(N,X,Pos,Visited) => % Values of the "clock" X = new_list(N), X :: 1..N, % Position of the I'th jump Pos = new_list(N), Pos :: 1..N, % Order of the visited cards Visited = new_list(N), Visited :: 1..N, all_different(X), all_different(Pos), all_different(Visited), X[1] #= 1, Pos[1] #= 1, Visited[1] #= 1, foreach(I in 2..N) %% T = X[Pos[I-1]] element(Pos[I-1],X,T), Pos[I] #= 1+(Pos[I-1]+T-1) mod N, % Tweaking for modulo %% Visited[I] = X[Pos[I]] element(Pos[I],X,Visited[I]) end, % Redundant constraints for fixing the value N % (speed up the solve time a little). % The last visited must be N since after that we are % going in an infinite cycle... Visited[N] #= N, % % The position for N is N+1 at "6 o'clock" for N=12 Pos[N] #= (N div 2) + 1, X[1 + N div 2 ] #= N, % Visited #= 1..N, % increasing(Visited), % much slower %% Test of a simple symmetry breaking (cf frog_circle2/2). % X[1] + X[1+N div 2] #= N+1, % foreach(I in 2..(N) div 2) % % X[N-I+2] #= 2*I-1, % This yield a unique solution. % X[I] #= N - X[N-I+2]+1 % end, Vars = X ++ Pos ++ Visited, solve($[ff,split],Vars). % % Solve Frog circle puzzle by algoritm ("imperative"): % % x = [1,10,8,6,4,2,12,11,9,7,5,3] % 1 % 3 10 % 5 8 % 7 6 % 9 4 % 11 2 % 12 % % Note that all "pairs" adds to 12+1 = 13 (in general = N+1) % 1 + 12 = 12 + 1 = 13 % 3 + 10 = 12 + 1 = 13 % 5 + 8 = 12 + 1 = 13 % 7 + 6 = 12 + 1 = 13 % 9 + 4 = 12 + 1 = 13 % 11 + 2 = 12 + 1 = 13 % frog_circle2(N,X) => X = new_list(N), X[1] := 1, % 1 is fixed X[1 + N div 2] := N, % 1 + N div 2 is fixed ("6 o'clock") foreach(I in 2..N div 2) X[N-I+2] := 2*I - 1, % N div 2+1..N: decreasing odd numbers X[I] := N - X[N-I+2] + 1 % 2..N div 2 : decreasing even numbers end.