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(©); 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(©); 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 182