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 Google.OrTools.ConstraintSolver;
18 
19 public class LeastDiff
20 {
21     /**
22      *
23      * Solve the Least diff problem
24      * For more info, see http://www.hakank.org/google_or_tools/least_diff.py
25      *
26      */
Solve()27     private static void Solve()
28     {
29         Solver solver = new Solver("LeastDiff");
30 
31         //
32         // Decision variables
33         //
34         IntVar A = solver.MakeIntVar(0, 9, "A");
35         IntVar B = solver.MakeIntVar(0, 9, "B");
36         IntVar C = solver.MakeIntVar(0, 9, "C");
37         IntVar D = solver.MakeIntVar(0, 9, "D");
38         IntVar E = solver.MakeIntVar(0, 9, "E");
39         IntVar F = solver.MakeIntVar(0, 9, "F");
40         IntVar G = solver.MakeIntVar(0, 9, "G");
41         IntVar H = solver.MakeIntVar(0, 9, "H");
42         IntVar I = solver.MakeIntVar(0, 9, "I");
43         IntVar J = solver.MakeIntVar(0, 9, "J");
44 
45         IntVar[] all = new IntVar[] { A, B, C, D, E, F, G, H, I, J };
46         int[] coeffs = { 10000, 1000, 100, 10, 1 };
47         IntVar x = new IntVar[] { A, B, C, D, E }.ScalProd(coeffs).Var();
48         IntVar y = new IntVar[] { F, G, H, I, J }.ScalProd(coeffs).Var();
49         IntVar diff = (x - y).VarWithName("diff");
50 
51         //
52         // Constraints
53         //
54         solver.Add(all.AllDifferent());
55         solver.Add(A > 0);
56         solver.Add(F > 0);
57         solver.Add(diff > 0);
58 
59         //
60         // Objective
61         //
62         OptimizeVar obj = diff.Minimize(1);
63 
64         //
65         // Search
66         //
67         DecisionBuilder db = solver.MakePhase(all, Solver.CHOOSE_PATH, Solver.ASSIGN_MIN_VALUE);
68 
69         solver.NewSearch(db, obj);
70         while (solver.NextSolution())
71         {
72             Console.WriteLine("{0} - {1} = {2}  ({3}", x.Value(), y.Value(), diff.Value(), diff.ToString());
73         }
74 
75         Console.WriteLine("\nSolutions: {0}", solver.Solutions());
76         Console.WriteLine("WallTime: {0}ms", solver.WallTime());
77         Console.WriteLine("Failures: {0}", solver.Failures());
78         Console.WriteLine("Branches: {0} ", solver.Branches());
79 
80         solver.EndSearch();
81     }
82 
Main(String[] args)83     public static void Main(String[] args)
84     {
85         Solve();
86     }
87 }
88