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
17const char*
18mask(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
34SudokuField::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
47SudokuField::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
57SudokuField::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
84SudokuField::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
97SudokuField::~SudokuField()
98{
99	delete[] fFields;
100}
101
102
103status_t
104SudokuField::InitCheck()
105{
106	if (fBlockSize == 0)
107		return B_BAD_VALUE;
108	return fFields == NULL ? B_NO_MEMORY : B_OK;
109}
110
111
112status_t
113SudokuField::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*
138SudokuField::Instantiate(BMessage* archive)
139{
140	if (!validate_instantiation(archive, "SudokuField"))
141		return NULL;
142
143	return new SudokuField(archive);
144}
145
146
147void
148SudokuField::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
162status_t
163SudokuField::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
196void
197SudokuField::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
212void
213SudokuField::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
226bool
227SudokuField::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
240bool
241SudokuField::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
254bool
255SudokuField::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
269void
270SudokuField::SetHintMaskAt(uint32 x, uint32 y, uint32 hintMask)
271{
272	_FieldAt(x, y).hint_mask = hintMask;
273}
274
275
276uint32
277SudokuField::HintMaskAt(uint32 x, uint32 y) const
278{
279	return _FieldAt(x, y).hint_mask;
280}
281
282
283bool
284SudokuField::HasHint(uint32 x, uint32 y, uint32 value) const
285{
286	return (_FieldAt(x, y).hint_mask & (1UL << (value - 1))) != 0;
287}
288
289
290void
291SudokuField::SetValidMaskAt(uint32 x, uint32 y, uint32 validMask)
292{
293	_FieldAt(x, y).valid_mask = validMask & fMaxMask;
294}
295
296
297uint32
298SudokuField::ValidMaskAt(uint32 x, uint32 y) const
299{
300	return _FieldAt(x, y).valid_mask;
301}
302
303
304bool
305SudokuField::IsValid(uint32 x, uint32 y, uint32 value) const
306{
307	return (_FieldAt(x, y).valid_mask & (1UL << (value - 1))) != 0;
308}
309
310
311void
312SudokuField::SetFlagsAt(uint32 x, uint32 y, uint32 flags)
313{
314	_FieldAt(x, y).flags = flags;
315}
316
317
318uint32
319SudokuField::FlagsAt(uint32 x, uint32 y) const
320{
321	return _FieldAt(x, y).flags;
322}
323
324
325bool
326SudokuField::IsInitialValue(uint32 x, uint32 y) const
327{
328	return (_FieldAt(x, y).flags & kInitialValue) != 0;
329}
330
331
332void
333SudokuField::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
341uint32
342SudokuField::ValueAt(uint32 x, uint32 y) const
343{
344	return _FieldAt(x, y).value;
345}
346
347
348bool
349SudokuField::_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
360void
361SudokuField::_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
417void
418SudokuField::_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
451const SudokuField::field&
452SudokuField::_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
461SudokuField::field&
462SudokuField::_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