/* N-Queens with reqions (with traditional n-queens constraints) in Picat. This is inspired by the Alireza Soroudi's post https://www.linkedin.com/pulse/queens-game-using-cp-alireza-soroudi-2hbke/ """ I recently came across a fascinating challenge on LinkedIn that caught my attention. It's a perfect example of the kind of problem that can be tackled using constraint programming. Let's explore how we can solve it with this powerful approach. Game rules: - Only one queen should be placed at each region - At most one queen can be placed on each row and column. - No two queens can touch each other (they can be on the same diagonal if they don't touch) """ (See queens_with_regions.pi for a model of this problem.) I misread the description first, and thought it was the "plain" n-queens problem with added regions, but it was not. Here's a way to model such a puzzle, i.e. the rules are: a) standard n-queens rules: no attacking queens in rows, columns, or diagonals b) there must be exactly one queen in each region. The method used is to incorporate the standard n_queens/2 constraint together with the constraints of the regions, see generate_regions/2 for details of the generation. For solving a specific instance, see queens_with_regions/2. The main goals: * go/0: Generate problem instances and solutions for a certain n * go2/0: Solve a specific instance * go3/0: Solve all the instances in problem/2. Here's an example Instance: 1 2 1 1 1 1 1 1 1 1 1 1 2 1 3 1 1 4 4 4 4 1 1 2 1 3 5 1 4 6 7 7 7 1 1 1 3 5 1 4 6 6 6 6 8 1 1 5 5 1 4 9 9 9 4 8 5 5 5 10 1 4 4 4 4 4 8 5 11 10 10 1 1 1 1 1 4 8 5 11 4 10 10 10 10 1 4 4 5 5 11 4 4 4 4 4 1 4 4 5 11 11 11 5 5 4 4 1 1 4 5 5 5 5 5 5 5 4 4 4 4 Solution: X = [2,4,9,11,8,5,3,1,7,10,6] 1 (2) 1 1 1 1 1 1 1 1 1 1 2 1 (3) 1 1 4 4 4 4 1 1 2 1 3 5 1 4 6 (7) 7 7 1 1 1 3 5 1 4 6 6 6 (6) 8 1 1 5 5 1 4 (9) 9 9 4 8 5 5 5 (10) 1 4 4 4 4 4 8 5 (11) 10 10 1 1 1 1 1 4 (8) 5 11 4 10 10 10 10 1 4 4 5 5 11 4 4 4 (4) 4 1 4 4 5 11 11 11 5 5 4 4 1 (1) 4 5 5 5 5 5 (5) 5 4 4 4 4 The list 'X' is the solution of the n_queens_01/2 constraint (reduced to a single list). X[I] should be interpreted as the I'th queen is placed in the X[I]'th column. For example X[3] = 9 means that for row 3 the queens is placed in column 9th columns, and is in the 7th region, which is indicated by "(7)". For N=4 there are 1932 solutions (it took about 5 minutes). I wrote about this at LinkedIn: https://www.linkedin.com/feed/update/urn:li:activity:7234621562195202049/ This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import sat. % The fastest to generate instances % import cp. % import mip. % import smt. main => go. % % Generate problem instances with solutions % go ?=> nolog, % Generate satisfiable problem instances N = 4, % N queens and N regions println(n=N), % Generate a problem instance generate_regions(N,Regions1,_X1), % Check that it is unique All = findall([Regions1,X],generate_regions(N,Regions1,X)), Len = All.len, if Len == 1 then % We've found a unique solution [Regions,X] = All.first, print_regions(Regions), printf("problem(x,%w).\n",Regions), print_solution(Regions,X), nl, nl, flush(stdout) end, fail, nl. go => true. /* Solve a specific problem Instance: 1 1 1 1 2 2 2 3 4 1 1 3 3 3 3 3 4 4 4 3 3 3 3 3 5 4 4 4 3 3 3 3 5 4 5 4 3 3 3 3 5 5 5 4 4 3 3 6 7 8 7 4 7 3 6 6 7 7 7 7 7 7 6 6 Solution: X = [6,3,7,4,1,8,2,5] 1 1 1 1 2 (2) 2 3 4 1 (1) 3 3 3 3 3 4 4 4 3 3 3 (3) 3 5 4 4 (4) 3 3 3 3 (5) 4 5 4 3 3 3 3 5 5 5 4 4 3 3 (6) 7 (8) 7 4 7 3 6 6 7 7 7 7 (7) 7 6 6 */ go2 => nolog, Regions = {{1,1,1,1,2,2,2,3}, {4,1,1,3,3,3,3,3}, {4,4,4,3,3,3,3,3}, {5,4,4,4,3,3,3,3}, {5,4,5,4,3,3,3,3}, {5,5,5,4,4,3,3,6}, {7,8,7,4,7,3,6,6}, {7,7,7,7,7,7,6,6}}, print_regions(Regions), if queens_with_regions(Regions,X) then print_solution(Regions, X) else println("No solution") end, fail, nl. % % Show all the problems in problem/2. % go3 ?=> nolog, garbage_collect(400_000_000), problem(N,Regions), nl, println(problem_instance=N), print_regions(Regions), queens_with_regions(Regions,X), print_solution(Regions,X), % All = findall(X,queens_with_regions(Regions,X)), % Len = All.len, % % Warn if it's not a unique solution % if Len == 1 then % print_solution(Regions, All.first) % else % printf("This instance has %d solutions!\n%w", All.len, All) % end, fail, nl. % % Solve the nqueens with requion problem. % Given: Regions % Solve: X (plain n-queen problem) % queens_with_regions(Regions,X) => N = Regions.len, % Traditional n-queens problem X = new_array(N,N), X :: 0..1, n_queens_01(N,X), % Ensure that it's exactly one queen in each region. foreach(R in 1..N) sum([X[I,J]*(Regions[I,J] #= R) : I in 1..N, J in 1..N]) #= 1 end, Vars = X.vars, solve($[ffc,split],Vars). % % Solve the standard N-queens problem % (represented as a 0/1 problem. % % (Defers the solving to the caller.) % n_queens_01(N,Q) => % Diagionals foreach (K in 1-N..N-1) % at most one sum([Q[I,J] : I in 1..N, J in 1..N, I-J==K]) #=< 1 end, foreach (K in 2..2*N) % at most one sum([Q[I,J] : I in 1..N, J in 1..N, I+J==K]) #=< 1 end, foreach (I in 1..N) % 1 in each row sum([Q[I,J] : J in 1..N]) #= 1 end, foreach (J in 1..N) % 1 in each column sum([Q[I,J] : I in 1..N]) #= 1 end. % % Generate a solvable problem instance. % Note that it might be more than one possible solution, % so this have to be checked by the caller. % generate_regions(N, Regions, X) => % The N scc grids for each region Grids = new_array(N, N,N), Grids :: 0..1, % Each cell in the regions must be filled, % i.e. the total number of 1s in Grids is N*N. sum(Grids.vars) #= N*N, % For the traditional nqueens problem X = new_array(N,N), X :: 0..1, n_queens_01(N,X), % To which regions does a cell belongs to. Regions = new_array(N,N), Regions :: 1..N, % Ensure that the 1s in Grid[K] are connected. foreach(K in 1..N) GK = Grids[K], sum(GK.vars) #>= 3, % each region should be at least 3 cells % sum(GK.vars) #>= 5, % each region should be at least 5 cells scc_grid(GK) end, % Each Grid constiture a unique region, i.e. there are no overlap foreach(I in 1..N, J in 1..N) sum([Grids[G,I,J] : G in 1..N]) #= 1 end, % Connect the K'th grid to the K'th region foreach(K in 1..N) foreach(I in 1..N) foreach(J in 1..N) Grids[K,I,J] #= 1 #=> Regions[I,J] #= K end end end, % Symmetry breaking: Ensure that the start % of each regions is in proper order. value_precede_chain(1..N,Regions.vars), % Ensure that it's exactly one queen in a region foreach(R in 1..N) sum([X[I,J]*(Regions[I,J] #= R) : I in 1..N, J in 1..N]) #= 1 end, Vars = X.vars ++ Grids.vars ++ Regions.vars, solve($[seq],Vars). % % The global constraint % value_precede_chain(C, X) % ensures that the value C[I-1] precedes the value C[I] in the array X % if both C[I-1] and C[I] are in X. % I.e. it ensures that the first occurrences of the numbers in C are in order. % value_precede_chain(C, X) => foreach(I in 2..C.length) value_precede(C[I-1], C[I], X) end. % % The global constraint % value_precede(S,T, X) % ensures that the value S precedes the value T in array X % if both S and T are in X. % % This definition is inspired by % MiniZinc definition value_precede_int.mzn % value_precede(S,T,X) => XLen = X.length, B = new_list(XLen+1), B :: 0..1, foreach(I in 1..XLen) % Xis :: 0..1, Xis #= (X[I] #= S), (Xis #=> (B[I+1] #= 1)) #/\ ((#~ Xis #= 1) #=> (B[I] #= B[I+1])) #/\ ((#~ B[I] #= 1) #=> (X[I] #!= T)) end, B[1] #= 0. % % Pretty print the regions % print_regions(Regions) => println("Instance:"), N = Regions.len, foreach(I in 1..N) foreach(J in 1..N) printf("%5w", Regions[I,J]) end, nl end, % Number of cells in each region nl, println(num_cells_in_region=[R=C : R in 1..N, C=sum([1 : I in 1..N, J in 1..N, Regions[I,J] == R])]), nl. % % Pretty print the solution % print_solution(Regions,X) => println("Solution:"), N = Regions.len, println('X'=[J : I in 1..N, J in 1..N, X[I,J] == 1]), foreach(I in 1..N) foreach(J in 1..N) if X[I,J] == 1 then printf("%5w","(" ++ Regions[I,J].to_string ++ ")") else printf("%5w",Regions[I,J]) end end, nl end, nl. /* The (generated) instances Here are some of the solutions: problem_instance = 1 Instance: 1 1 1 1 1 1 1 1 1 2 2 2 3 3 3 3 1 4 2 2 2 2 3 3 1 4 4 4 2 2 2 2 1 1 4 4 4 4 5 2 6 1 1 1 4 4 5 2 6 7 1 1 8 8 5 5 6 7 7 1 8 8 8 5 Solution: X = [5,3,8,4,7,1,6,2] 1 1 1 1 (1) 1 1 1 1 2 (2) 2 3 3 3 3 1 4 2 2 2 2 3 (3) 1 4 4 (4) 2 2 2 2 1 1 4 4 4 4 (5) 2 (6) 1 1 1 4 4 5 2 6 7 1 1 8 (8) 5 5 6 (7) 7 1 8 8 8 5 problem_instance = 11 Instance: 1 1 2 2 2 2 2 2 2 1 3 3 3 2 2 2 2 2 1 4 4 4 4 2 2 4 4 5 5 5 5 4 4 4 4 4 6 6 6 5 5 6 6 6 4 6 7 6 6 6 6 6 6 4 6 7 8 8 8 6 6 4 4 7 7 9 9 8 8 4 4 4 7 7 9 9 9 9 4 4 4 Solution: X = [1,4,7,3,8,2,5,9,6] (1) 1 2 2 2 2 2 2 2 1 3 3 (3) 2 2 2 2 2 1 4 4 4 4 2 (2) 4 4 5 5 (5) 5 4 4 4 4 4 6 6 6 5 5 6 6 (6) 4 6 (7) 6 6 6 6 6 6 4 6 7 8 8 (8) 6 6 4 4 7 7 9 9 8 8 4 4 (4) 7 7 9 9 9 (9) 4 4 4 problem_instance = 21 Instance: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 1 3 1 1 1 1 1 1 3 3 3 3 1 4 4 4 1 1 5 5 5 3 3 6 6 7 1 8 5 3 3 3 3 6 3 7 8 8 5 3 3 6 3 6 3 7 5 5 5 5 3 6 6 6 3 7 9 9 5 5 3 6 3 3 3 3 9 10 3 3 3 6 3 3 3 3 10 10 10 3 3 3 3 3 3 3 Solution: X = [7,4,8,5,9,1,10,2,6,3] 1 1 1 1 1 1 (1) 1 1 1 1 2 2 (2) 1 3 1 1 1 1 1 1 3 3 3 3 1 (4) 4 4 1 1 5 5 (5) 3 3 6 6 7 1 8 5 3 3 3 3 6 (3) 7 (8) 8 5 3 3 6 3 6 3 7 5 5 5 5 3 6 6 6 3 (7) 9 (9) 5 5 3 6 3 3 3 3 9 10 3 3 3 (6) 3 3 3 3 10 10 (10) 3 3 3 3 3 3 3 problem_instance = 31 Instance: 1 2 1 1 1 1 1 1 1 1 1 1 2 1 3 1 1 4 4 4 4 1 1 2 1 3 5 1 4 6 7 7 7 1 1 1 3 5 1 4 6 6 6 6 8 1 1 5 5 1 4 9 9 9 4 8 5 5 5 10 1 4 4 4 4 4 8 5 11 10 10 1 1 1 1 1 4 8 5 11 4 10 10 10 10 1 4 4 5 5 11 4 4 4 4 4 1 4 4 5 11 11 11 5 5 4 4 1 1 4 5 5 5 5 5 5 5 4 4 4 4 Solution: X = [2,4,9,11,8,5,3,1,7,10,6] 1 (2) 1 1 1 1 1 1 1 1 1 1 2 1 (3) 1 1 4 4 4 4 1 1 2 1 3 5 1 4 6 (7) 7 7 1 1 1 3 5 1 4 6 6 6 (6) 8 1 1 5 5 1 4 (9) 9 9 4 8 5 5 5 (10) 1 4 4 4 4 4 8 5 (11) 10 10 1 1 1 1 1 4 (8) 5 11 4 10 10 10 10 1 4 4 5 5 11 4 4 4 (4) 4 1 4 4 5 11 11 11 5 5 4 4 1 (1) 4 5 5 5 5 5 (5) 5 4 4 4 4 problem_instance = 41 Instance: 1 2 2 3 3 3 1 1 1 1 1 1 1 1 2 2 2 2 2 1 4 4 4 1 1 1 1 1 1 1 1 1 1 1 4 1 5 6 6 1 7 8 8 8 8 8 4 1 5 5 6 1 7 7 7 7 8 8 4 1 6 6 6 1 1 1 1 7 8 9 4 1 6 10 10 10 10 1 1 7 8 9 4 1 6 11 11 11 11 11 11 7 9 9 4 1 6 6 11 7 11 11 11 7 7 7 4 1 6 7 7 7 11 7 7 7 12 7 4 1 6 7 7 7 7 7 7 12 12 12 4 1 6 6 6 6 6 7 7 12 12 4 4 4 Solution: X = [4,7,12,6,1,10,5,3,9,11,8,2] 1 2 2 (3) 3 3 1 1 1 1 1 1 1 1 2 2 2 2 (2) 1 4 4 4 1 1 1 1 1 1 1 1 1 1 1 4 (1) 5 6 6 1 7 (8) 8 8 8 8 4 1 (5) 5 6 1 7 7 7 7 8 8 4 1 6 6 6 1 1 1 1 7 8 (9) 4 1 6 10 10 10 (10) 1 1 7 8 9 4 1 6 11 (11) 11 11 11 11 7 9 9 4 1 6 6 11 7 11 11 11 7 (7) 7 4 1 6 7 7 7 11 7 7 7 12 7 (4) 1 6 7 7 7 7 7 7 (12) 12 12 4 1 6 (6) 6 6 6 7 7 12 12 4 4 4 problem_instance = 51 Instance: 1 2 2 3 3 3 4 4 4 4 4 4 4 1 2 3 3 4 4 4 4 5 5 5 5 5 1 2 3 4 4 5 5 5 5 5 5 6 5 1 1 3 4 4 5 5 5 6 6 6 6 5 1 1 3 4 4 5 5 5 7 7 7 6 5 8 1 3 4 4 5 5 5 5 5 5 5 9 8 1 3 3 3 5 5 10 10 10 10 5 9 8 1 1 11 3 5 5 10 10 10 10 5 9 8 1 11 11 3 3 5 5 5 5 5 5 9 8 1 1 1 12 13 13 13 5 5 5 5 9 8 1 8 12 12 13 13 8 8 5 5 5 9 8 1 8 12 12 13 8 8 8 5 5 5 5 8 8 8 8 8 8 8 8 8 5 5 5 5 num_cells_in_region = [1 = 17,2 = 4,3 = 15,4 = 19,5 = 54,6 = 6,7 = 3,8 = 23,9 = 6,10 = 8,11 = 3,12 = 5,13 = 6] Solution: X = [1,6,2,12,10,7,4,11,3,8,13,5,9] (1) 2 2 3 3 3 4 4 4 4 4 4 4 1 2 3 3 4 (4) 4 4 5 5 5 5 5 1 (2) 3 4 4 5 5 5 5 5 5 6 5 1 1 3 4 4 5 5 5 6 6 6 (6) 5 1 1 3 4 4 5 5 5 7 (7) 7 6 5 8 1 3 4 4 5 (5) 5 5 5 5 5 9 8 1 3 (3) 3 5 5 10 10 10 10 5 9 8 1 1 11 3 5 5 10 10 10 (10) 5 9 8 1 (11) 11 3 3 5 5 5 5 5 5 9 8 1 1 1 12 13 13 (13) 5 5 5 5 9 8 1 8 12 12 13 13 8 8 5 5 5 (9) 8 1 8 12 (12) 13 8 8 8 5 5 5 5 8 8 8 8 8 8 8 8 (8) 5 5 5 5 */ % N = 8 problem(1,{{1,1,1,1,1,1,1,1},{1,2,2,2,3,3,3,3},{1,4,2,2,2,2,3,3},{1,4,4,4,2,2,2,2},{1,1,4,4,4,4,5,2},{6,1,1,1,4,4,5,2},{6,7,1,1,8,8,5,5},{6,7,7,1,8,8,8,5}}). problem(2,{{1,1,1,1,2,3,3,3},{1,2,2,2,2,2,4,3},{2,2,2,2,5,4,4,3},{2,6,2,5,5,7,7,3},{6,6,2,2,2,7,3,3},{2,2,2,2,2,2,3,3},{2,2,8,8,8,8,8,3},{8,8,8,8,8,3,3,3}}). problem(3,{{1,2,2,2,2,1,1,1},{1,1,1,1,1,1,1,1},{3,1,1,4,5,5,5,5},{3,3,4,4,6,6,5,5},{3,7,7,7,6,3,3,5},{3,3,7,7,6,3,3,3},{3,3,3,6,6,3,8,3},{3,3,3,3,3,3,8,8}}). problem(4,{{1,1,1,1,2,3,3,3},{1,1,1,1,2,2,2,4},{1,5,5,1,2,2,2,4},{1,6,5,1,2,2,4,4},{6,6,1,1,4,4,4,4},{7,1,1,4,8,8,8,4},{7,1,1,4,4,4,4,4},{7,7,7,7,7,7,4,4}}). problem(5,{{1,2,2,2,2,3,4,5},{1,1,2,6,3,3,4,5},{7,1,2,6,6,4,4,5},{7,1,2,2,2,4,4,5},{7,1,1,1,2,2,4,5},{7,2,2,2,2,2,4,5},{7,8,8,8,2,4,4,5},{2,2,2,2,2,2,2,5}}). problem(6,{{1,2,2,3,4,5,5,5},{1,2,3,3,4,4,4,5},{1,6,3,3,4,7,8,5},{1,6,3,3,7,7,8,5},{6,6,3,3,3,7,8,5},{6,3,3,3,7,7,3,5},{6,6,6,3,7,7,3,5},{6,6,6,3,3,3,3,3}}). problem(7,{{1,1,2,2,2,2,2,2},{3,1,2,1,1,1,1,2},{3,1,1,1,1,4,1,1},{3,1,1,1,1,4,1,1},{1,1,5,5,5,4,6,1},{1,1,1,1,5,5,6,6},{7,8,8,8,5,5,6,6},{7,7,7,7,7,7,7,6}}). problem(8,{{1,1,1,1,1,2,2,3},{1,4,4,4,4,4,2,3},{1,1,4,4,5,4,3,3},{5,5,4,4,5,4,3,3},{5,5,4,4,5,4,4,6},{5,5,5,5,5,5,4,6},{5,7,8,5,5,5,4,6},{7,7,8,8,5,5,4,4}}). problem(9,{{1,1,1,2,3,3,4,5},{1,1,2,2,3,3,4,5},{3,3,3,2,3,4,4,5},{3,5,3,3,3,4,4,5},{3,5,6,6,6,6,4,5},{3,5,6,6,5,5,5,5},{7,5,5,5,5,5,5,5},{7,7,8,8,8,8,5,5}}). problem(10,{{1,1,1,1,2,2,2,2},{1,3,1,1,2,2,2,2},{3,3,1,1,2,2,2,2},{4,5,1,1,1,2,6,6},{4,5,5,5,1,2,6,2},{4,4,1,1,1,2,2,2},{7,7,1,1,1,8,8,2},{7,7,7,7,7,8,2,2}}). % N = 9 problem(11,{{1,1,2,2,2,2,2,2,2},{1,3,3,3,2,2,2,2,2},{1,4,4,4,4,2,2,4,4},{5,5,5,5,4,4,4,4,4},{6,6,6,5,5,6,6,6,4},{6,7,6,6,6,6,6,6,4},{6,7,8,8,8,6,6,4,4},{7,7,9,9,8,8,4,4,4},{7,7,9,9,9,9,4,4,4}}). problem(12,{{1,2,2,2,2,2,3,3,3},{1,4,4,4,4,3,3,4,4},{1,1,1,5,4,3,4,4,4},{5,5,1,5,4,4,4,4,4},{6,5,5,5,5,4,4,4,4},{6,6,7,7,5,4,4,4,8},{4,4,4,7,5,4,9,9,8},{4,4,4,4,4,4,9,9,8},{4,4,4,4,4,4,9,8,8}}). problem(13,{{1,1,2,2,3,3,3,3,3},{1,1,1,2,2,2,4,4,4},{1,1,1,5,5,2,2,6,6},{1,1,1,5,5,5,2,2,6},{1,2,2,5,5,5,5,2,2},{1,2,2,2,2,2,2,2,2},{1,1,7,7,7,8,9,2,2},{7,7,7,8,8,8,9,2,2},{7,7,8,8,8,8,9,9,9}}). problem(14,{{1,1,1,2,2,2,3,3,3},{1,4,4,4,2,3,3,5,3},{1,4,6,6,2,5,3,5,5},{1,4,6,2,2,5,5,5,5},{1,2,2,2,2,5,7,5,5},{1,2,8,8,2,9,7,7,7},{2,8,8,2,2,9,9,9,7},{2,2,2,2,2,2,2,9,9},{2,2,2,2,9,9,9,9,9}}). problem(15,{{1,1,2,2,2,2,2,2,2},{1,1,2,2,3,4,4,4,2},{5,5,5,3,3,2,2,2,2},{3,3,3,3,2,2,2,3,3},{3,3,3,6,2,2,2,3,3},{3,3,3,6,6,3,3,3,3},{7,8,3,3,3,3,9,9,3},{7,8,8,8,8,8,9,3,3},{7,7,7,7,7,8,8,8,3}}). problem(16,{{1,1,1,1,1,1,1,1,2},{1,3,3,3,3,1,1,2,2},{4,4,1,1,1,1,1,1,2},{4,5,5,1,6,6,6,6,2},{6,6,5,5,7,7,7,6,6},{6,6,6,5,5,5,5,6,6},{6,6,6,6,6,6,5,6,8},{6,6,9,9,8,6,6,6,8},{6,6,6,9,8,8,8,8,8}}). problem(17,{{1,1,1,1,1,2,2,2,2},{3,3,3,3,3,2,4,4,2},{3,5,3,3,6,4,4,2,2},{3,5,7,6,6,2,2,2,8},{5,5,7,6,2,2,2,8,8},{5,5,7,7,2,2,2,2,2},{5,9,9,7,7,2,2,2,2},{9,9,9,9,7,7,7,2,9},{9,9,9,9,9,9,9,9,9}}). problem(18,{{1,1,1,1,1,1,1,1,1},{1,1,2,3,1,1,4,4,4},{2,2,2,3,5,5,5,2,2},{6,2,2,3,3,3,7,7,2},{6,2,2,3,8,3,3,7,2},{6,2,2,8,8,3,3,2,2},{2,2,2,2,2,3,2,2,9},{2,2,2,2,2,2,2,2,9},{2,2,2,2,2,2,2,2,9}}). problem(19,{{1,1,2,2,2,2,2,3,3},{1,4,4,4,4,2,5,3,6},{4,4,4,4,4,4,5,3,6},{4,7,7,8,8,4,5,3,6},{4,7,7,8,9,9,5,3,6},{4,7,8,8,8,9,5,3,3},{4,7,7,8,8,9,5,3,3},{4,4,7,7,7,9,9,9,3},{4,4,4,7,7,3,3,3,3}}). problem(20,{{1,1,1,1,1,1,1,1,1},{1,1,1,1,2,1,1,1,1},{1,3,3,4,2,2,1,1,1},{5,3,4,4,2,2,2,1,6},{5,4,4,7,8,8,8,6,6},{5,4,9,7,7,7,7,7,7},{5,4,9,7,7,4,4,4,7},{5,4,9,7,7,4,4,7,7},{5,4,4,4,4,4,4,7,7}}). % N = 10 problem(21,{{1,1,1,1,1,1,1,1,1,1},{1,2,2,2,1,3,1,1,1,1},{1,1,3,3,3,3,1,4,4,4},{1,1,5,5,5,3,3,6,6,7},{1,8,5,3,3,3,3,6,3,7},{8,8,5,3,3,6,3,6,3,7},{5,5,5,5,3,6,6,6,3,7},{9,9,5,5,3,6,3,3,3,3},{9,10,3,3,3,6,3,3,3,3},{10,10,10,3,3,3,3,3,3,3}}). problem(22,{{1,1,1,1,1,1,2,2,3,3},{4,4,1,4,2,2,2,2,3,3},{5,4,4,4,2,6,6,6,3,3},{5,5,5,5,2,2,2,2,3,3},{5,5,5,2,2,7,7,2,3,3},{8,5,5,8,7,7,2,2,3,3},{8,8,8,8,7,7,2,9,9,9},{8,8,8,2,2,7,2,2,2,2},{2,2,2,2,2,2,2,2,2,2},{2,2,2,10,10,10,2,2,2,2}}). problem(23,{{1,1,1,2,2,2,1,1,1,1},{1,1,3,3,1,1,1,1,1,1},{1,1,3,1,1,1,4,4,1,1},{1,1,1,1,1,5,4,1,1,1},{1,6,6,6,1,5,4,1,1,1},{1,1,1,1,1,5,4,4,7,1},{8,1,1,1,7,7,7,7,7,7},{8,1,1,1,7,7,7,7,7,7},{8,8,1,1,7,7,9,7,7,10},{8,8,1,1,1,1,9,9,10,10}}). problem(24,{{1,1,1,2,2,2,2,2,2,2},{1,1,2,2,3,2,2,2,2,4},{5,1,2,2,3,2,6,2,7,4},{5,5,5,5,3,2,6,2,7,4},{8,8,5,6,3,3,6,2,7,4},{8,5,5,6,6,6,6,2,7,4},{8,5,5,6,9,9,2,2,4,4},{2,2,2,6,9,9,2,4,4,4},{2,2,2,2,9,2,2,10,4,4},{2,2,2,2,2,2,10,10,4,4}}). problem(25,{{1,2,2,2,1,1,1,1,1,1},{1,1,1,1,1,3,3,1,4,4},{5,1,1,1,3,3,3,1,4,6},{5,5,5,7,7,3,3,1,6,6},{8,3,3,3,7,3,3,1,6,6},{8,3,9,3,3,3,3,1,6,6},{8,1,9,9,9,9,9,1,6,6},{8,1,1,1,1,1,1,1,6,6},{8,8,1,6,6,6,10,10,10,6},{8,8,8,8,6,6,6,6,6,6}}). problem(26,{{1,1,1,2,2,2,2,1,3,3},{1,4,1,1,1,1,1,1,3,5},{1,4,3,3,3,3,1,3,3,5},{6,4,3,7,7,3,3,3,5,5},{6,4,3,7,7,7,8,8,8,8},{6,3,3,3,3,7,9,9,10,8},{6,3,7,7,7,7,7,9,10,8},{6,3,8,8,8,8,7,7,10,8},{3,3,8,8,8,8,8,8,10,8},{3,3,3,3,3,3,3,8,8,8}}). problem(27,{{1,1,1,1,1,1,1,1,1,2},{1,1,1,3,3,4,4,4,1,2},{1,5,3,3,4,4,4,6,1,2},{1,5,5,3,4,7,7,6,1,2},{1,1,5,5,5,7,6,6,1,2},{1,1,5,6,6,6,6,1,1,1},{1,1,1,6,1,1,8,8,8,1},{1,9,9,6,6,1,1,1,1,1},{1,1,9,6,6,1,1,10,10,1},{1,1,6,6,6,1,1,10,1,1}}). problem(28,{{1,1,1,1,1,1,1,1,1,1},{1,1,2,1,1,1,1,1,1,1},{3,3,2,2,1,1,1,1,3,3},{4,3,3,3,5,5,5,5,3,3},{4,4,3,3,3,3,3,3,3,3},{3,3,3,3,6,6,6,6,6,6},{3,7,7,7,8,8,6,6,6,9},{3,3,7,7,8,3,3,3,9,9},{3,3,7,3,3,3,9,9,9,9},{3,3,3,3,10,10,10,10,10,10}}). problem(29,{{1,1,1,2,2,2,2,2,2,2},{3,1,4,4,4,5,5,5,6,2},{3,1,4,4,4,4,4,5,6,2},{3,1,4,4,5,5,5,5,6,2},{4,1,4,4,5,5,2,2,2,2},{4,4,4,4,5,5,2,7,2,2},{4,4,4,4,5,5,8,7,7,2},{4,4,9,5,5,5,8,2,2,2},{4,4,9,5,5,5,8,8,10,10},{4,4,9,5,5,8,8,8,8,10}}). problem(30,{{1,1,2,2,2,2,2,2,3,3},{4,1,2,5,5,2,6,6,3,3},{4,1,1,1,5,5,5,6,6,3},{4,6,6,5,5,5,5,5,6,3},{6,6,6,6,6,6,6,5,6,3},{6,6,6,7,7,7,6,6,6,3},{6,6,8,8,6,6,6,6,3,3},{6,6,6,8,6,6,6,6,9,3},{10,10,6,6,6,6,6,6,9,3},{10,6,6,6,6,6,6,6,9,3}}). % N = 11 problem(31,{{1,2,1,1,1,1,1,1,1,1,1},{1,2,1,3,1,1,4,4,4,4,1},{1,2,1,3,5,1,4,6,7,7,7},{1,1,1,3,5,1,4,6,6,6,6},{8,1,1,5,5,1,4,9,9,9,4},{8,5,5,5,10,1,4,4,4,4,4},{8,5,11,10,10,1,1,1,1,1,4},{8,5,11,4,10,10,10,10,1,4,4},{5,5,11,4,4,4,4,4,1,4,4},{5,11,11,11,5,5,4,4,1,1,4},{5,5,5,5,5,5,5,4,4,4,4}}). problem(32,{{1,1,1,1,1,1,1,1,2,1,1},{1,3,3,3,3,1,1,1,2,2,1},{1,1,1,1,3,1,1,1,1,1,1},{1,4,4,1,1,1,1,1,5,1,1},{1,4,1,1,6,5,5,5,5,5,1},{1,7,7,7,6,5,6,8,8,8,8},{9,9,9,7,6,5,6,8,8,8,8},{9,7,7,7,6,6,6,8,8,10,8},{9,7,7,7,7,7,6,7,8,10,8},{7,7,7,11,11,7,6,7,8,10,8},{7,11,11,11,11,7,7,7,8,8,8}}). problem(33,{{1,1,1,1,2,3,3,3,3,3,3},{4,1,2,2,2,2,2,2,3,5,3},{4,4,4,4,2,3,2,2,3,5,5},{4,6,6,4,2,3,2,3,3,3,5},{4,6,6,4,4,3,3,3,5,5,5},{6,6,3,3,3,3,3,5,5,7,7},{6,6,3,8,3,3,9,5,5,7,7},{6,6,8,8,3,10,9,5,5,7,6},{11,6,6,10,10,10,9,5,7,7,6},{11,11,6,10,10,10,9,9,9,9,6},{11,11,6,6,6,6,6,6,6,6,6}}). problem(34,{{1,1,1,2,2,1,1,1,1,1,1},{3,1,2,2,2,1,4,4,4,4,1},{3,1,1,1,1,1,5,5,4,4,1},{3,1,3,5,5,5,5,4,4,1,1},{3,3,3,5,4,4,4,4,6,1,1},{3,7,3,4,4,6,6,6,6,1,1},{8,7,7,4,4,6,6,6,6,1,1},{8,8,8,8,4,4,6,9,9,1,1},{10,10,8,8,4,4,6,9,6,1,11},{10,10,8,8,8,4,6,6,6,6,11},{10,8,8,8,8,8,6,6,6,6,11}}). problem(35,{{1,1,1,1,1,2,2,3,3,3,3},{1,1,2,2,2,2,3,3,4,4,3},{5,1,1,3,3,2,3,6,4,4,3},{5,5,1,3,3,3,3,6,6,4,3},{5,3,3,3,3,3,3,6,6,4,3},{5,3,5,5,5,3,3,6,7,4,3},{5,5,5,5,5,3,8,7,7,4,3},{9,10,10,10,5,8,8,7,7,4,3},{9,5,5,5,5,9,9,7,7,4,3},{9,9,9,9,9,9,9,4,4,4,11},{9,9,9,9,9,9,9,4,4,11,11}}). problem(36,{{1,1,2,2,2,1,3,3,3,4,4},{1,1,1,1,1,1,3,4,4,4,4},{1,1,5,3,3,3,3,4,4,4,4},{1,5,5,5,5,5,3,3,5,5,5},{1,5,5,5,5,5,5,5,5,5,5},{1,1,1,1,1,1,1,1,6,7,5},{8,8,8,8,8,6,6,1,6,7,7},{6,6,9,6,6,6,6,6,6,7,7},{6,6,9,6,6,10,10,6,6,7,7},{6,6,9,6,10,10,10,6,6,11,11},{6,6,6,6,6,6,6,6,6,11,11}}). problem(37,{{1,1,1,2,2,2,2,3,3,4,4},{1,1,2,2,5,5,5,3,4,4,4},{1,6,2,7,5,8,8,3,9,9,4},{1,6,2,7,5,8,10,3,9,9,9},{1,6,7,7,5,11,10,3,3,9,9},{1,6,7,5,5,11,10,3,3,3,3},{1,6,7,5,11,11,3,3,3,7,3},{1,6,7,5,11,3,3,3,3,7,7},{1,6,7,5,11,3,7,7,7,7,7},{6,6,7,5,5,3,3,7,7,7,7},{6,6,7,7,7,7,7,7,7,7,7}}). problem(38,{{1,1,2,2,2,2,2,2,2,2,2},{1,3,3,3,3,2,2,2,2,2,2},{3,3,3,3,3,3,2,2,4,5,5},{3,2,2,2,2,2,2,4,4,5,5},{3,2,6,7,7,2,2,8,8,5,5},{3,6,6,6,7,2,2,9,8,8,5},{3,6,10,6,2,2,9,9,9,8,5},{3,6,10,6,6,11,11,5,5,8,5},{3,3,10,6,6,11,11,5,5,5,5},{10,3,10,10,10,10,10,10,5,5,5},{10,10,10,10,10,10,10,10,5,5,5}}). problem(39,{{1,1,1,2,2,2,2,2,2,2,2},{1,1,1,3,3,3,3,1,1,2,2},{1,1,1,1,1,4,3,1,1,5,5},{1,1,1,1,4,4,1,1,1,1,5},{1,1,1,1,1,1,6,1,1,1,7},{1,1,1,1,1,1,6,1,1,1,7},{1,8,8,9,1,6,6,1,10,10,7},{1,1,8,9,1,6,6,1,11,10,10},{9,1,1,9,1,6,6,1,11,11,10},{9,9,9,9,1,1,1,1,1,11,10},{9,9,1,1,1,1,1,10,10,10,10}}). problem(40,{{1,1,1,1,2,3,3,3,3,3,3},{4,1,1,1,2,5,5,5,5,5,3},{4,6,6,7,2,5,5,5,5,5,3},{4,6,6,7,2,2,5,5,5,5,5},{4,6,7,7,7,2,2,5,5,5,5},{4,6,6,6,7,2,2,5,5,5,5},{4,4,4,6,6,2,2,8,5,5,5},{4,4,9,6,8,8,8,8,8,8,5},{4,10,9,6,6,6,6,6,11,11,5},{4,10,9,9,9,9,6,11,11,5,5},{4,10,10,10,10,10,10,10,10,5,5}}). % N = 12 problem(41,{{1,2,2,3,3,3,1,1,1,1,1,1},{1,1,2,2,2,2,2,1,4,4,4,1},{1,1,1,1,1,1,1,1,1,1,4,1},{5,6,6,1,7,8,8,8,8,8,4,1},{5,5,6,1,7,7,7,7,8,8,4,1},{6,6,6,1,1,1,1,7,8,9,4,1},{6,10,10,10,10,1,1,7,8,9,4,1},{6,11,11,11,11,11,11,7,9,9,4,1},{6,6,11,7,11,11,11,7,7,7,4,1},{6,7,7,7,11,7,7,7,12,7,4,1},{6,7,7,7,7,7,7,12,12,12,4,1},{6,6,6,6,6,7,7,12,12,4,4,4}}). problem(42,{{1,2,2,2,3,3,3,3,3,3,3,3},{1,2,2,2,2,4,5,5,5,3,3,3},{1,1,6,2,2,4,5,7,7,7,7,7},{1,6,6,2,2,4,5,5,8,8,2,2},{1,1,6,2,2,4,4,5,5,8,2,2},{1,6,6,6,2,2,2,5,5,2,2,2},{1,6,2,2,2,2,2,5,5,2,2,2},{1,6,6,9,2,2,5,5,5,2,2,2},{10,9,9,9,11,2,2,2,2,2,2,12},{10,10,9,9,11,11,10,10,10,10,12,12},{10,10,9,9,10,10,10,10,10,10,12,12},{10,10,10,10,10,10,10,10,10,10,10,12}}). problem(43,{{1,1,1,1,2,2,2,2,2,2,2,3},{2,2,2,2,2,4,4,4,5,5,2,3},{2,6,2,2,4,4,7,4,5,8,2,3},{2,6,6,2,7,7,7,4,9,8,10,3},{2,6,6,2,2,2,7,4,9,8,10,3},{2,2,6,9,2,11,4,4,9,8,10,3},{2,9,9,9,2,11,11,4,9,10,10,3},{2,2,9,9,2,2,11,4,9,10,3,3},{2,2,9,2,2,11,11,11,9,10,12,12},{2,9,9,2,2,2,11,9,9,10,10,12},{9,9,2,2,9,9,9,9,10,10,10,12},{9,9,9,9,9,10,10,10,10,10,12,12}}). problem(44,{{1,1,1,1,1,1,1,1,1,1,1,1},{1,1,2,2,2,2,2,2,2,3,3,1},{1,1,2,2,4,2,4,2,2,3,3,3},{5,2,2,6,4,4,4,3,3,3,6,3},{5,2,2,6,6,6,6,6,6,6,6,3},{5,2,7,7,7,7,6,6,6,3,3,3},{5,2,7,8,9,10,10,6,6,3,3,3},{5,2,11,8,9,9,10,12,6,3,3,3},{2,2,11,8,8,8,10,12,6,3,3,8},{2,2,11,11,11,8,10,12,8,8,8,8},{2,2,2,2,11,8,12,12,12,12,12,8},{2,2,2,11,11,8,8,8,8,8,8,8}}). problem(45,{{1,1,1,2,2,2,1,1,3,4,4,4},{5,5,1,1,1,1,1,1,3,4,4,6},{5,1,1,1,7,8,8,1,3,4,4,6},{1,1,1,1,7,8,1,1,3,4,4,6},{1,1,1,1,7,7,1,1,1,4,4,6},{9,1,1,1,1,7,1,1,1,4,4,6},{9,9,1,1,7,7,10,1,4,4,4,6},{11,9,12,1,7,10,10,1,4,7,4,4},{11,9,12,1,7,7,7,7,7,7,7,4},{11,9,12,1,1,1,9,9,9,9,9,4},{11,9,9,9,9,9,9,4,4,4,4,4},{11,11,11,11,9,9,9,9,4,4,4,4}}). problem(46,{{1,2,2,2,2,2,2,2,2,2,2,2},{1,2,3,3,4,5,2,2,2,2,2,2},{1,2,2,3,4,5,5,5,2,2,2,6},{1,1,1,3,4,5,5,5,2,7,6,6},{8,8,1,3,4,5,5,2,2,7,6,6},{9,8,1,3,4,5,2,2,7,7,6,6},{9,3,3,3,4,5,10,2,7,6,6,6},{9,3,3,3,3,5,10,10,7,7,7,6},{9,9,9,5,5,5,11,6,6,6,7,6},{5,9,9,5,5,11,11,11,5,6,6,6},{5,5,5,5,11,11,5,11,5,5,5,5},{5,5,5,5,5,5,5,5,5,12,12,12}}). problem(47,{{1,2,3,4,5,6,7,8,8,9,9,9},{1,2,3,4,5,6,7,7,8,9,9,9},{1,2,3,4,5,6,6,7,8,8,8,9},{2,2,3,4,5,4,4,4,4,4,8,9},{2,3,3,4,4,4,10,10,10,4,8,9},{2,3,2,2,2,2,2,11,11,4,8,9},{2,2,2,11,11,11,2,2,11,4,8,9},{9,9,2,11,11,11,2,2,11,4,8,9},{9,9,2,11,4,11,11,11,11,4,8,9},{9,9,2,2,4,4,4,4,4,4,8,9},{9,9,9,9,4,9,9,9,9,9,8,9},{9,9,9,9,9,9,12,12,12,9,9,9}}). problem(48,{{1,1,1,1,1,1,1,1,1,1,1,1},{1,1,1,1,1,2,3,3,3,3,3,1},{1,1,1,1,1,2,2,2,2,2,3,1},{1,1,4,4,4,4,4,4,4,3,3,1},{1,1,1,1,1,1,5,5,5,5,5,1},{1,6,6,1,5,5,5,7,7,1,1,1},{1,6,1,1,5,8,9,9,7,1,10,1},{1,6,6,1,8,8,9,7,7,10,10,1},{11,11,6,1,1,1,7,7,10,10,1,1},{11,11,6,1,7,7,7,10,10,1,1,12},{11,6,6,7,7,1,10,10,10,1,12,12},{11,6,6,7,7,1,1,1,1,1,12,12}}). problem(49,{{1,1,1,1,1,1,1,1,1,2,2,3},{1,4,4,1,1,1,1,1,2,2,2,3},{1,1,4,1,1,1,5,2,2,2,2,3},{1,4,4,1,5,5,5,2,5,5,5,3},{1,4,4,1,5,5,5,5,5,6,5,3},{7,7,4,1,1,7,7,7,7,6,5,6},{7,7,7,7,7,7,7,7,7,6,6,6},{8,8,9,9,9,9,9,10,10,10,10,10},{8,11,9,10,10,9,9,9,9,10,10,10},{8,11,10,10,10,10,9,10,10,10,10,10},{8,11,10,10,10,10,9,10,10,10,10,12},{8,8,8,8,8,10,10,10,10,10,12,12}}). problem(50,{{1,1,2,3,1,1,1,1,1,1,1,1},{1,1,2,3,3,3,1,1,1,1,1,1},{1,1,2,2,2,1,1,1,1,1,4,1},{1,1,1,1,1,1,5,1,1,1,4,1},{6,1,1,7,1,1,5,1,1,1,4,8},{6,9,1,7,10,10,5,5,4,4,4,8},{6,9,1,7,10,10,10,10,4,11,4,8},{9,9,1,1,10,4,4,10,4,11,4,8},{9,9,1,1,10,4,4,4,4,11,4,12},{9,9,1,1,1,11,11,11,11,11,4,12},{9,9,9,9,9,11,9,9,9,9,4,12},{9,9,9,9,9,9,9,9,12,12,12,12}}). % N = 13 problem(51,{{1,2,2,3,3,3,4,4,4,4,4,4,4},{1,2,3,3,4,4,4,4,5,5,5,5,5},{1,2,3,4,4,5,5,5,5,5,5,6,5},{1,1,3,4,4,5,5,5,6,6,6,6,5},{1,1,3,4,4,5,5,5,7,7,7,6,5},{8,1,3,4,4,5,5,5,5,5,5,5,9},{8,1,3,3,3,5,5,10,10,10,10,5,9},{8,1,1,11,3,5,5,10,10,10,10,5,9},{8,1,11,11,3,3,5,5,5,5,5,5,9},{8,1,1,1,12,13,13,13,5,5,5,5,9},{8,1,8,12,12,13,13,8,8,5,5,5,9},{8,1,8,12,12,13,8,8,8,5,5,5,5},{8,8,8,8,8,8,8,8,8,5,5,5,5}}). problem(52,{{1,2,2,2,3,3,3,3,3,3,3,3,3},{1,2,1,2,3,3,4,4,4,4,4,4,3},{1,1,1,2,5,5,5,5,4,6,6,6,6},{1,1,1,2,2,2,2,4,4,7,7,6,6},{1,1,1,1,1,2,4,4,7,7,6,6,6},{8,8,8,8,1,2,2,7,7,6,6,9,10},{11,1,1,8,1,2,2,2,2,6,6,9,10},{11,1,1,12,1,2,2,2,13,1,6,9,10},{11,1,12,12,1,13,13,13,13,1,6,6,10},{6,1,1,1,1,13,13,1,1,1,6,6,10},{6,6,6,6,1,1,13,13,13,1,6,10,10},{6,6,6,1,1,1,1,1,1,1,6,10,10},{6,6,6,6,6,6,6,6,6,6,6,10,10}}). problem(53,{{1,1,2,2,2,2,3,3,3,4,4,4,4},{1,1,5,5,2,2,6,3,3,4,7,7,8},{1,5,5,5,2,6,6,6,9,4,7,8,8},{1,5,10,10,2,10,10,9,9,4,4,4,8},{1,5,10,2,2,10,10,9,9,5,5,4,8},{1,5,10,10,2,10,9,9,5,5,5,5,8},{1,5,10,2,2,10,11,9,5,5,5,5,8},{1,5,10,10,10,10,11,9,9,9,5,5,8},{1,5,5,5,5,5,11,5,5,5,5,5,8},{1,1,1,1,1,5,5,5,5,5,5,5,8},{12,5,5,5,1,1,1,5,1,5,5,5,8},{12,5,13,13,13,1,1,1,1,5,5,5,8},{12,5,5,5,5,5,5,5,5,5,8,8,8}}). problem(54,{{1,1,1,1,1,2,2,2,2,3,4,4,4},{1,1,5,1,1,1,1,2,3,3,1,1,4},{5,1,5,1,6,1,1,1,1,1,1,1,4},{5,5,5,1,6,1,1,7,7,7,7,4,4},{1,1,1,1,6,1,7,7,7,7,7,8,4},{9,9,9,1,6,6,7,7,10,7,8,8,4},{9,9,9,1,6,6,7,7,10,7,8,4,4},{9,9,1,1,6,6,7,10,10,7,8,8,11},{8,9,9,1,12,12,7,7,7,7,7,8,11},{8,9,9,1,1,12,12,7,7,7,8,8,11},{8,9,9,1,13,12,12,7,7,8,8,8,11},{8,9,9,13,13,12,12,7,8,8,8,11,11},{8,8,8,8,8,8,8,8,8,8,8,11,11}}). problem(55,{{1,1,1,1,1,1,1,1,1,1,2,2,2},{1,1,1,1,3,3,3,3,3,2,2,2,2},{4,5,5,5,5,5,3,3,3,2,2,2,6},{4,7,5,8,5,5,5,5,5,5,2,2,6},{4,7,7,8,8,5,5,5,5,5,2,6,6},{4,4,7,7,8,5,5,9,5,5,2,2,6},{4,4,4,7,8,8,9,9,5,5,7,2,6},{4,4,4,7,8,8,9,9,5,5,7,6,6},{7,7,7,7,7,7,7,7,7,7,7,6,10},{7,6,6,6,7,6,6,6,11,7,7,6,10},{7,6,12,6,6,6,11,11,11,6,6,6,10},{12,6,12,12,6,6,6,6,6,6,6,13,13},{12,12,12,12,6,6,6,6,6,6,6,13,13}}).