testSudoku.cpp
Go to the documentation of this file.
1 /*
2  * testSudoku.cpp
3  * @brief develop code for Sudoku CSP solver
4  * @date Jan 29, 2012
5  * @author Frank Dellaert
6  */
7 
11 
12 #include <stdarg.h>
13 
14 #include <iostream>
15 #include <sstream>
16 
17 using namespace std;
18 using namespace gtsam;
19 
20 #define PRINT false
21 
23 class Sudoku : public CSP {
24  size_t n_;
25 
27  using IJ = std::pair<size_t, size_t>;
28  std::map<IJ, DiscreteKey> dkeys_;
29 
30  public:
32  const DiscreteKey& dkey(size_t i, size_t j) const {
33  return dkeys_.at(IJ(i, j));
34  }
35 
37  Key key(size_t i, size_t j) const { return dkey(i, j).first; }
38 
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(dkeys_[ij], 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(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(dkey(i, j));
69  addAllDiff(dkeys);
70  }
71 
72  // add box constraints
73  size_t N = (size_t)sqrt(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(dkey(i, j));
81  addAllDiff(dkeys);
82  j0 += N;
83  }
84  i0 += N;
85  }
86  }
87 
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) << " ";
94  }
95  cout << endl;
96  }
97  }
98 
100  void printSolution() const {
101  auto MPE = optimize();
102  printAssignment(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).base1Str();
111  cout << "\t";
112  } // i
113  cout << endl;
114  } // j
115  }
116 };
117 
118 /* ************************************************************************* */
119 TEST(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();
129  expected = {{csp.key(0, 0), 0}, {csp.key(0, 1), 1},
130  {csp.key(0, 2), 2}, {csp.key(0, 3), 3}, //
131  {csp.key(1, 0), 2}, {csp.key(1, 1), 3},
132  {csp.key(1, 2), 0}, {csp.key(1, 3), 1}, //
133  {csp.key(2, 0), 3}, {csp.key(2, 1), 2},
134  {csp.key(2, 2), 1}, {csp.key(2, 3), 0}, //
135  {csp.key(3, 0), 1}, {csp.key(3, 1), 0},
136  {csp.key(3, 2), 3}, {csp.key(3, 3), 2}};
137  EXPECT(assert_equal(expected, solution));
138  // csp.printAssignment(solution);
139 
140  // Do BP (AC1)
141  auto domains = csp.runArcConsistency(4, 3);
142  // csp.printDomains(domains);
143  Domain domain44 = domains.at(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 /* ************************************************************************* */
158 TEST(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(9, 10);
176  // csp.printDomains(domains);
177  Key key99 = Symbol('9', 9);
178  Domain domain99 = domains.at(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 /* ************************************************************************* */
190 TEST(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(9, 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(9, 10);
213  // csp.printDomains(domains);
214  Key key99 = Symbol('9', 9);
215  Domain domain99 = domains.at(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 /* ************************************************************************* */
227 TEST(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(9, 10);
243  // csp.printDomains(domains);
244  Key key99 = Symbol('9', 9);
245  Domain domain99 = domains.at(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 /* ************************************************************************* */
260 int main() {
261  TestResult tr;
262  return TestRegistry::runAllTests(tr);
263 }
264 /* ************************************************************************* */
TestRegistry::runAllTests
static int runAllTests(TestResult &result)
Definition: TestRegistry.cpp:27
Sudoku::dkeys_
std::map< IJ, DiscreteKey > dkeys_
Definition: testSudoku.cpp:28
EXPECT_LONGS_EQUAL
#define EXPECT_LONGS_EQUAL(expected, actual)
Definition: Test.h:154
EXPECT
#define EXPECT(condition)
Definition: Test.h:150
optimize
int optimize(const SfmData &db, const NonlinearFactorGraph &graph, const Values &initial, bool separateCalibration=false)
Definition: timeSFMBAL.h:64
TestHarness.h
Sudoku::dkey
const DiscreteKey & dkey(size_t i, size_t j) const
return DiscreteKey for cell(i,j)
Definition: testSudoku.cpp:32
Sudoku::IJ
std::pair< size_t, size_t > IJ
Mapping from base i,j coordinates to discrete keys:
Definition: testSudoku.cpp:27
gtsam::Domain::nrValues
size_t nrValues() const
Definition: Domain.h:52
gtsam::DiscreteKeys
DiscreteKeys is a set of keys that can be assembled using the & operator.
Definition: DiscreteKey.h:41
os
ofstream os("timeSchurFactors.csv")
Sudoku::printAssignment
void printAssignment(const DiscreteValues &assignment) const
Print readable form of assignment.
Definition: testSudoku.cpp:89
n
int n
Definition: BiCGSTAB_simple.cpp:1
gtsam::CSP::partiallyApply
CSP partiallyApply(const Domains &domains) const
Definition: CSP.cpp:63
Sudoku::Sudoku
Sudoku(size_t n,...)
Constructor.
Definition: testSudoku.cpp:40
J
JacobiRotation< float > J
Definition: Jacobi_makeJacobi.cpp:3
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
I
#define I
Definition: main.h:112
main
int main()
Definition: testSudoku.cpp:260
Sudoku::key
Key key(size_t i, size_t j) const
return Key for cell(i,j)
Definition: testSudoku.cpp:37
gtsam::Domain
Definition: Domain.h:20
cholesky::expected
Matrix expected
Definition: testMatrix.cpp:971
Symbol.h
Sudoku
A class that encodes Sudoku's as a CSP problem.
Definition: testSudoku.cpp:23
Sudoku::printDomains
void printDomains(const Domains &domains)
Definition: testSudoku.cpp:106
gtsam::Domains
std::map< Key, Domain > Domains
Definition: Constraint.h:29
size_t
std::size_t size_t
Definition: wrap/pybind11/include/pybind11/detail/common.h:490
TestResult
Definition: TestResult.h:26
key
const gtsam::Symbol key('X', 0)
gtsam::FactorGraph::size
size_t size() const
Definition: FactorGraph.h:297
i0
double i0(double x)
Definition: i0.c:149
j0
double j0(double x)
Definition: j0.c:185
gtsam::CSP::runArcConsistency
Domains runArcConsistency(size_t cardinality, size_t maxIterations=10) const
Definition: CSP.cpp:44
gtsam
traits
Definition: SFMdata.h:40
gtsam::DiscreteValues
Definition: DiscreteValues.h:34
gtsam::CSP
Definition: CSP.h:21
gtsam::DiscreteKey
std::pair< Key, size_t > DiscreteKey
Definition: DiscreteKey.h:38
std
Definition: BFloat16.h:88
CSP.h
gtsam::assert_equal
bool assert_equal(const Matrix &expected, const Matrix &actual, double tol)
Definition: Matrix.cpp:40
Sudoku::printSolution
void printSolution() const
solve and print solution
Definition: testSudoku.cpp:100
TEST
TEST(Sudoku, small)
Definition: testSudoku.cpp:119
Sudoku::n_
size_t n_
Side of Sudoku, e.g. 4 or 9.
Definition: testSudoku.cpp:24
N
#define N
Definition: igam.h:9
gtsam::DiscreteFactorGraph::optimize
DiscreteValues optimize(OptionalOrderingType orderingType={}) const
Find the maximum probable explanation (MPE) by doing max-product.
Definition: DiscreteFactorGraph.cpp:189
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:97
test_callbacks.value
value
Definition: test_callbacks.py:160
ceres::sqrt
Jet< T, N > sqrt(const Jet< T, N > &f)
Definition: jet.h:418
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
gtsam::Symbol
Definition: inference/Symbol.h:37


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:41:48