1# Copyright 2010 Hakan Kjellerstrand hakank@gmail.com
2#
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7#     http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14"""
15
16  Seseman Convent problem in Google CP Solver.
17
18
19  n is the length of a border
20  There are (n-2)^2 "holes", i.e.
21  there are n^2 - (n-2)^2 variables to find out.
22
23  The simplest problem, n = 3 (n x n matrix)
24  which is represented by the following matrix:
25
26   a b c
27   d   e
28   f g h
29
30  Where the following constraints must hold:
31
32    a + b + c = border_sum
33    a + d + f = border_sum
34    c + e + h = border_sum
35    f + g + h = border_sum
36    a + b + c + d + e + f = total_sum
37
38
39  Compare with the following models:
40  * Tailor/Essence': http://hakank.org/tailor/seseman.eprime
41  * MiniZinc: http://hakank.org/minizinc/seseman.mzn
42  * SICStus: http://hakank.org/sicstus/seseman.pl
43  * Zinc: http://hakank.org/minizinc/seseman.zinc
44  * Choco: http://hakank.org/choco/Seseman.java
45  * Comet: http://hakank.org/comet/seseman.co
46  * ECLiPSe: http://hakank.org/eclipse/seseman.ecl
47  * Gecode: http://hakank.org/gecode/seseman.cpp
48  * Gecode/R: http://hakank.org/gecode_r/seseman.rb
49  * JaCoP: http://hakank.org/JaCoP/Seseman.java
50
51  This version use a better way of looping through all solutions.
52
53
54  This model was created by Hakan Kjellerstrand (hakank@gmail.com)
55  Also see my other Google CP Solver models:
56  http://www.hakank.org/google_or_tools/
57"""
58from ortools.constraint_solver import pywrapcp
59
60
61def main(unused_argv):
62  # Create the solver.
63  solver = pywrapcp.Solver("Seseman Convent problem")
64
65  # data
66  n = 3
67  border_sum = n * n
68
69  # declare variables
70  total_sum = solver.IntVar(1, n * n * n * n, "total_sum")
71  # x[0..n-1,0..n-1]
72  x = {}
73  for i in range(n):
74    for j in range(n):
75      x[(i, j)] = solver.IntVar(0, n * n, "x %i %i" % (i, j))
76
77  #
78  # constraints
79  #
80  # zero all middle cells
81  for i in range(1, n - 1):
82    for j in range(1, n - 1):
83      solver.Add(x[(i, j)] == 0)
84
85  # all borders must be >= 1
86  for i in range(n):
87    for j in range(n):
88      if i == 0 or j == 0 or i == n - 1 or j == n - 1:
89        solver.Add(x[(i, j)] >= 1)
90
91  # sum the borders (border_sum)
92  solver.Add(solver.Sum([x[(i, 0)] for i in range(n)]) == border_sum)
93  solver.Add(solver.Sum([x[(i, n - 1)] for i in range(n)]) == border_sum)
94  solver.Add(solver.Sum([x[(0, i)] for i in range(n)]) == border_sum)
95  solver.Add(solver.Sum([x[(n - 1, i)] for i in range(n)]) == border_sum)
96
97  # total
98  solver.Add(
99      solver.Sum([x[(i, j)] for i in range(n) for j in range(n)]) == total_sum)
100
101  #
102  # solution and search
103  #
104  solution = solver.Assignment()
105  solution.Add([x[(i, j)] for i in range(n) for j in range(n)])
106  solution.Add(total_sum)
107
108  db = solver.Phase([x[(i, j)] for i in range(n) for j in range(n)],
109                    solver.CHOOSE_PATH, solver.ASSIGN_MIN_VALUE)
110
111  solver.NewSearch(db)
112
113  num_solutions = 0
114
115  while solver.NextSolution():
116    num_solutions += 1
117    print("total_sum:", total_sum.Value())
118    for i in range(n):
119      for j in range(n):
120        print(x[(i, j)].Value(), end=" ")
121      print()
122    print()
123
124  print("num_solutions:", num_solutions)
125  print("failures:", solver.Failures())
126  print("branches:", solver.Branches())
127  print("WallTime:", solver.WallTime())
128
129
130if __name__ == "__main__":
131  main("cp sample")
132