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 24 SudokuField* Field() { return fField; } 25 uint32 X() { return fX; } 26 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 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 53 SolutionStep::SolutionStep(const SudokuField* _field) 54 { 55 fField = new SudokuField(*_field); 56 fX = 0; 57 fY = 0; 58 } 59 60 61 SolutionStep::SolutionStep(const SolutionStep& other) 62 { 63 fField = new SudokuField(*other.fField); 64 fX = other.fX; 65 fY = other.fY; 66 } 67 68 69 SolutionStep::~SolutionStep() 70 { 71 delete fField; 72 } 73 74 75 void 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 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 130 SudokuSolver::SudokuSolver(SudokuField* field) 131 : 132 fField(field) 133 { 134 } 135 136 137 SudokuSolver::SudokuSolver() 138 : 139 fField(NULL) 140 { 141 } 142 143 144 SudokuSolver::~SudokuSolver() 145 { 146 // we don't own the field but the solutions 147 _MakeEmpty(); 148 } 149 150 151 void 152 SudokuSolver::_MakeEmpty() 153 { 154 for (uint32 i = 0; i < fSolutions.size(); i++) { 155 delete fSolutions[i]; 156 } 157 } 158 159 160 void 161 SudokuSolver::SetTo(SudokuField* field) 162 { 163 fField = field; 164 } 165 166 167 void 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 223 SudokuSolver::CountSolutions() 224 { 225 return fSolutions.size(); 226 } 227 228 229 SudokuField* 230 SudokuSolver::SolutionAt(uint32 index) 231 { 232 return fSolutions[index]; 233 } 234 235