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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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