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