src/apps/sudoku/SudokuField.cpp

   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