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