1/*
2 * testSudoku.cpp
3 * @brief develop code for Sudoku CSP solver
4 * @date Jan 29, 2012
5 * @author Frank Dellaert
6 */
7
8#include <CppUnitLite/TestHarness.h>
9#include <gtsam/inference/Symbol.h>
10#include <gtsam_unstable/discrete/CSP.h>
11
12#include <stdarg.h>
13
14#include <iostream>
15#include <sstream>
16
17using namespace std;
18using namespace gtsam;
19
20#define PRINT false
21
22/// A class that encodes Sudoku's as a CSP problem
23class Sudoku : public CSP {
24 size_t n_; ///< Side of Sudoku, e.g. 4 or 9
25
26 /// Mapping from base i,j coordinates to discrete keys:
27 using IJ = std::pair<size_t, size_t>;
28 std::map<IJ, DiscreteKey> dkeys_;
29
30 public:
31 /// return DiscreteKey for cell(i,j)
32 const DiscreteKey& dkey(size_t i, size_t j) const {
33 return dkeys_.at(k: IJ(i, j));
34 }
35
36 /// return Key for cell(i,j)
37 Key key(size_t i, size_t j) const { return dkey(i, j).first; }
38
39 /// Constructor
40 Sudoku(size_t n, ...) : n_(n) {
41 // Create variables, ordering, and unary constraints
42 va_list ap;
43 va_start(ap, n);
44 for (size_t i = 0; i < n; ++i) {
45 for (size_t j = 0; j < n; ++j) {
46 // create the key
47 IJ ij(i, j);
48 Symbol key('1' + i, j + 1);
49 dkeys_[ij] = DiscreteKey(key, n);
50 // get the unary constraint, if any
51 int value = va_arg(ap, int);
52 if (value != 0) addSingleValue(dkey: dkeys_[ij], value: value - 1);
53 }
54 // cout << endl;
55 }
56 va_end(ap);
57
58 // add row constraints
59 for (size_t i = 0; i < n; i++) {
60 DiscreteKeys dkeys;
61 for (size_t j = 0; j < n; j++) dkeys.push_back(x: dkey(i, j));
62 addAllDiff(dkeys);
63 }
64
65 // add col constraints
66 for (size_t j = 0; j < n; j++) {
67 DiscreteKeys dkeys;
68 for (size_t i = 0; i < n; i++) dkeys.push_back(x: dkey(i, j));
69 addAllDiff(dkeys);
70 }
71
72 // add box constraints
73 size_t N = (size_t)sqrt(x: double(n)), i0 = 0;
74 for (size_t I = 0; I < N; I++) {
75 size_t j0 = 0;
76 for (size_t J = 0; J < N; J++) {
77 // Box I,J
78 DiscreteKeys dkeys;
79 for (size_t i = i0; i < i0 + N; i++)
80 for (size_t j = j0; j < j0 + N; j++) dkeys.push_back(x: dkey(i, j));
81 addAllDiff(dkeys);
82 j0 += N;
83 }
84 i0 += N;
85 }
86 }
87
88 /// Print readable form of assignment
89 void printAssignment(const DiscreteValues& assignment) const {
90 for (size_t i = 0; i < n_; i++) {
91 for (size_t j = 0; j < n_; j++) {
92 Key k = key(i, j);
93 cout << 1 + assignment.at(k: k) << " ";
94 }
95 cout << endl;
96 }
97 }
98
99 /// solve and print solution
100 void printSolution() const {
101 auto MPE = optimize();
102 printAssignment(assignment: MPE);
103 }
104
105 // Print domain
106 void printDomains(const Domains& domains) {
107 for (size_t i = 0; i < n_; i++) {
108 for (size_t j = 0; j < n_; j++) {
109 Key k = key(i, j);
110 cout << domains.at(k: k).base1Str();
111 cout << "\t";
112 } // i
113 cout << endl;
114 } // j
115 }
116};
117
118/* ************************************************************************* */
119TEST(Sudoku, small) {
120 Sudoku csp(4, //
121 1, 0, 0, 4, //
122 0, 0, 0, 0, //
123 4, 0, 2, 0, //
124 0, 1, 0, 0);
125
126 // optimize and check
127 auto solution = csp.optimize();
128 DiscreteValues expected;
129 expected = {{csp.key(i: 0, j: 0), 0}, {csp.key(i: 0, j: 1), 1},
130 {csp.key(i: 0, j: 2), 2}, {csp.key(i: 0, j: 3), 3}, //
131 {csp.key(i: 1, j: 0), 2}, {csp.key(i: 1, j: 1), 3},
132 {csp.key(i: 1, j: 2), 0}, {csp.key(i: 1, j: 3), 1}, //
133 {csp.key(i: 2, j: 0), 3}, {csp.key(i: 2, j: 1), 2},
134 {csp.key(i: 2, j: 2), 1}, {csp.key(i: 2, j: 3), 0}, //
135 {csp.key(i: 3, j: 0), 1}, {csp.key(i: 3, j: 1), 0},
136 {csp.key(i: 3, j: 2), 3}, {csp.key(i: 3, j: 3), 2}};
137 EXPECT(assert_equal(expected, solution));
138 // csp.printAssignment(solution);
139
140 // Do BP (AC1)
141 auto domains = csp.runArcConsistency(cardinality: 4, maxIterations: 3);
142 // csp.printDomains(domains);
143 Domain domain44 = domains.at(k: Symbol('4', 4));
144 EXPECT_LONGS_EQUAL(1, domain44.nrValues());
145
146 // Test Creation of a new, simpler CSP
147 CSP new_csp = csp.partiallyApply(domains);
148 // Should only be 16 new Domains
149 EXPECT_LONGS_EQUAL(16, new_csp.size());
150
151 // Check that solution
152 auto new_solution = new_csp.optimize();
153 // csp.printAssignment(new_solution);
154 EXPECT(assert_equal(expected, new_solution));
155}
156
157/* ************************************************************************* */
158TEST(Sudoku, easy) {
159 Sudoku csp(9, //
160 0, 0, 5, 0, 9, 0, 0, 0, 1, //
161 0, 0, 0, 0, 0, 2, 0, 7, 3, //
162 7, 6, 0, 0, 0, 8, 2, 0, 0, //
163
164 0, 1, 2, 0, 0, 9, 0, 0, 4, //
165 0, 0, 0, 2, 0, 3, 0, 0, 0, //
166 3, 0, 0, 1, 0, 0, 9, 6, 0, //
167
168 0, 0, 1, 9, 0, 0, 0, 5, 8, //
169 9, 7, 0, 5, 0, 0, 0, 0, 0, //
170 5, 0, 0, 0, 3, 0, 7, 0, 0);
171
172 // csp.printSolution(); // don't do it
173
174 // Do BP (AC1)
175 auto domains = csp.runArcConsistency(cardinality: 9, maxIterations: 10);
176 // csp.printDomains(domains);
177 Key key99 = Symbol('9', 9);
178 Domain domain99 = domains.at(k: key99);
179 EXPECT_LONGS_EQUAL(1, domain99.nrValues());
180
181 // Test Creation of a new, simpler CSP
182 CSP new_csp = csp.partiallyApply(domains);
183 // 81 new Domains, and still 26 all-diff constraints
184 EXPECT_LONGS_EQUAL(81 + 26, new_csp.size());
185
186 // csp.printSolution(); // still don't do it ! :-(
187}
188
189/* ************************************************************************* */
190TEST(Sudoku, extreme) {
191 Sudoku csp(9, //
192 0, 0, 9, 7, 4, 8, 0, 0, 0, 7, //
193 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, //
194 0, 1, 0, 9, 0, 0, 0, 0, 0, 7, //
195 0, 0, 0, 2, 4, 0, 0, 6, 4, 0, //
196 1, 0, 5, 9, 0, 0, 9, 8, 0, 0, //
197 0, 3, 0, 0, 0, 0, 0, 8, 0, 3, //
198 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, //
199 0, 6, 0, 0, 0, 2, 7, 5, 9, 0, 0);
200
201 // Do BP
202 csp.runArcConsistency(cardinality: 9, maxIterations: 10);
203
204#ifdef METIS
205 VariableIndexOrdered index(csp);
206 index.print("index");
207 ofstream os("/Users/dellaert/src/hmetis-1.5-osx-i686/extreme-dual.txt");
208 index.outputMetisFormat(os);
209#endif
210
211 // Do BP (AC1)
212 auto domains = csp.runArcConsistency(cardinality: 9, maxIterations: 10);
213 // csp.printDomains(domains);
214 Key key99 = Symbol('9', 9);
215 Domain domain99 = domains.at(k: key99);
216 EXPECT_LONGS_EQUAL(2, domain99.nrValues());
217
218 // Test Creation of a new, simpler CSP
219 CSP new_csp = csp.partiallyApply(domains);
220 // 81 new Domains, and still 20 all-diff constraints
221 EXPECT_LONGS_EQUAL(81 + 20, new_csp.size());
222
223 // csp.printSolution(); // still don't do it ! :-(
224}
225
226/* ************************************************************************* */
227TEST(Sudoku, AJC_3star_Feb8_2012) {
228 Sudoku csp(9, //
229 9, 5, 0, 0, 0, 6, 0, 0, 0, //
230 0, 8, 4, 0, 7, 0, 0, 0, 0, //
231 6, 2, 0, 5, 0, 0, 4, 0, 0, //
232
233 0, 0, 0, 2, 9, 0, 6, 0, 0, //
234 0, 9, 0, 0, 0, 0, 0, 2, 0, //
235 0, 0, 2, 0, 6, 3, 0, 0, 0, //
236
237 0, 0, 9, 0, 0, 7, 0, 6, 8, //
238 0, 0, 0, 0, 3, 0, 2, 9, 0, //
239 0, 0, 0, 1, 0, 0, 0, 3, 7);
240
241 // Do BP (AC1)
242 auto domains = csp.runArcConsistency(cardinality: 9, maxIterations: 10);
243 // csp.printDomains(domains);
244 Key key99 = Symbol('9', 9);
245 Domain domain99 = domains.at(k: key99);
246 EXPECT_LONGS_EQUAL(1, domain99.nrValues());
247
248 // Test Creation of a new, simpler CSP
249 CSP new_csp = csp.partiallyApply(domains);
250 // Just the 81 new Domains
251 EXPECT_LONGS_EQUAL(81, new_csp.size());
252
253 // Check that solution
254 auto solution = new_csp.optimize();
255 // csp.printAssignment(solution);
256 EXPECT_LONGS_EQUAL(6, solution.at(key99));
257}
258
259/* ************************************************************************* */
260int main() {
261 TestResult tr;
262 return TestRegistry::runAllTests(result&: tr);
263}
264/* ************************************************************************* */
265