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
SudokuGenerator()24 SudokuGenerator::SudokuGenerator()
25 {
26 }
27
28
~SudokuGenerator()29 SudokuGenerator::~SudokuGenerator()
30 {
31 }
32
33
34 bool
_HasOnlyOneSolution(SudokuField & field)35 SudokuGenerator::_HasOnlyOneSolution(SudokuField& field)
36 {
37 SudokuSolver solver(&field);
38 solver.ComputeSolutions();
39
40 return solver.CountSolutions() == 1;
41 }
42
43
44 void
_Progress(BMessenger progress,const char * text,float percent)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
Generate(SudokuField * target,uint32 fieldsLeft,BMessenger progress,volatile bool * quit)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