btrfs: Attempt to fix GCC2 build.
[haiku.git] / src / apps / sudoku / SudokuSolver.cpp
blob1f53bcc3a2d681b3ce08974fd44f272b11dad038
1 /*
2 * Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 */
7 #include "SudokuSolver.h"
9 #include "SudokuField.h"
10 #include "Stack.h"
13 struct SolutionStep {
14 public:
15 SolutionStep(const SudokuField* field);
16 SolutionStep(const SolutionStep& other);
17 ~SolutionStep();
19 void ToFirstUnset();
20 bool ToNextUnset();
22 void SetSolvedFields();
24 SudokuField* Field() { return fField; }
25 uint32 X() { return fX; }
26 uint32 Y() { return fY; }
28 private:
29 SudokuField* fField;
30 uint32 fX;
31 uint32 fY;
34 typedef std::vector<SolutionStep*> StepList;
37 uint32
38 bit_count(uint32 value)
40 uint32 count = 0;
41 while (value > 0) {
42 if (value & 1)
43 count++;
44 value >>= 1;
46 return count;
50 // #pragma mark -
53 SolutionStep::SolutionStep(const SudokuField* _field)
55 fField = new SudokuField(*_field);
56 fX = 0;
57 fY = 0;
61 SolutionStep::SolutionStep(const SolutionStep& other)
63 fField = new SudokuField(*other.fField);
64 fX = other.fX;
65 fY = other.fY;
69 SolutionStep::~SolutionStep()
71 delete fField;
75 void
76 SolutionStep::ToFirstUnset()
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++;
91 fField->SetValueAt(x, y, value + 1, true);
92 continue;
95 fX = x;
96 fY = y;
97 return;
105 bool
106 SolutionStep::ToNextUnset()
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;
115 if (!fField->ValueAt(x, y)) {
116 fX = x;
117 fY = y;
118 return true;
123 return false;
127 // #pragma mark -
130 SudokuSolver::SudokuSolver(SudokuField* field)
132 fField(field)
137 SudokuSolver::SudokuSolver()
139 fField(NULL)
144 SudokuSolver::~SudokuSolver()
146 // we don't own the field but the solutions
147 _MakeEmpty();
151 void
152 SudokuSolver::_MakeEmpty()
154 for (uint32 i = 0; i < fSolutions.size(); i++) {
155 delete fSolutions[i];
160 void
161 SudokuSolver::SetTo(SudokuField* field)
163 fField = field;
167 void
168 SudokuSolver::ComputeSolutions()
170 _MakeEmpty();
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++;
181 if (set < fField->Size() * fField->Size() / 6)
182 return;
184 Stack<SolutionStep*> stack;
185 SolutionStep* step = new SolutionStep(fField);
186 step->ToFirstUnset();
188 stack.Push(step);
189 uint32 count = 0;
191 // brute force version
193 while (stack.Pop(&step)) {
194 uint32 x = step->X();
195 uint32 y = step->Y();
196 uint32 validMask = step->Field()->ValidMaskAt(x, y);
198 count++;
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;
207 SolutionStep* next = new SolutionStep(*step);
208 next->Field()->SetValueAt(x, y, i + 1, true);
209 stack.Push(next);
212 } else if (step->Field()->IsSolved())
213 fSolutions.push_back(new SudokuField(*step->Field()));
215 delete step;
218 //printf("evaluated %lu steps\n", count);
222 uint32
223 SudokuSolver::CountSolutions()
225 return fSolutions.size();
229 SudokuField*
230 SudokuSolver::SolutionAt(uint32 index)
232 return fSolutions[index];