1 /*
2 Copyright (c) 2005-2021 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #include <cstdio>
18 #include <cstdlib>
19
20 #include <string>
21 #include <atomic>
22
23 #include "oneapi/tbb/tick_count.h"
24 #include "oneapi/tbb/task_group.h"
25 #include "oneapi/tbb/global_control.h"
26
27 #include "common/utility/utility.hpp"
28 #include "common/utility/get_default_num_threads.hpp"
29
30 #pragma warning(disable : 4996)
31
32 const unsigned BOARD_SIZE = 81;
33 const unsigned BOARD_DIM = 9;
34 std::atomic<unsigned> nSols;
35 bool find_one = false;
36 bool verbose = false;
37 unsigned short init_values[BOARD_SIZE] = { 1, 0, 0, 9, 0, 0, 0, 8, 0, 0, 8, 0, 2, 0, 0, 0, 0,
38 0, 0, 0, 5, 0, 0, 0, 7, 0, 0, 0, 5, 2, 1, 0, 0, 4,
39 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 7, 4, 0, 0, 7, 0, 0,
40 0, 3, 0, 0, 3, 0, 0, 0, 2, 0, 0, 5, 0, 0, 0, 0, 0,
41 0, 1, 0, 0, 5, 0, 0, 0, 1, 0, 0, 0, 0 };
42 double solve_time;
43
44 typedef struct {
45 unsigned short solved_element;
46 unsigned potential_set;
47 } board_element;
48
read_board(const char * filename)49 void read_board(const char* filename) {
50 FILE* fp;
51 int input;
52 fp = fopen(filename, "r");
53 if (!fp) {
54 fprintf(stderr, "sudoku: Could not open input file '%s'.\n", filename);
55 std::exit(-1);
56 }
57 for (unsigned i = 0; i < BOARD_SIZE; ++i) {
58 if (fscanf(fp, "%d", &input))
59 init_values[i] = input;
60 else {
61 fprintf(stderr, "sudoku: Error in input file at entry %d, assuming 0.\n", i);
62 init_values[i] = 0;
63 }
64 }
65 fclose(fp);
66 }
67
print_board(const std::vector<board_element> & b)68 void print_board(const std::vector<board_element>& b) {
69 for (unsigned row = 0; row < BOARD_DIM; ++row) {
70 for (unsigned col = 0; col < BOARD_DIM; ++col) {
71 printf(" %d", b[row * BOARD_DIM + col].solved_element);
72 if (col == 2 || col == 5)
73 printf(" |");
74 }
75 printf("\n");
76 if (row == 2 || row == 5)
77 printf(" ---------------------\n");
78 }
79 }
80
print_potential_board(const std::vector<board_element> & b)81 void print_potential_board(const std::vector<board_element>& b) {
82 for (unsigned row = 0; row < BOARD_DIM; ++row) {
83 for (unsigned col = 0; col < BOARD_DIM; ++col) {
84 if (b[row * BOARD_DIM + col].solved_element)
85 printf(" %4d ", b[row * BOARD_DIM + col].solved_element);
86 else
87 printf(" [%4d]", b[row * BOARD_DIM + col].potential_set);
88 if (col == 2 || col == 5)
89 printf(" |");
90 }
91 printf("\n");
92 if (row == 2 || row == 5)
93 printf(" ------------------------------------------------------------------\n");
94 }
95 }
96
init_board(std::vector<board_element> & b)97 void init_board(std::vector<board_element>& b) {
98 for (unsigned i = 0; i < BOARD_SIZE; ++i)
99 b[i].solved_element = b[i].potential_set = 0;
100 }
101
init_board(std::vector<board_element> & b,unsigned short arr[BOARD_SIZE])102 void init_board(std::vector<board_element>& b, unsigned short arr[BOARD_SIZE]) {
103 for (unsigned i = 0; i < BOARD_SIZE; ++i) {
104 b[i].solved_element = arr[i];
105 b[i].potential_set = 0;
106 }
107 }
108
init_potentials(std::vector<board_element> & b)109 void init_potentials(std::vector<board_element>& b) {
110 for (unsigned i = 0; i < BOARD_SIZE; ++i)
111 b[i].potential_set = 0;
112 }
113
fixed_board(const std::vector<board_element> & b)114 bool fixed_board(const std::vector<board_element>& b) {
115 for (int i = BOARD_SIZE - 1; i >= 0; --i)
116 if (b[i].solved_element == 0)
117 return false;
118 return true;
119 }
120
in_row(const std::vector<board_element> & b,unsigned row,unsigned col,unsigned short p)121 bool in_row(const std::vector<board_element>& b, unsigned row, unsigned col, unsigned short p) {
122 for (unsigned c = 0; c < BOARD_DIM; ++c)
123 if (c != col && b[row * BOARD_DIM + c].solved_element == p)
124 return true;
125 return false;
126 }
127
in_col(const std::vector<board_element> & b,unsigned row,unsigned col,unsigned short p)128 bool in_col(const std::vector<board_element>& b, unsigned row, unsigned col, unsigned short p) {
129 for (unsigned r = 0; r < BOARD_DIM; ++r)
130 if (r != row && b[r * BOARD_DIM + col].solved_element == p)
131 return true;
132 return false;
133 }
134
in_block(const std::vector<board_element> & b,unsigned row,unsigned col,unsigned short p)135 bool in_block(const std::vector<board_element>& b, unsigned row, unsigned col, unsigned short p) {
136 unsigned b_row = row / 3 * 3, b_col = col / 3 * 3;
137 for (unsigned i = b_row; i < b_row + 3; ++i)
138 for (unsigned j = b_col; j < b_col + 3; ++j)
139 if (!(i == row && j == col) && b[i * BOARD_DIM + j].solved_element == p)
140 return true;
141 return false;
142 }
143
calculate_potentials(std::vector<board_element> & b)144 void calculate_potentials(std::vector<board_element>& b) {
145 for (unsigned i = 0; i < BOARD_SIZE; ++i) {
146 b[i].potential_set = 0;
147 if (!b[i].solved_element) { // element is not yet fixed
148 unsigned row = i / BOARD_DIM, col = i % BOARD_DIM;
149 for (unsigned potential = 1; potential <= BOARD_DIM; ++potential) {
150 if (!in_row(b, row, col, potential) && !in_col(b, row, col, potential) &&
151 !in_block(b, row, col, potential))
152 b[i].potential_set |= 1 << (potential - 1);
153 }
154 }
155 }
156 }
157
valid_board(const std::vector<board_element> & b)158 bool valid_board(const std::vector<board_element>& b) {
159 bool success = true;
160 for (unsigned i = 0; i < BOARD_SIZE; ++i) {
161 if (success && b[i].solved_element) { // element is fixed
162 unsigned row = i / BOARD_DIM, col = i % BOARD_DIM;
163 if (in_row(b, row, col, b[i].solved_element) ||
164 in_col(b, row, col, b[i].solved_element) ||
165 in_block(b, row, col, b[i].solved_element))
166 success = false;
167 }
168 }
169 return success;
170 }
171
examine_potentials(std::vector<board_element> & b,bool & progress)172 bool examine_potentials(std::vector<board_element>& b, bool& progress) {
173 bool singletons = false;
174 for (unsigned i = 0; i < BOARD_SIZE; ++i) {
175 if (b[i].solved_element == 0 && b[i].potential_set == 0) // empty set
176 return false;
177 switch (b[i].potential_set) {
178 case 1: {
179 b[i].solved_element = 1;
180 singletons = true;
181 break;
182 }
183 case 2: {
184 b[i].solved_element = 2;
185 singletons = true;
186 break;
187 }
188 case 4: {
189 b[i].solved_element = 3;
190 singletons = true;
191 break;
192 }
193 case 8: {
194 b[i].solved_element = 4;
195 singletons = true;
196 break;
197 }
198 case 16: {
199 b[i].solved_element = 5;
200 singletons = true;
201 break;
202 }
203 case 32: {
204 b[i].solved_element = 6;
205 singletons = true;
206 break;
207 }
208 case 64: {
209 b[i].solved_element = 7;
210 singletons = true;
211 break;
212 }
213 case 128: {
214 b[i].solved_element = 8;
215 singletons = true;
216 break;
217 }
218 case 256: {
219 b[i].solved_element = 9;
220 singletons = true;
221 break;
222 }
223 }
224 }
225 progress = singletons;
226 return valid_board(b);
227 }
228
partial_solve(oneapi::tbb::task_group & g,std::vector<board_element> & b,unsigned first_potential_set)229 void partial_solve(oneapi::tbb::task_group& g,
230 std::vector<board_element>& b,
231 unsigned first_potential_set) {
232 if (fixed_board(b)) {
233 if (find_one)
234 g.cancel();
235 if (++nSols == 1 && verbose) {
236 print_board(b);
237 }
238 return;
239 }
240 calculate_potentials(b);
241 bool progress = true;
242 bool success = examine_potentials(b, progress);
243 if (success && progress) {
244 partial_solve(g, b, first_potential_set);
245 }
246 else if (success && !progress) {
247 while (b[first_potential_set].solved_element != 0)
248 ++first_potential_set;
249 for (unsigned short potential = 1; potential <= BOARD_DIM; ++potential) {
250 if (1 << (potential - 1) & b[first_potential_set].potential_set) {
251 g.run([&g, b /*make a copy of the board*/, first_potential_set, potential]() {
252 //as task_group treat passed in functor as const - const_cast is needed
253 //to allow modification of the copy
254 auto& new_board = const_cast<std::vector<board_element>&>(b);
255 new_board[first_potential_set].solved_element = potential;
256 partial_solve(g, new_board, first_potential_set);
257 });
258 }
259 }
260 }
261 }
262
solve(int p)263 unsigned solve(int p) {
264 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, p);
265 nSols = 0;
266 std::vector<board_element> start_board(BOARD_SIZE);
267 init_board(start_board, init_values);
268 oneapi::tbb::task_group g;
269 oneapi::tbb::tick_count t0 = oneapi::tbb::tick_count::now();
270 partial_solve(g, start_board, 0);
271 g.wait();
272 solve_time = (oneapi::tbb::tick_count::now() - t0).seconds();
273 return nSols;
274 }
275
main(int argc,char * argv[])276 int main(int argc, char* argv[]) {
277 oneapi::tbb::tick_count mainStartTime = oneapi::tbb::tick_count::now();
278
279 utility::thread_number_range threads(utility::get_default_num_threads);
280 std::string filename = "";
281 bool silent = false;
282
283 utility::parse_cli_arguments(
284 argc,
285 argv,
286 utility::cli_argument_pack()
287 //"-h" option for displaying help is present implicitly
288 .positional_arg(threads, "n-of-threads", utility::thread_number_range_desc)
289 .positional_arg(filename, "filename", "input filename")
290
291 .arg(verbose, "verbose", "prints the first solution")
292 .arg(silent, "silent", "no output except elapsed time")
293 .arg(find_one, "find-one", "stops after finding first solution\n"));
294
295 if (silent)
296 verbose = false;
297
298 if (!filename.empty())
299 read_board(filename.c_str());
300 // otherwise (if file name not specified), the default statically initialized board will be used.
301 for (int p = threads.first; p <= threads.last; p = threads.step(p)) {
302 unsigned number = solve(p);
303
304 if (!silent) {
305 if (find_one) {
306 printf("Sudoku: Time to find first solution on %d threads: %6.6f seconds.\n",
307 p,
308 solve_time);
309 }
310 else {
311 printf("Sudoku: Time to find all %u solutions on %d threads: %6.6f seconds.\n",
312 number,
313 p,
314 solve_time);
315 }
316 }
317 }
318
319 utility::report_elapsed_time((oneapi::tbb::tick_count::now() - mainStartTime).seconds());
320
321 return 0;
322 };
323