src/apps/sudoku/SudokuSolver.cpp

   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