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 "SudokuField.h"
8
9 #include <new>
10 #include <stdio.h>
11 #include <string.h>
12
13 #include <Message.h>
14 #include <OS.h>
15
16
17 const char*
mask(uint32 set)18 mask(uint32 set)
19 {
20 static char text[64];
21 uint32 i = 0;
22 for (int32 number = 9; number > 0; number--) {
23 text[i++] = set & (1UL << (number - 1)) ? number + '0' : '-';
24 }
25
26 text[i] = '\0';
27 return text;
28 }
29
30
31 // #pragma mark -
32
33
field()34 SudokuField::field::field()
35 :
36 hint_mask(0),
37 valid_mask(~0),
38 flags(0),
39 value(0)
40 {
41 }
42
43
44 // #pragma mark -
45
46
SudokuField(uint32 size)47 SudokuField::SudokuField(uint32 size)
48 :
49 fSize(size * size),
50 fBlockSize(size)
51 {
52 fFields = new (std::nothrow) field[fSize * fSize];
53 fMaxMask = (1UL << fSize) - 1;
54 }
55
56
SudokuField(const BMessage * archive)57 SudokuField::SudokuField(const BMessage* archive)
58 {
59 if (archive->FindInt32("block size", (int32*)&fBlockSize) != B_OK)
60 return;
61
62 fSize = fBlockSize * fBlockSize;
63 fMaxMask = (1UL << fSize) - 1;
64
65 uint32 count = fSize * fSize;
66 fFields = new (std::nothrow) field[count];
67 if (fFields == NULL)
68 return;
69
70 for (uint32 i = 0; i < count; i++) {
71 struct field& field = fFields[i];
72
73 if (archive->FindInt32("value", i, (int32*)&field.value) != B_OK
74 || archive->FindInt32("valid mask", i,
75 (int32*)&field.valid_mask) != B_OK
76 || archive->FindInt32("hint mask", i,
77 (int32*)&field.hint_mask) != B_OK
78 || archive->FindInt32("flags", i, (int32*)&field.flags) != B_OK)
79 break;
80 }
81 }
82
83
SudokuField(const SudokuField & other)84 SudokuField::SudokuField(const SudokuField& other)
85 : BArchivable(other)
86 {
87 fSize = other.fSize;
88 fBlockSize = other.fBlockSize;
89 fMaxMask = other.fMaxMask;
90
91 fFields = new (std::nothrow) field[fSize * fSize];
92 if (fFields != NULL)
93 memcpy(fFields, other.fFields, sizeof(field) * fSize * fSize);
94 }
95
96
~SudokuField()97 SudokuField::~SudokuField()
98 {
99 delete[] fFields;
100 }
101
102
103 status_t
InitCheck()104 SudokuField::InitCheck()
105 {
106 if (fBlockSize == 0)
107 return B_BAD_VALUE;
108 return fFields == NULL ? B_NO_MEMORY : B_OK;
109 }
110
111
112 status_t
Archive(BMessage * archive,bool deep) const113 SudokuField::Archive(BMessage* archive, bool deep) const
114 {
115 status_t status = BArchivable::Archive(archive, deep);
116 if (status == B_OK)
117 archive->AddInt32("block size", fBlockSize);
118 if (status < B_OK)
119 return status;
120
121 uint32 count = fSize * fSize;
122 for (uint32 i = 0; i < count && status == B_OK; i++) {
123 struct field& field = fFields[i];
124 status = archive->AddInt32("value", field.value);
125 if (status == B_OK)
126 status = archive->AddInt32("valid mask", field.valid_mask);
127 if (status == B_OK)
128 status = archive->AddInt32("hint mask", field.hint_mask);
129 if (status == B_OK)
130 status = archive->AddInt32("flags", field.flags);
131 }
132
133 return status;
134 }
135
136
137 /*static*/ SudokuField*
Instantiate(BMessage * archive)138 SudokuField::Instantiate(BMessage* archive)
139 {
140 if (!validate_instantiation(archive, "SudokuField"))
141 return NULL;
142
143 return new SudokuField(archive);
144 }
145
146
147 void
Reset()148 SudokuField::Reset()
149 {
150 for (uint32 y = 0; y < fSize; y++) {
151 for (uint32 x = 0; x < fSize; x++) {
152 struct field& field = _FieldAt(x, y);
153 field.value = 0;
154 field.flags = 0;
155 field.hint_mask = 0;
156 field.valid_mask = fMaxMask;
157 }
158 }
159 }
160
161
162 status_t
SetTo(char base,const char * data)163 SudokuField::SetTo(char base, const char* data)
164 {
165 if (data != NULL && strlen(data) < fSize * fSize)
166 return B_BAD_VALUE;
167
168 Reset();
169
170 if (data == NULL)
171 return B_OK;
172
173 uint32 i = 0;
174
175 for (uint32 y = 0; y < fSize; y++) {
176 for (uint32 x = 0; x < fSize; x++) {
177 uint32 value = data[i++] - base;
178 if (value) {
179 struct field& field = _FieldAt(x, y);
180 field.value = value;
181 field.flags = kInitialValue;
182 }
183 }
184 }
185
186 for (uint32 y = 0; y < fSize; y++) {
187 for (uint32 x = 0; x < fSize; x++) {
188 _ComputeValidMask(x, y, false);
189 }
190 }
191
192 return B_OK;
193 }
194
195
196 void
SetTo(const SudokuField * field)197 SudokuField::SetTo(const SudokuField* field)
198 {
199 if (field == NULL) {
200 Reset();
201 return;
202 }
203
204 for (uint32 y = 0; y < fSize; y++) {
205 for (uint32 x = 0; x < fSize; x++) {
206 _FieldAt(x, y) = field->_FieldAt(x, y);
207 }
208 }
209 }
210
211
212 void
Dump()213 SudokuField::Dump()
214 {
215 for (uint32 y = 0; y < fSize; y++) {
216 for (uint32 x = 0; x < fSize; x++) {
217 if (x != 0 && x % fBlockSize == 0)
218 putchar(' ');
219 printf("%" B_PRIu32, ValueAt(x, y));
220 }
221 putchar('\n');
222 }
223 }
224
225
226 bool
IsSolved() const227 SudokuField::IsSolved() const
228 {
229 for (uint32 y = 0; y < fSize; y++) {
230 for (uint32 x = 0; x < fSize; x++) {
231 if (!_ValidValueAt(x, y))
232 return false;
233 }
234 }
235
236 return true;
237 }
238
239
240 bool
IsEmpty() const241 SudokuField::IsEmpty() const
242 {
243 for (uint32 y = 0; y < fSize; y++) {
244 for (uint32 x = 0; x < fSize; x++) {
245 if (ValueAt(x, y) != 0)
246 return false;
247 }
248 }
249
250 return true;
251 }
252
253
254 bool
IsValueCompleted(uint32 value) const255 SudokuField::IsValueCompleted(uint32 value) const
256 {
257 uint32 count = 0;
258 for (uint32 y = 0; y < fSize; y++) {
259 for (uint32 x = 0; x < fSize; x++) {
260 if (ValueAt(x, y) == value)
261 count++;
262 }
263 }
264
265 return count == Size();
266 }
267
268
269 void
SetHintMaskAt(uint32 x,uint32 y,uint32 hintMask)270 SudokuField::SetHintMaskAt(uint32 x, uint32 y, uint32 hintMask)
271 {
272 _FieldAt(x, y).hint_mask = hintMask;
273 }
274
275
276 uint32
HintMaskAt(uint32 x,uint32 y) const277 SudokuField::HintMaskAt(uint32 x, uint32 y) const
278 {
279 return _FieldAt(x, y).hint_mask;
280 }
281
282
283 bool
HasHint(uint32 x,uint32 y,uint32 value) const284 SudokuField::HasHint(uint32 x, uint32 y, uint32 value) const
285 {
286 return (_FieldAt(x, y).hint_mask & (1UL << (value - 1))) != 0;
287 }
288
289
290 void
SetValidMaskAt(uint32 x,uint32 y,uint32 validMask)291 SudokuField::SetValidMaskAt(uint32 x, uint32 y, uint32 validMask)
292 {
293 _FieldAt(x, y).valid_mask = validMask & fMaxMask;
294 }
295
296
297 uint32
ValidMaskAt(uint32 x,uint32 y) const298 SudokuField::ValidMaskAt(uint32 x, uint32 y) const
299 {
300 return _FieldAt(x, y).valid_mask;
301 }
302
303
304 bool
IsValid(uint32 x,uint32 y,uint32 value) const305 SudokuField::IsValid(uint32 x, uint32 y, uint32 value) const
306 {
307 return (_FieldAt(x, y).valid_mask & (1UL << (value - 1))) != 0;
308 }
309
310
311 void
SetFlagsAt(uint32 x,uint32 y,uint32 flags)312 SudokuField::SetFlagsAt(uint32 x, uint32 y, uint32 flags)
313 {
314 _FieldAt(x, y).flags = flags;
315 }
316
317
318 uint32
FlagsAt(uint32 x,uint32 y) const319 SudokuField::FlagsAt(uint32 x, uint32 y) const
320 {
321 return _FieldAt(x, y).flags;
322 }
323
324
325 bool
IsInitialValue(uint32 x,uint32 y) const326 SudokuField::IsInitialValue(uint32 x, uint32 y) const
327 {
328 return (_FieldAt(x, y).flags & kInitialValue) != 0;
329 }
330
331
332 void
SetValueAt(uint32 x,uint32 y,uint32 value,bool setSolved)333 SudokuField::SetValueAt(uint32 x, uint32 y, uint32 value, bool setSolved)
334 {
335 _FieldAt(x, y).value = value;
336 _FieldAt(x, y).hint_mask = 0;
337 _UpdateValidMaskChanged(x, y, setSolved);
338 }
339
340
341 uint32
ValueAt(uint32 x,uint32 y) const342 SudokuField::ValueAt(uint32 x, uint32 y) const
343 {
344 return _FieldAt(x, y).value;
345 }
346
347
348 bool
_ValidValueAt(uint32 x,uint32 y) const349 SudokuField::_ValidValueAt(uint32 x, uint32 y) const
350 {
351 uint32 value = _FieldAt(x, y).value;
352 if (!value)
353 return false;
354
355 value = 1UL << (value - 1);
356 return (_FieldAt(x, y).valid_mask & value) != 0;
357 }
358
359
360 void
_ComputeValidMask(uint32 x,uint32 y,bool setSolved)361 SudokuField::_ComputeValidMask(uint32 x, uint32 y, bool setSolved)
362 {
363 if (ValueAt(x, y))
364 return;
365
366 // check row
367
368 uint32 foundMask = 0;
369 for (uint32 i = 0; i < fSize; i++) {
370 uint32 value = ValueAt(i, y);
371 if (value && _ValidValueAt(i, y))
372 foundMask |= 1UL << (value - 1);
373 }
374
375 // check column
376
377 for (uint32 i = 0; i < fSize; i++) {
378 uint32 value = ValueAt(x, i);
379 if (value && _ValidValueAt(x, i))
380 foundMask |= 1UL << (value - 1);
381 }
382
383 // check block
384
385 uint32 offsetX = x / fBlockSize * fBlockSize;
386 uint32 offsetY = y / fBlockSize * fBlockSize;
387
388 for (uint32 partY = 0; partY < fBlockSize; partY++) {
389 for (uint32 partX = 0; partX < fBlockSize; partX++) {
390 uint32 value = ValueAt(partX + offsetX, partY + offsetY);
391 if (value && _ValidValueAt(partX + offsetX, partY + offsetY))
392 foundMask |= 1UL << (value - 1);
393 }
394 }
395
396 SetValidMaskAt(x, y, ~foundMask);
397
398 if (setSolved) {
399 // find the one set bit, if not more
400 uint32 value = 0;
401 for (uint32 i = 0; i < fSize; i++) {
402 if ((foundMask & (1UL << i)) == 0) {
403 if (value != 0) {
404 value = 0;
405 break;
406 }
407
408 value = i + 1;
409 }
410 }
411 if (value != 0)
412 SetValueAt(x, y, value, true);
413 }
414 }
415
416
417 void
_UpdateValidMaskChanged(uint32 x,uint32 y,bool setSolved)418 SudokuField::_UpdateValidMaskChanged(uint32 x, uint32 y, bool setSolved)
419 {
420 // update row
421
422 for (uint32 i = 0; i < fSize; i++) {
423 _ComputeValidMask(i, y, setSolved);
424 }
425
426 // update column
427
428 for (uint32 i = 0; i < fSize; i++) {
429 if (i == y)
430 continue;
431
432 _ComputeValidMask(x, i, setSolved);
433 }
434
435 // update block
436
437 uint32 offsetX = x / fBlockSize * fBlockSize;
438 uint32 offsetY = y / fBlockSize * fBlockSize;
439
440 for (uint32 partY = 0; partY < fBlockSize; partY++) {
441 for (uint32 partX = 0; partX < fBlockSize; partX++) {
442 if (partX + offsetX == x || partY + offsetY == y)
443 continue;
444
445 _ComputeValidMask(partX + offsetX, partY + offsetY, setSolved);
446 }
447 }
448 }
449
450
451 const SudokuField::field&
_FieldAt(uint32 x,uint32 y) const452 SudokuField::_FieldAt(uint32 x, uint32 y) const
453 {
454 if (x >= fSize || y >= fSize)
455 debugger("field outside bounds");
456
457 return fFields[x + y * fSize];
458 }
459
460
461 SudokuField::field&
_FieldAt(uint32 x,uint32 y)462 SudokuField::_FieldAt(uint32 x, uint32 y)
463 {
464 if (x >= fSize || y >= fSize)
465 debugger("field outside bounds");
466
467 return fFields[x + y * fSize];
468 }
469
470
471