src/apps/sudoku/SudokuGenerator.cpp

   1 /*
   2  * Copyright 2007-2012, Axel Dörfler, axeld@pinc-software.de.
   3  * Distributed under the terms of the MIT License.
   4  */
   5
   6
   7 #include "SudokuGenerator.h"
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12
  13 #include <Catalog.h>
  14
  15 #include "ProgressWindow.h"
  16 #include "SudokuField.h"
  17 #include "SudokuSolver.h"
  18
  19
  20 #undef B_TRANSLATION_CONTEXT
  21 #define B_TRANSLATION_CONTEXT "SudokuGenerator"
  22
  23
  24 SudokuGenerator::SudokuGenerator()
  25 {
  26 }
  27
  28
  29 SudokuGenerator::~SudokuGenerator()
  30 {
  31 }
  32
  33
  34 bool
  35 SudokuGenerator::_HasOnlyOneSolution(SudokuField& field)
  36 {
  37         SudokuSolver solver(&field);
  38         solver.ComputeSolutions();
  39
  40         return solver.CountSolutions() == 1;
  41 }
  42
  43
  44 void
  45 SudokuGenerator::_Progress(BMessenger progress, const char* text,
  46         float percent)
  47 {
  48         BMessage update(kMsgProgressStatusUpdate);
  49         if (text)
  50                 update.AddString("message", text);
  51         update.AddFloat("percent", percent);
  52         progress.SendMessage(&update);
  53 }
  54
  55
  56 void
  57 SudokuGenerator::Generate(SudokuField* target, uint32 fieldsLeft,
  58         BMessenger progress, volatile bool *quit)
  59 {
  60         // first step: generate a solved field - random brute force style
  61
  62         SudokuField field(target->BlockSize());
  63         uint32 inputCount = field.Size() * field.Size() / 3;
  64         _Progress(progress, B_TRANSLATE("Creating solvable field"), 5.f);
  65
  66         while (!*quit) {
  67                 field.Reset();
  68
  69                 // generate input field
  70
  71                 uint32 validMask = 0;
  72
  73                 for (uint32 i = 0; i < inputCount; i++) {
  74                         uint32 x;
  75                         uint32 y;
  76                         do {
  77                                 x = rand() % field.Size();
  78                                 y = rand() % field.Size();
  79                         } while (!*quit && field.ValueAt(x, y) != 0);
  80
  81                         validMask = field.ValidMaskAt(x, y);
  82                         if (validMask == 0)
  83                                 break;
  84
  85                         uint32 value;
  86                         do {
  87                                 value = rand() % field.Size();
  88                         } while (!*quit && (validMask & (1UL << value)) == 0);
  89
  90                         field.SetValueAt(x, y, value + 1);
  91                 }
  92
  93                 if (validMask == 0)
  94                         continue;
  95
  96                 // try to solve it
  97
  98                 SudokuSolver solver(&field);
  99                 solver.ComputeSolutions();
 100                 if (solver.CountSolutions() > 0) {
 101                         // choose a random solution
 102                         field.SetTo(solver.SolutionAt(rand() % solver.CountSolutions()));
 103                         break;
 104                 }
 105         }
 106
 107         if (*quit)
 108                 return;
 109
 110         // next step: try to remove as many fields as possible (and wished)
 111         // that still have only a single solution
 112
 113         int32 removeCount = field.Size() * field.Size() - fieldsLeft;
 114         bool tried[field.Size() * field.Size()];
 115         int32 tries = field.Size() * field.Size() * 3 / 4;
 116         memset(tried, 0, sizeof(tried));
 117         _Progress(progress, B_TRANSLATE("Searching for removable values"), 30.f);
 118
 119         while (!*quit && removeCount > 0 && tries-- > 0) {
 120                 SudokuField copy(field);
 121                 uint32 x;
 122                 uint32 y;
 123                 do {
 124                         x = rand() % field.Size();
 125                         y = rand() % field.Size();
 126                 } while (copy.ValueAt(x, y) == 0 || tried[x + y * field.Size()]);
 127
 128                 tried[x + y * field.Size()] = true;
 129                 copy.SetValueAt(x, y, 0);
 130
 131                 if (_HasOnlyOneSolution(copy)) {
 132                         _Progress(progress, NULL, 100.f - (70.f * removeCount / 70.f));
 133                         field.SetTo(&copy);
 134                         removeCount--;
 135                 }
 136         }
 137
 138         if (*quit)
 139                 return;
 140
 141         if (tries <= 0) {
 142                 puts("check all remove");
 143                 for (uint32 y = 0; y < field.Size(); y++) {
 144                         for (uint32 x = 0; x < field.Size(); x++) {
 145                                 if (tried[x + y * field.Size()])
 146                                         continue;
 147
 148                                 SudokuField copy(field);
 149                                 copy.SetValueAt(x, y, 0);
 150
 151                                 if (_HasOnlyOneSolution(copy)) {
 152                                         _Progress(progress, NULL,
 153                                                 100.f - (70.f * removeCount / 70.f));
 154                                         field.SetTo(&copy);
 155
 156                                         if (--removeCount <= 0 || *quit)
 157                                                 break;
 158                                 }
 159                         }
 160
 161                         if (removeCount <= 0 || *quit)
 162                                 break;
 163                 }
 164                 printf("  remove count = %" B_PRId32 "\n", removeCount);
 165         }
 166
 167         // set the remaining values to be initial values
 168
 169         for (uint32 y = 0; y < field.Size(); y++) {
 170                 for (uint32 x = 0; x < field.Size(); x++) {
 171                         if (field.ValueAt(x, y))
 172                                 field.SetFlagsAt(x, y, kInitialValue);
 173                 }
 174         }
 175
 176         if (*quit)
 177                 return;
 178
 179         target->SetTo(&field);
 180 }
 181