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.IO;
19 using System.Linq;
20 using System.Text.RegularExpressions;
21 using Google.OrTools.ConstraintSolver;
22 
23 public class JustForgotten
24 {
25     /**
26      *
27      * Just forgotten puzzle (Enigma 1517) in Google CP Solver.
28      *
29      * From http://www.f1compiler.com/samples/Enigma 201517.f1.html
30      * """
31      * Enigma 1517 Bob Walker, New Scientist magazine, October 25, 2008.
32      *
33      * Joe was furious when he forgot one of his bank account numbers.
34      * He remembered that it had all the digits 0 to 9 in some order,
35      * so he tried the following four sets without success:
36      *
37      * 9 4 6 2 1 5 7 8 3 0
38      * 8 6 0 4 3 9 1 2 5 7
39      * 1 6 4 0 2 9 7 8 5 3
40      * 6 8 2 4 3 1 9 0 7 5
41      *
42      * When Joe finally remembered his account number, he realised that
43      * in each set just four of the digits were in their correct position
44      * and that, if one knew that, it was possible to work out his
45      * account number. What was it?
46      * """
47      *
48      * Also see http://www.hakank.org/google_or_tools/just_forgotten.py
49      *
50      */
Solve()51     private static void Solve()
52     {
53         Solver solver = new Solver("JustForgotten");
54 
55         int rows = 4;
56         int cols = 10;
57 
58         // The four tries
59         int[,] a = { { 9, 4, 6, 2, 1, 5, 7, 8, 3, 0 },
60                      { 8, 6, 0, 4, 3, 9, 1, 2, 5, 7 },
61                      { 1, 6, 4, 0, 2, 9, 7, 8, 5, 3 },
62                      { 6, 8, 2, 4, 3, 1, 9, 0, 7, 5 } };
63 
64         //
65         // Decision variables
66         //
67         IntVar[] x = solver.MakeIntVarArray(cols, 0, 9, "x");
68 
69         //
70         // Constraints
71         //
72         solver.Add(x.AllDifferent());
73         for (int r = 0; r < rows; r++)
74         {
75             solver.Add((from c in Enumerable.Range(0, cols) select x[c] == a[r, c]).ToArray().Sum() == 4);
76         }
77 
78         //
79         // Search
80         //
81         DecisionBuilder db = solver.MakePhase(x, Solver.INT_VAR_DEFAULT, Solver.INT_VALUE_DEFAULT);
82 
83         solver.NewSearch(db);
84 
85         while (solver.NextSolution())
86         {
87             Console.WriteLine("Account number:");
88             for (int j = 0; j < cols; j++)
89             {
90                 Console.Write(x[j].Value() + " ");
91             }
92             Console.WriteLine("\n");
93             Console.WriteLine("The four tries, where '!' represents a correct digit:");
94             for (int i = 0; i < rows; i++)
95             {
96                 for (int j = 0; j < cols; j++)
97                 {
98                     String c = " ";
99                     if (a[i, j] == x[j].Value())
100                     {
101                         c = "!";
102                     }
103                     Console.Write("{0}{1} ", a[i, j], c);
104                 }
105                 Console.WriteLine();
106             }
107             Console.WriteLine();
108         }
109 
110         Console.WriteLine("\nSolutions: {0}", solver.Solutions());
111         Console.WriteLine("WallTime: {0}ms", solver.WallTime());
112         Console.WriteLine("Failures: {0}", solver.Failures());
113         Console.WriteLine("Branches: {0} ", solver.Branches());
114 
115         solver.EndSearch();
116     }
117 
Main(String[] args)118     public static void Main(String[] args)
119     {
120         Solve();
121     }
122 }
123