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