00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include "puzzle.h"
00022 #include "generator.h"
00023 #include "history.h"
00024 #include <string.h>
00025 #include <assert.h>
00026
00027 using namespace Sudoku;
00028
00029
00030
00031
00032
00033 Numbers::Numbers(const char* dump) :
00034 numbers_dump()
00035 {
00036 load_from_dump(dump);
00037
00038 assert(!numbers_dump);
00039 }
00040
00041
00042 Numbers::~Numbers()
00043 {
00044 delete[] numbers_dump;
00045 }
00046
00047
00048 const char* Numbers::get_dump() const
00049 {
00050 if (!numbers_dump)
00051 numbers_dump = new char[SDIM + DIM];
00052 assert(numbers_dump);
00053
00054 char* dump = numbers_dump;
00055 unsigned int n;
00056 for (unsigned int row = 0; row < DIM; ++row, *dump++ = '+')
00057 for (unsigned int col = 0; col < DIM; ++col, ++dump)
00058 *dump = (n = get(Pos(col, row))) ? '0' + n : '_';
00059 *--dump = 0;
00060
00061 return numbers_dump;
00062 }
00063
00064
00065 void Numbers::reset()
00066 {
00067 for (unsigned int i = 0; i < SDIM; ++i)
00068 content[i] = 0;
00069 }
00070
00071
00072 void Numbers::set_contents(const Numbers& sudoku, const bool marks[SDIM])
00073 {
00074 for (unsigned int i = 0; i < SDIM; ++i)
00075 if (marks[i])
00076 content[i] = sudoku.get(i);
00077 else
00078 content[i] = 0;
00079 }
00080
00081
00082 void Numbers::set(Pos pos, unsigned int number)
00083 {
00084 assert(pos <= Pos::last());
00085 assert(0 <= number && number <= DIM);
00086 content[pos] = number;
00087 }
00088
00089
00090 unsigned int Numbers::get(Pos pos) const
00091 {
00092 assert(pos <= Pos::last());
00093 assert(0 <= content[pos] && content[pos] <= DIM);
00094 return content[pos];
00095 }
00096
00097
00098 void Numbers::load_from_dump(const char* dump)
00099 {
00100 reset();
00101
00102 if (dump)
00103 for (unsigned int i = 0; *dump && *dump != ':' && i < SDIM; ++i, ++dump)
00104 if (*dump == '+')
00105 --i;
00106 else if (*dump > '0' && *dump - '0' <= DIM)
00107 content[i] = *dump - '0';
00108 }
00109
00110
00111
00112
00113
00114 Puzzle::Puzzle(const char* dump) :
00115 puzzle_dump()
00116 {
00117 load_from_dump(dump);
00118
00119 assert(!puzzle_dump);
00120 }
00121
00122
00123 Puzzle::Puzzle(unsigned int givens_count, bool symmetric) :
00124 puzzle_dump()
00125 {
00126 if (givens_count == 0)
00127 clear_givens();
00128 else
00129 generate(givens_count, symmetric);
00130
00131 assert(!puzzle_dump);
00132 }
00133
00134
00135 Puzzle::~Puzzle()
00136 {
00137 delete[] puzzle_dump;
00138 }
00139
00140
00141 const char* Puzzle::get_dump() const
00142 {
00143 if (!puzzle_dump)
00144 puzzle_dump = new char[3 * (SDIM + DIM)];
00145 assert(puzzle_dump);
00146
00147
00148 strcpy(puzzle_dump, givens.get_dump());
00149 if (!untouched())
00150 {
00151
00152 strcat(puzzle_dump, ":");
00153 strcat(puzzle_dump, Numbers::get_dump());
00154
00155
00156 strcat(puzzle_dump, ":");
00157 strcat(puzzle_dump, marks.get_dump());
00158 }
00159
00160 return puzzle_dump;
00161 }
00162
00163
00164 void Puzzle::reset()
00165 {
00166 reset(true);
00167 }
00168
00169
00170 void Puzzle::reset(bool clear_marks)
00171 {
00172 unsigned int i;
00173
00174
00175 for (i = 0; i < SDIM; ++i)
00176 Numbers::set(i, givens.get(i));
00177
00178
00179 for (i = 0; i < SDIM; ++i)
00180 compute_numbers(i);
00181
00182
00183 if (clear_marks)
00184 marks.reset();
00185 }
00186
00187
00188 void Puzzle::set(Pos pos, unsigned int number)
00189 {
00190 assert(pos <= Pos::last());
00191 assert(0 <= number && number <= DIM);
00192
00193 if (!given(pos) && get(pos) != number)
00194 {
00195 Numbers::set(pos, number);
00196
00197
00198 for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
00199 if (p.interacts_with(pos))
00200 compute_numbers(p);
00201 }
00202 }
00203
00204
00205 void Puzzle::load_from_dump(const char* dump)
00206 {
00207
00208 givens.load_from_dump(dump);
00209 reset();
00210
00211
00212 if (dump)
00213 dump = strchr(dump, ':');
00214 if (dump)
00215 {
00216 Numbers numbers(++dump);
00217 for (unsigned int i = 0; i < SDIM; ++i)
00218 if (numbers.get(i) != 0)
00219 set(i, numbers.get(i));
00220 }
00221
00222
00223 if (dump)
00224 dump = strchr(dump, ':');
00225 if (dump)
00226 marks.load_from_dump(++dump);
00227 }
00228
00229
00230 void Puzzle::generate(unsigned int givens_count, bool symmetric)
00231 {
00232
00233 for (bool found = false; !found;)
00234 {
00235 Generator generator(*this, givens_count, symmetric, symmetric ? 500 : 2000);
00236 generator.find_next_solution();
00237 found = generator.solution_is_valid();
00238 }
00239 reset();
00240 }
00241
00242
00243 void Puzzle::set_givens(const Numbers& sudoku, const bool given_marks[SDIM])
00244 {
00245 givens.set_contents(sudoku, given_marks);
00246 reset();
00247 }
00248
00249
00250 void Puzzle::clear_givens()
00251 {
00252 givens.reset();
00253 reset();
00254 }
00255
00256
00257 bool Puzzle::untouched() const
00258 {
00259 for (unsigned int i = 0; i < SDIM; ++i)
00260 if (get(i) != givens.get(i))
00261 return false;
00262
00263 return true;
00264 }
00265
00266
00267 bool Puzzle::given(Pos pos) const
00268 {
00269 assert(pos <= Pos::last());
00270 return givens.get(pos) != 0;
00271 }
00272
00273
00274 bool Puzzle::error(Pos pos) const
00275 {
00276 assert(pos <= Pos::last());
00277 return !correct(pos);
00278 }
00279
00280
00281 bool Puzzle::ambiguous(Pos pos) const
00282 {
00283 assert(pos <= Pos::last());
00284 return get(pos) != 0 && count[pos] > 1;
00285 }
00286
00287
00288 bool Puzzle::solved() const
00289 {
00290 for (unsigned int i = 0; i < SDIM; ++i)
00291 if (get(i) == 0 || !correct(i))
00292 return false;
00293
00294 return true;
00295 }
00296
00297
00298 bool Puzzle::marked(Pos pos) const
00299 {
00300 assert(pos <= Pos::last());
00301 return marks.get(pos) != 0;
00302 }
00303
00304
00305 void Puzzle::toggle_mark(Pos pos)
00306 {
00307 assert(pos <= Pos::last());
00308 marks.set(pos, marks.get(pos) != 0 ? 0 : 1);
00309 }
00310
00311
00312 Pos Puzzle::next_cell(Pos pos) const
00313 {
00314 unsigned int min_count = DIM+1, min_index = SDIM, i;
00315
00316 for (pos = (pos+1)%SDIM, i = 0; i < SDIM; ++i, pos = (pos+1)%SDIM)
00317 if (get(pos) == 0 && count[pos] < min_count)
00318 min_count = count[pos], min_index = pos;
00319
00320 return min_index;
00321 }
00322
00323
00324 unsigned int Puzzle::next_number(Pos pos) const
00325 {
00326 assert(pos <= Pos::last());
00327 unsigned int n = get(pos);
00328 unsigned int i;
00329
00330 if (!given(pos))
00331 for (n = (n+1)%(DIM+1), i = 0; i < DIM+1; ++i, n = (n+1)%(DIM+1))
00332 if (numbers[pos][n])
00333 break;
00334
00335 return n;
00336 }
00337
00338
00339 unsigned int Puzzle::numbers_count(Pos pos) const
00340 {
00341 assert(pos <= Pos::last());
00342 return count[pos];
00343 }
00344
00345
00346 bool Puzzle::possible_number(Pos pos, unsigned int number) const
00347 {
00348 assert(pos <= Pos::last());
00349 assert(0 < number && number <= DIM);
00350 return numbers[pos][number];
00351 }
00352
00353
00354 void Puzzle::compute_numbers(Pos pos)
00355 {
00356 assert(pos <= Pos::last());
00357 unsigned int i;
00358
00359
00360 for (i = 1; i <= DIM; ++i)
00361 numbers[pos][i] = true;
00362
00363
00364 for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
00365 if (p.interacts_with(pos))
00366 numbers[pos][get(p)] = false;
00367
00368
00369 count[pos] = 0;
00370 for (i = 1; i <= DIM; ++i)
00371 if (numbers[pos][i])
00372 ++count[pos];
00373
00374
00375 numbers[pos][0] = true;
00376 }
00377
00378
00379 bool Puzzle::correct(Pos pos) const
00380 {
00381 assert(pos <= Pos::last());
00382 return count[pos] != 0 && numbers[pos][get(pos)];
00383 }
00384
00385
00386
00387
00388
00389 PuzzleGame::PuzzleGame(const char* dump) :
00390 Puzzle(dump), pos(Pos::center()), history(new History())
00391 {
00392 assert(history);
00393 }
00394
00395
00396 PuzzleGame::PuzzleGame(unsigned int givens_count, bool symmetric) :
00397 Puzzle(givens_count, symmetric), pos(Pos::center()), history(new History())
00398 {
00399 assert(history);
00400 }
00401
00402
00403 PuzzleGame::~PuzzleGame()
00404 {
00405 delete history;
00406 }
00407
00408
00409 void PuzzleGame::reset()
00410 {
00411 reset(true);
00412 }
00413
00414
00415 void PuzzleGame::reset(bool clear_marks)
00416 {
00417 Puzzle::reset(clear_marks);
00418 if (history)
00419 history->reset();
00420 }
00421
00422
00423 void PuzzleGame::set_with_history(unsigned int number)
00424 {
00425 if (history && !given(pos) && get(pos) != number)
00426 {
00427 history->add(new SetMove(*this, number));
00428 history->current()->execute();
00429 }
00430 else
00431 set(pos, number);
00432 }
00433
00434
00435 Pos PuzzleGame::get_pos() const
00436 {
00437 return pos;
00438 }
00439
00440
00441 void PuzzleGame::set_pos(Pos new_pos)
00442 {
00443 pos = new_pos;
00444 }
00445
00446
00447 void PuzzleGame::backward()
00448 {
00449 if (history->movesExecuted())
00450 {
00451 history->current()->takeBack();
00452 history->backward();
00453 }
00454 }
00455
00456
00457 void PuzzleGame::forward()
00458 {
00459 if (history->movesToExecute())
00460 {
00461 history->forward();
00462 history->current()->execute();
00463 }
00464 }