00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #define USE_RAND
00022 #include "solver.h"
00023 #include "backtrack.h"
00024 #include "puzzle.h"
00025 #include <assert.h>
00026
00027 using namespace Sudoku;
00028 using namespace BackTrack;
00029
00030
00031
00032
00033
00034 Solver::Solver(Puzzle& puzzle, bool random_init, unsigned int max_iter) :
00035 Algorithm(*this, max_iter), puzzle(puzzle), random_init(random_init)
00036 {
00037 free_count = 0;
00038 for (Pos p = Pos::first(); p <= Pos::last(); p = p.next())
00039 if (!puzzle.given(p))
00040 ++free_count;
00041 }
00042
00043
00044 void Solver::set_first_at(unsigned int level)
00045 {
00046 assert(level < free_count);
00047 const Pos p = puzzle.next_cell();
00048 assert(p <= Pos::last());
00049
00050 free_list[level] = p;
00051 puzzle.set(p, 0);
00052
00053 if (level == 0)
00054 random = random_init;
00055
00056 unsigned int i, count = puzzle.numbers_count(p);
00057 if (count != 0)
00058 {
00059 puzzle.set(p, puzzle.next_number(p));
00060
00061 if (random)
00062 for (count = rand(count), i = 0; i < count; ++i)
00063 puzzle.set(p, puzzle.next_number(p));
00064 }
00065 else
00066 puzzle.set(p, 1);
00067 }
00068
00069
00070 void Solver::set_next_at(unsigned int level)
00071 {
00072 assert(level < free_count);
00073 Pos p = free_list[level];
00074 unsigned int n = puzzle.next_number(p);
00075 if (n != 0)
00076 puzzle.set(p, n);
00077 }
00078
00079
00080 void Solver::reset_at(unsigned int level)
00081 {
00082 assert(level < free_count);
00083 puzzle.set(free_list[level], 0);
00084 random = false;
00085 }
00086
00087
00088 bool Solver::is_last_at(unsigned int level) const
00089 {
00090 assert(level < free_count);
00091 return puzzle.next_number(free_list[level]) == 0;
00092 }
00093
00094
00095 bool Solver::is_valid_at(int level) const
00096 {
00097 assert(level < int(free_count));
00098 if (level < 0)
00099 return puzzle.solved();
00100 return !puzzle.error(free_list[level]);
00101 }
00102
00103
00104 bool Solver::is_last_level(int level) const
00105 {
00106 return level >= int(free_count) - 1;
00107 }