1 /* 2 * Copyright 2007-2010, 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("%lu", 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 void 255 SudokuField::SetHintMaskAt(uint32 x, uint32 y, uint32 hintMask) 256 { 257 _FieldAt(x, y).hint_mask = hintMask; 258 } 259 260 261 uint32 262 SudokuField::HintMaskAt(uint32 x, uint32 y) const 263 { 264 return _FieldAt(x, y).hint_mask; 265 } 266 267 268 void 269 SudokuField::SetValidMaskAt(uint32 x, uint32 y, uint32 validMask) 270 { 271 _FieldAt(x, y).valid_mask = validMask & fMaxMask; 272 } 273 274 275 uint32 276 SudokuField::ValidMaskAt(uint32 x, uint32 y) const 277 { 278 return _FieldAt(x, y).valid_mask; 279 } 280 281 282 void 283 SudokuField::SetFlagsAt(uint32 x, uint32 y, uint32 flags) 284 { 285 _FieldAt(x, y).flags = flags; 286 } 287 288 289 uint32 290 SudokuField::FlagsAt(uint32 x, uint32 y) const 291 { 292 return _FieldAt(x, y).flags; 293 } 294 295 296 void 297 SudokuField::SetValueAt(uint32 x, uint32 y, uint32 value, bool setSolved) 298 { 299 _FieldAt(x, y).value = value; 300 _FieldAt(x, y).hint_mask = 0; 301 _UpdateValidMaskChanged(x, y, setSolved); 302 } 303 304 305 uint32 306 SudokuField::ValueAt(uint32 x, uint32 y) const 307 { 308 return _FieldAt(x, y).value; 309 } 310 311 312 bool 313 SudokuField::_ValidValueAt(uint32 x, uint32 y) const 314 { 315 uint32 value = _FieldAt(x, y).value; 316 if (!value) 317 return false; 318 319 value = 1UL << (value - 1); 320 return (_FieldAt(x, y).valid_mask & value) != 0; 321 } 322 323 324 void 325 SudokuField::_ComputeValidMask(uint32 x, uint32 y, bool setSolved) 326 { 327 if (ValueAt(x, y)) 328 return; 329 330 // check row 331 332 uint32 foundMask = 0; 333 for (uint32 i = 0; i < fSize; i++) { 334 uint32 value = ValueAt(i, y); 335 if (value && _ValidValueAt(i, y)) 336 foundMask |= 1UL << (value - 1); 337 } 338 339 // check column 340 341 for (uint32 i = 0; i < fSize; i++) { 342 uint32 value = ValueAt(x, i); 343 if (value && _ValidValueAt(x, i)) 344 foundMask |= 1UL << (value - 1); 345 } 346 347 // check block 348 349 uint32 offsetX = x / fBlockSize * fBlockSize; 350 uint32 offsetY = y / fBlockSize * fBlockSize; 351 352 for (uint32 partY = 0; partY < fBlockSize; partY++) { 353 for (uint32 partX = 0; partX < fBlockSize; partX++) { 354 uint32 value = ValueAt(partX + offsetX, partY + offsetY); 355 if (value && _ValidValueAt(partX + offsetX, partY + offsetY)) 356 foundMask |= 1UL << (value - 1); 357 } 358 } 359 360 SetValidMaskAt(x, y, ~foundMask); 361 362 if (setSolved) { 363 // find the one set bit, if not more 364 uint32 value = 0; 365 for (uint32 i = 0; i < fSize; i++) { 366 if ((foundMask & (1UL << i)) == 0) { 367 if (value != 0) { 368 value = 0; 369 break; 370 } 371 372 value = i + 1; 373 } 374 } 375 if (value != 0) 376 SetValueAt(x, y, value, true); 377 } 378 } 379 380 381 void 382 SudokuField::_UpdateValidMaskChanged(uint32 x, uint32 y, bool setSolved) 383 { 384 // update row 385 386 for (uint32 i = 0; i < fSize; i++) { 387 _ComputeValidMask(i, y, setSolved); 388 } 389 390 // update column 391 392 for (uint32 i = 0; i < fSize; i++) { 393 if (i == y) 394 continue; 395 396 _ComputeValidMask(x, i, setSolved); 397 } 398 399 // update block 400 401 uint32 offsetX = x / fBlockSize * fBlockSize; 402 uint32 offsetY = y / fBlockSize * fBlockSize; 403 404 for (uint32 partY = 0; partY < fBlockSize; partY++) { 405 for (uint32 partX = 0; partX < fBlockSize; partX++) { 406 if (partX + offsetX == x || partY + offsetY == y) 407 continue; 408 409 _ComputeValidMask(partX + offsetX, partY + offsetY, setSolved); 410 } 411 } 412 } 413 414 415 const SudokuField::field& 416 SudokuField::_FieldAt(uint32 x, uint32 y) const 417 { 418 if (x >= fSize || y >= fSize) 419 debugger("field outside bounds"); 420 421 return fFields[x + y * fSize]; 422 } 423 424 425 SudokuField::field& 426 SudokuField::_FieldAt(uint32 x, uint32 y) 427 { 428 if (x >= fSize || y >= fSize) 429 debugger("field outside bounds"); 430 431 return fFields[x + y * fSize]; 432 } 433 434 435