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 "generator.h"
00023 #include "solver.h"
00024 #include "backtrack.h"
00025 #include "puzzle.h"
00026 #include <assert.h>
00027
00028 using namespace Sudoku;
00029 using namespace BackTrack;
00030
00031
00032
00033
00034
00035 Generator::Generator(Puzzle& puzzle, unsigned int givens_count,
00036 bool symmetric, unsigned int max_iter) :
00037 Algorithm(*this, max_iter), puzzle(puzzle), symmetric(symmetric)
00038 {
00039 assert(givens_count <= SDIM);
00040
00041
00042 for (bool found = false; !found;)
00043 {
00044 sudoku.reset();
00045 Solver solver(sudoku, true);
00046 solver.find_next_solution();
00047 found = solver.solution_is_valid();
00048 }
00049
00050
00051 pos_count = SDIM;
00052 free_count = SDIM - givens_count;
00053 free_center = symmetric && pos_count % 2 != 0 && free_count % 2 != 0;
00054 if (symmetric)
00055 pos_count /= 2, free_count /= 2;
00056
00057
00058 bool list[pos_count];
00059 unsigned int p, i, c;
00060 for (p = 0; p < pos_count; ++p)
00061 list[p] = true;
00062 for (i = 0; i < pos_count; ++i)
00063 {
00064 c = rand(pos_count - i) + 1;
00065 for (p = 0; p < pos_count; ++p)
00066 if (list[p])
00067 if (--c == 0)
00068 break;
00069 assert(p < pos_count);
00070 list[p] = false;
00071 pos_list[i] = p;
00072 }
00073 }
00074
00075
00076 void Generator::set_first_at(unsigned int level)
00077 {
00078 assert(level < free_count);
00079 free_list[level] = 0;
00080 }
00081
00082
00083 void Generator::set_next_at(unsigned int level)
00084 {
00085 assert(level < free_count);
00086 ++free_list[level];
00087 }
00088
00089
00090 void Generator::reset_at(unsigned int level)
00091 {
00092 }
00093
00094
00095 bool Generator::is_last_at(unsigned int level) const
00096 {
00097 assert(level < free_count);
00098 return free_list[level] >= pos_count - 1;
00099 }
00100
00101
00102 bool Generator::is_valid_at(int level) const
00103 {
00104 assert(level < int(free_count));
00105
00106
00107 if (level > 0 && free_list[level] <= free_list[level - 1])
00108 return false;
00109 if (level >= 0 && free_list[level] > pos_count - (free_count - level))
00110 return false;
00111
00112
00113 bool given_marks[SDIM];
00114 int i;
00115 for (i = 0; i < SDIM; ++i)
00116 given_marks[i] = true;
00117 for (i = 0; i <= level; ++i)
00118 {
00119 Pos p = pos_list[free_list[i]];
00120 given_marks[p] = false;
00121 if (symmetric)
00122 given_marks[p.symmetric()] = false;
00123 }
00124 if (free_center)
00125 given_marks[Pos::center()] = false;
00126
00127
00128 puzzle.set_givens(sudoku, given_marks);
00129 Solver solver(puzzle);
00130 solver.find_next_solution();
00131 assert(solver.solution_is_valid());
00132 solver.find_next_solution();
00133 return !solver.solution_is_valid();
00134 }
00135
00136
00137 bool Generator::is_last_level(int level) const
00138 {
00139 return level >= int(free_count) - 1;
00140 }