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* 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 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 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 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 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 97 SudokuField::~SudokuField() 98 { 99 delete[] fFields; 100 } 101 102 103 status_t 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 113 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* 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 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 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 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 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 227 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 241 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 255 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 270 SudokuField::SetHintMaskAt(uint32 x, uint32 y, uint32 hintMask) 271 { 272 _FieldAt(x, y).hint_mask = hintMask; 273 } 274 275 276 uint32 277 SudokuField::HintMaskAt(uint32 x, uint32 y) const 278 { 279 return _FieldAt(x, y).hint_mask; 280 } 281 282 283 bool 284 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 291 SudokuField::SetValidMaskAt(uint32 x, uint32 y, uint32 validMask) 292 { 293 _FieldAt(x, y).valid_mask = validMask & fMaxMask; 294 } 295 296 297 uint32 298 SudokuField::ValidMaskAt(uint32 x, uint32 y) const 299 { 300 return _FieldAt(x, y).valid_mask; 301 } 302 303 304 bool 305 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 312 SudokuField::SetFlagsAt(uint32 x, uint32 y, uint32 flags) 313 { 314 _FieldAt(x, y).flags = flags; 315 } 316 317 318 uint32 319 SudokuField::FlagsAt(uint32 x, uint32 y) const 320 { 321 return _FieldAt(x, y).flags; 322 } 323 324 325 bool 326 SudokuField::IsInitialValue(uint32 x, uint32 y) const 327 { 328 return (_FieldAt(x, y).flags & kInitialValue) != 0; 329 } 330 331 332 void 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 342 SudokuField::ValueAt(uint32 x, uint32 y) const 343 { 344 return _FieldAt(x, y).value; 345 } 346 347 348 bool 349 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 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 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& 452 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& 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