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