1 // Copyright 2011 Hakan Kjellerstrand hakank@gmail.com 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 package com.google.ortools.contrib; 14 15 import com.google.ortools.Loader; 16 import com.google.ortools.constraintsolver.DecisionBuilder; 17 import com.google.ortools.constraintsolver.IntVar; 18 import com.google.ortools.constraintsolver.Solver; 19 import java.io.*; 20 import java.text.*; 21 import java.util.*; 22 23 public class Seseman { 24 /** Solves the Seseman convent problem. See http://www.hakank.org/google_or_tools/seseman.py */ solve(int n)25 private static void solve(int n) { 26 Solver solver = new Solver("Seseman"); 27 28 // 29 // data 30 // 31 final int border_sum = n * n; 32 33 // 34 // variables 35 // 36 IntVar[][] x = new IntVar[n][n]; 37 IntVar[] x_flat = new IntVar[n * n]; 38 for (int i = 0; i < n; i++) { 39 for (int j = 0; j < n; j++) { 40 x[i][j] = solver.makeIntVar(0, n * n); 41 x_flat[i * n + j] = x[i][j]; 42 } 43 } 44 45 IntVar total_sum = solver.makeSum(x_flat).var(); 46 47 // 48 // constraints 49 // 50 51 // zero in all middle cells 52 for (int i = 1; i < n - 1; i++) { 53 for (int j = 1; j < n - 1; j++) { 54 solver.addConstraint(solver.makeEquality(x[i][j], 0)); 55 } 56 } 57 58 // all borders must be >= 1 59 for (int i = 0; i < n; i++) { 60 for (int j = 0; j < n; j++) { 61 if (i == 0 || j == 0 || i == n - 1 || j == n - 1) { 62 solver.addConstraint(solver.makeGreaterOrEqual(x[i][j], 1)); 63 } 64 } 65 } 66 67 // sum the four borders 68 IntVar[] border1 = new IntVar[n]; 69 IntVar[] border2 = new IntVar[n]; 70 IntVar[] border3 = new IntVar[n]; 71 IntVar[] border4 = new IntVar[n]; 72 for (int i = 0; i < n; i++) { 73 border1[i] = x[i][0]; 74 border2[i] = x[i][n - 1]; 75 border3[i] = x[0][i]; 76 border4[i] = x[n - 1][i]; 77 } 78 solver.addConstraint(solver.makeSumEquality(border1, border_sum)); 79 80 solver.addConstraint(solver.makeSumEquality(border2, border_sum)); 81 82 solver.addConstraint(solver.makeSumEquality(border3, border_sum)); 83 84 solver.addConstraint(solver.makeSumEquality(border4, border_sum)); 85 86 // 87 // search 88 // 89 90 DecisionBuilder db = solver.makePhase(x_flat, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT); 91 solver.newSearch(db); 92 93 while (solver.nextSolution()) { 94 System.out.println("total_sum: " + total_sum.value()); 95 for (int i = 0; i < n; i++) { 96 for (int j = 0; j < n; j++) { 97 System.out.print(x[i][j].value() + " "); 98 } 99 System.out.println(); 100 } 101 System.out.println(); 102 } 103 solver.endSearch(); 104 105 // Statistics 106 System.out.println(); 107 System.out.println("Solutions: " + solver.solutions()); 108 System.out.println("Failures: " + solver.failures()); 109 System.out.println("Branches: " + solver.branches()); 110 System.out.println("Wall time: " + solver.wallTime() + "ms"); 111 } 112 main(String[] args)113 public static void main(String[] args) throws Exception { 114 Loader.loadNativeLibraries(); 115 int n = 3; 116 if (args.length > 0) { 117 n = Integer.parseInt(args[0]); 118 } 119 Seseman.solve(n); 120 } 121 } 122