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