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