1 // 2 // Copyright 2012 Hakan Kjellerstrand 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 16 using System; 17 using System.Collections; 18 using System.Collections.Generic; 19 using System.Linq; 20 using Google.OrTools.ConstraintSolver; 21 22 public class PerfectSquareSequence 23 { 24 /** 25 * 26 * Perfect square sequence. 27 * 28 * From 'Fun with num3ers' 29 * "Sequence" 30 * http://benvitale-funwithnum3ers.blogspot.com/2010/11/sequence.html 31 * """ 32 * If we take the numbers from 1 to 15 33 * (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) 34 * and rearrange them in such an order that any two consecutive 35 * numbers in the sequence add up to a perfect square, we get, 36 * 37 * 8 1 15 10 6 3 13 12 4 5 11 14 2 38 * 7 9 9 16 25 16 9 16 25 16 9 16 25 16 39 * 9 16 40 * 41 * 42 * I ask the readers the following: 43 * 44 * Can you take the numbers from 1 to 25 to produce such an arrangement? 45 * How about the numbers from 1 to 100? 46 * """ 47 * 48 * Via http://wildaboutmath.com/2010/11/26/wild-about-math-bloggers-111910 49 * 50 * 51 * Also see http://www.hakank.org/or-tools/perfect_square_sequence.py 52 * 53 */ Solve(int n = 15, int print_solutions = 1, int show_num_sols = 0)54 private static int Solve(int n = 15, int print_solutions = 1, int show_num_sols = 0) 55 { 56 Solver solver = new Solver("PerfectSquareSequence"); 57 58 IEnumerable<int> RANGE = Enumerable.Range(0, n); 59 60 // create the table of possible squares 61 int[] squares = new int[n - 1]; 62 for (int i = 1; i < n; i++) 63 { 64 squares[i - 1] = i * i; 65 } 66 67 // 68 // Decision variables 69 // 70 IntVar[] x = solver.MakeIntVarArray(n, 1, n, "x"); 71 72 // 73 // Constraints 74 // 75 76 solver.Add(x.AllDifferent()); 77 78 for (int i = 1; i < n; i++) 79 { 80 solver.Add((x[i - 1] + x[i]).Member(squares)); 81 } 82 83 // symmetry breaking 84 solver.Add(x[0] < x[n - 1]); 85 86 // 87 // Search 88 // 89 DecisionBuilder db = solver.MakePhase(x, Solver.CHOOSE_FIRST_UNBOUND, Solver.INT_VALUE_DEFAULT); 90 91 solver.NewSearch(db); 92 93 int num_solutions = 0; 94 while (solver.NextSolution()) 95 { 96 num_solutions++; 97 if (print_solutions > 0) 98 { 99 Console.Write("x: "); 100 foreach (int i in RANGE) 101 { 102 Console.Write(x[i].Value() + " "); 103 } 104 Console.WriteLine(); 105 } 106 107 if (show_num_sols > 0 && num_solutions >= show_num_sols) 108 { 109 break; 110 } 111 } 112 113 if (print_solutions > 0) 114 { 115 Console.WriteLine("\nSolutions: {0}", solver.Solutions()); 116 Console.WriteLine("WallTime: {0}ms", solver.WallTime()); 117 Console.WriteLine("Failures: {0}", solver.Failures()); 118 Console.WriteLine("Branches: {0} ", solver.Branches()); 119 } 120 121 solver.EndSearch(); 122 123 return num_solutions; 124 } 125 Main(String[] args)126 public static void Main(String[] args) 127 { 128 int n = 15; 129 if (args.Length > 0) 130 { 131 n = Convert.ToInt32(args[0]); 132 } 133 134 if (n == 0) 135 { 136 for (int i = 2; i < 100; i++) 137 { 138 int num_solutions = Solve(i, 0, 0); 139 Console.WriteLine("{0}: {1} solution(s)", i, num_solutions); 140 } 141 } 142 else 143 { 144 int num_solutions = Solve(n); 145 Console.WriteLine("{0}: {1} solution(s)", n, num_solutions); 146 } 147 } 148 } 149