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