1 /*
2 * Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7 #include "SudokuSolver.h"
8
9 #include "SudokuField.h"
10 #include "Stack.h"
11
12
13 struct SolutionStep {
14 public:
15 SolutionStep(const SudokuField* field);
16 SolutionStep(const SolutionStep& other);
17 ~SolutionStep();
18
19 void ToFirstUnset();
20 bool ToNextUnset();
21
22 void SetSolvedFields();
23
FieldSolutionStep24 SudokuField* Field() { return fField; }
XSolutionStep25 uint32 X() { return fX; }
YSolutionStep26 uint32 Y() { return fY; }
27
28 private:
29 SudokuField* fField;
30 uint32 fX;
31 uint32 fY;
32 };
33
34 typedef std::vector<SolutionStep*> StepList;
35
36
37 uint32
bit_count(uint32 value)38 bit_count(uint32 value)
39 {
40 uint32 count = 0;
41 while (value > 0) {
42 if (value & 1)
43 count++;
44 value >>= 1;
45 }
46 return count;
47 }
48
49
50 // #pragma mark -
51
52
SolutionStep(const SudokuField * _field)53 SolutionStep::SolutionStep(const SudokuField* _field)
54 {
55 fField = new SudokuField(*_field);
56 fX = 0;
57 fY = 0;
58 }
59
60
SolutionStep(const SolutionStep & other)61 SolutionStep::SolutionStep(const SolutionStep& other)
62 {
63 fField = new SudokuField(*other.fField);
64 fX = other.fX;
65 fY = other.fY;
66 }
67
68
~SolutionStep()69 SolutionStep::~SolutionStep()
70 {
71 delete fField;
72 }
73
74
75 void
ToFirstUnset()76 SolutionStep::ToFirstUnset()
77 {
78 for (uint32 y = 0; y < fField->Size(); y++) {
79 for (uint32 x = 0; x < fField->Size(); x++) {
80 if (!fField->ValueAt(x, y)) {
81 uint32 validMask = fField->ValidMaskAt(x, y);
82 if (bit_count(validMask) == 1) {
83 // If the chosen value is already solved, we set its
84 // value here and go on - this makes sure the first
85 // unset we return has actually more than one possible
86 // value
87 uint32 value = 0;
88 while ((validMask & (1UL << value)) == 0) {
89 value++;
90 }
91 fField->SetValueAt(x, y, value + 1, true);
92 continue;
93 }
94
95 fX = x;
96 fY = y;
97 return;
98 }
99 }
100 }
101
102 }
103
104
105 bool
ToNextUnset()106 SolutionStep::ToNextUnset()
107 {
108 for (uint32 y = fY; y < fField->Size(); y++) {
109 for (uint32 x = 0; x < fField->Size(); x++) {
110 if (y == fY && x == 0) {
111 x = fX;
112 continue;
113 }
114
115 if (!fField->ValueAt(x, y)) {
116 fX = x;
117 fY = y;
118 return true;
119 }
120 }
121 }
122
123 return false;
124 }
125
126
127 // #pragma mark -
128
129
SudokuSolver(SudokuField * field)130 SudokuSolver::SudokuSolver(SudokuField* field)
131 :
132 fField(field)
133 {
134 }
135
136
SudokuSolver()137 SudokuSolver::SudokuSolver()
138 :
139 fField(NULL)
140 {
141 }
142
143
~SudokuSolver()144 SudokuSolver::~SudokuSolver()
145 {
146 // we don't own the field but the solutions
147 _MakeEmpty();
148 }
149
150
151 void
_MakeEmpty()152 SudokuSolver::_MakeEmpty()
153 {
154 for (uint32 i = 0; i < fSolutions.size(); i++) {
155 delete fSolutions[i];
156 }
157 }
158
159
160 void
SetTo(SudokuField * field)161 SudokuSolver::SetTo(SudokuField* field)
162 {
163 fField = field;
164 }
165
166
167 void
ComputeSolutions()168 SudokuSolver::ComputeSolutions()
169 {
170 _MakeEmpty();
171
172 // We need to check if generating a solution is affordable with a
173 // brute force algorithm like this one
174 uint32 set = 0;
175 for (uint32 y = 0; y < fField->Size(); y++) {
176 for (uint32 x = 0; x < fField->Size(); x++) {
177 if (fField->ValueAt(x, y))
178 set++;
179 }
180 }
181 if (set < fField->Size() * fField->Size() / 6)
182 return;
183
184 Stack<SolutionStep*> stack;
185 SolutionStep* step = new SolutionStep(fField);
186 step->ToFirstUnset();
187
188 stack.Push(step);
189 uint32 count = 0;
190
191 // brute force version
192
193 while (stack.Pop(&step)) {
194 uint32 x = step->X();
195 uint32 y = step->Y();
196 uint32 validMask = step->Field()->ValidMaskAt(x, y);
197
198 count++;
199
200 if (step->ToNextUnset()) {
201 if (validMask != 0) {
202 // generate further steps
203 for (uint32 i = 0; i < fField->Size(); i++) {
204 if ((validMask & (1UL << i)) == 0)
205 continue;
206
207 SolutionStep* next = new SolutionStep(*step);
208 next->Field()->SetValueAt(x, y, i + 1, true);
209 stack.Push(next);
210 }
211 }
212 } else if (step->Field()->IsSolved())
213 fSolutions.push_back(new SudokuField(*step->Field()));
214
215 delete step;
216 }
217
218 //printf("evaluated %lu steps\n", count);
219 }
220
221
222 uint32
CountSolutions()223 SudokuSolver::CountSolutions()
224 {
225 return fSolutions.size();
226 }
227
228
229 SudokuField*
SolutionAt(uint32 index)230 SudokuSolver::SolutionAt(uint32 index)
231 {
232 return fSolutions[index];
233 }
234
235