1 #include <sys/time.h>
2 #include <stdlib.h>
3 #include <
string.h>
4 #include <iostream>
5 #include <vector>
6 #include <
string>
7 #include <
set>
8 9 class Sudoku {
10 public:
11 Sudoku(
const std::
string& question,
bool does_try_all_answers =
false): m_does_try_all_answers(does_try_all_answers), m_data(9) {
12 for (
int i = 0; i < 9; ++i) {
13 m_data[i].resize(9);
14 for (
int j = 0; j < 9; ++j) {
15 m_data[i][j] = question[i * 9 + j];
16 }
17 }
18 }
19 20 bool Solve() {
21 return Fill(0, 0);
22 }
23 24 const std::
string GiveOneAnswer()
const {
25 return m_all_answers.empty() ? "" : *m_all_answers.begin();
26 }
27 28 const std::
set<std::
string> GiveAllAnswers()
const {
29 return m_all_answers;
30 }
31 32 static const std::
string ProvideOneQuestionRandomly(
int min_filled_num = 30) {
33 std::vector<std::vector<
char> > ques(9, std::vector<
char>(9, '.'));
34 35 struct timeval cur_tv;
36 gettimeofday(&cur_tv, NULL);
37 srand(cur_tv.tv_usec);
38 39 int valid_digit_num = 0;
40 for (
int i = 0; i < 9; ++i) {
41 for (
int j = 0; j < 9; ++j) {
42 if (rand() % 81 <= min_filled_num + valid_digit_num / 6) {
43 char c = rand() % 9 + '1';
44 45 if (DoesConflict(ques, i, j, c)) {
46 int k = 0;
47 for (; k < 8; ++k) {
48 if (c == '9') {
49 c = '1';
50 }
51 if (!DoesConflict(ques, i, j, ++c)) {
52 break;
53 }
54 }
55 if (8 == k) {
56 c = '.';
57 }
58 }
59 60 valid_digit_num += ('.' != c);
61 ques[i][j] = c;
62 }
else {
63 ques[i][j] = '.';
64 }
65 }
66 }
67 68 char buf[82];
69 buf[81] = '\0';
70 for (
int i = 0; i < 9; ++i) {
71 for (
int j = 0; j < 9; ++j) {
72 buf[i * 9 + j] = ques[i][j];
73 }
74 }
75 76 Sudoku sudoku(buf);
77 sudoku.Solve();
78 if (81 == sudoku.GiveOneAnswer().size()) {
79 return buf;
80 }
else {
81 return ProvideOneQuestionRandomly(min_filled_num);
82 }
83 84 return buf;
85 }
86 87 static void PrintSudoku(
const std::
string& sudoku) {
88 if (sudoku.size() < 81) {
89 return;
90 }
91 92 for (
int i = 0; i < 9; ++i) {
93 for (
int j = 0; j < 9; ++j) {
94 if (0 != j) {
95 std::cout << " ";
96 }
97 std::cout << sudoku[i * 9 + j];
98 }
99 std::cout << std::endl;
100 }
101 }
102 103 static bool ValidateOneAnswer(
const std::
string& answer) {
104 if (answer.size() != 81) {
105 return false;
106 }
107 108 for (
int i = 0; i < 9; ++i) {
109 char hit_h[9] = { '\0' };
110 char hit_v[9] = { '\0' };
111 for (
int j = 0; j < 9; ++j) {
112 if ('.' == answer[i * 9 + j] || ++hit_h[answer[i * 9 + j] - '1'] != 1) {
//row check
113 return false;
114 }
else if ('.' == answer[j * 9 + i] || ++hit_v[answer[j * 9 + i] - '1'] != 1) {
//column check
115 return false;
116 }
117 if (0 == i % 3 && 0 == j % 3) {
//3x3 square check
118 char hit_m[9] = { '\0' };
119 for (
int i2 = i; i2 < i + 3; ++i2) {
120 for (
int j2 = j; j2 < j + 3; ++j2) {
121 if ('.' == answer[i2 * 9 + j2] || ++hit_m[answer[i2 * 9 + j2] - '1'] != 1) {
122 return false;
123 }
124 }
125 }
126 }
127 }
128 }
129 return true;
130 }
131 132 private:
133 void AddOneAnswer() {
134 char buf[82];
135 buf[81] = '\0';
136 137 for (
int i = 0; i < 9; ++i) {
138 for (
int j = 0; j < 9; ++j) {
139 buf[i * 9 + j] = m_data[i][j];
140 }
141 }
142 143 m_all_answers.insert(buf);
144 }
145 146 static bool DoesConflict(
const std::vector<std::vector<
char> >& data,
int i,
int j,
char digit) {
147 for (
int k = 0; k < 9; ++k) {
148 if (digit == data[i][k]) {
149 return true;
150 }
151 if (digit == data[k][j]) {
152 return true;
153 }
154 }
155 156 int i0 = i - i % 3;
157 int j0 = j - j % 3;
158 for (
int i2 = i0; i2 < i0 + 3; ++i2) {
159 for (
int j2 = j0; j2 < j0 + 3; ++j2) {
160 if (digit == data[i2][j2]) {
161 return true;
162 }
163 }
164 }
165 166 return false;
167 }
168 169 bool Fill(
int i,
int j) {
170 for (; i < 9; ++i, j = 0) {
171 for (; j < 9; ++j) {
172 if ('.' == m_data[i][j]) {
173 for (
int k = '1'; k <= '9'; ++k) {
174 if (DoesConflict(m_data, i, j, k)) {
175 continue;
176 }
177 178 m_data[i][j] = k;
179 if (8 == j) {
180 if (Fill(i + 1, 0)) {
181 AddOneAnswer();
182 if (!m_does_try_all_answers) {
183 return true;
184 }
185 }
186 }
else {
187 if (Fill(i, j + 1)) {
188 AddOneAnswer();
189 if (!m_does_try_all_answers) {
190 return true;
191 }
192 }
193 }
194 }
195 m_data[i][j] = '.';
196 return false;
197 }
198 }
199 }
200 201 AddOneAnswer();
202 return true;
203 }
204 205 private:
206 bool m_does_try_all_answers;
207 std::vector<std::vector<
char> > m_data;
208 std::
set<std::
string> m_all_answers;
209 };
210 211 int main(
int argc,
char* argv[]) {
212 std::
string question;
213 //with many answers
214 question = ".2
..4
836..51
63887
..63195
..4
5
.4.7.2.98
..";
215 216 //with just one answer: https://baike.baidu.com/item/%E4%B8%96%E7%95%8C%E6%9C%80%E9%9A%BE%E6%95%B0%E7%8B%AC/13848819
217 question = "..53
..8
2..7..1.5..4
.53
1..7
6..32
8..6.5
.9..4
.3
97..";
218 219 bool find_all_answers =
false;
220 if (argc > 1 && 81 == strlen(argv[1])) {
221 question = argv[1];
222 }
else {
223 if (argc > 1) {
224 find_all_answers =
true;
225 }
226 question = Sudoku::ProvideOneQuestionRandomly();
227 }
228 229 Sudoku::PrintSudoku(question);
230 231 Sudoku sudoku(question, find_all_answers);
232 sudoku.Solve();
233 234 const std::
set<std::
string>& all_answers = sudoku.GiveAllAnswers();
235 int idx = 0;
236 for (
typeof(all_answers.begin()) iter = all_answers.begin(); all_answers.end() != iter; ++iter) {
237 std::cout << "answer " << ++idx << " for this sudoku is:" << std::endl;
238 Sudoku::PrintSudoku(*iter);
239 if (!Sudoku::ValidateOneAnswer(*iter)) {
240 std::cout << "answer is not correct: " << *iter << std::endl;
241 }
242 std::cout << "[" << *iter << "]" << std::endl;
243 }
244 return 0;
245 }
246