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 oneapi::tbb::task_group *g;
43 double solve_time;
44 
45 typedef struct {
46     unsigned short solved_element;
47     unsigned potential_set;
48 } board_element;
49 
50 void read_board(const char *filename) {
51     FILE *fp;
52     int input;
53     fp = fopen(filename, "r");
54     if (!fp) {
55         fprintf(stderr, "sudoku: Could not open input file '%s'.\n", filename);
56         std::exit(-1);
57     }
58     for (unsigned i = 0; i < BOARD_SIZE; ++i) {
59         if (fscanf(fp, "%d", &input))
60             init_values[i] = input;
61         else {
62             fprintf(stderr, "sudoku: Error in input file at entry %d, assuming 0.\n", i);
63             init_values[i] = 0;
64         }
65     }
66     fclose(fp);
67 }
68 
69 void print_board(board_element *b) {
70     for (unsigned row = 0; row < BOARD_DIM; ++row) {
71         for (unsigned col = 0; col < BOARD_DIM; ++col) {
72             printf(" %d", b[row * BOARD_DIM + col].solved_element);
73             if (col == 2 || col == 5)
74                 printf(" |");
75         }
76         printf("\n");
77         if (row == 2 || row == 5)
78             printf(" ---------------------\n");
79     }
80 }
81 
82 void print_potential_board(board_element *b) {
83     for (unsigned row = 0; row < BOARD_DIM; ++row) {
84         for (unsigned col = 0; col < BOARD_DIM; ++col) {
85             if (b[row * BOARD_DIM + col].solved_element)
86                 printf("  %4d ", b[row * BOARD_DIM + col].solved_element);
87             else
88                 printf(" [%4d]", b[row * BOARD_DIM + col].potential_set);
89             if (col == 2 || col == 5)
90                 printf(" |");
91         }
92         printf("\n");
93         if (row == 2 || row == 5)
94             printf(" ------------------------------------------------------------------\n");
95     }
96 }
97 
98 void init_board(board_element *b) {
99     for (unsigned i = 0; i < BOARD_SIZE; ++i)
100         b[i].solved_element = b[i].potential_set = 0;
101 }
102 
103 void init_board(board_element *b, unsigned short arr[81]) {
104     for (unsigned i = 0; i < BOARD_SIZE; ++i) {
105         b[i].solved_element = arr[i];
106         b[i].potential_set = 0;
107     }
108 }
109 
110 void init_potentials(board_element *b) {
111     for (unsigned i = 0; i < BOARD_SIZE; ++i)
112         b[i].potential_set = 0;
113 }
114 
115 void copy_board(board_element *src, board_element *dst) {
116     for (unsigned i = 0; i < BOARD_SIZE; ++i)
117         dst[i].solved_element = src[i].solved_element;
118 }
119 
120 bool fixed_board(board_element *b) {
121     for (int i = BOARD_SIZE - 1; i >= 0; --i)
122         if (b[i].solved_element == 0)
123             return false;
124     return true;
125 }
126 
127 bool in_row(board_element *b, unsigned row, unsigned col, unsigned short p) {
128     for (unsigned c = 0; c < BOARD_DIM; ++c)
129         if (c != col && b[row * BOARD_DIM + c].solved_element == p)
130             return true;
131     return false;
132 }
133 
134 bool in_col(board_element *b, unsigned row, unsigned col, unsigned short p) {
135     for (unsigned r = 0; r < BOARD_DIM; ++r)
136         if (r != row && b[r * BOARD_DIM + col].solved_element == p)
137             return true;
138     return false;
139 }
140 
141 bool in_block(board_element *b, unsigned row, unsigned col, unsigned short p) {
142     unsigned b_row = row / 3 * 3, b_col = col / 3 * 3;
143     for (unsigned i = b_row; i < b_row + 3; ++i)
144         for (unsigned j = b_col; j < b_col + 3; ++j)
145             if (!(i == row && j == col) && b[i * BOARD_DIM + j].solved_element == p)
146                 return true;
147     return false;
148 }
149 
150 void calculate_potentials(board_element *b) {
151     for (unsigned i = 0; i < BOARD_SIZE; ++i) {
152         b[i].potential_set = 0;
153         if (!b[i].solved_element) { // element is not yet fixed
154             unsigned row = i / BOARD_DIM, col = i % BOARD_DIM;
155             for (unsigned potential = 1; potential <= BOARD_DIM; ++potential) {
156                 if (!in_row(b, row, col, potential) && !in_col(b, row, col, potential) &&
157                     !in_block(b, row, col, potential))
158                     b[i].potential_set |= 1 << (potential - 1);
159             }
160         }
161     }
162 }
163 
164 bool valid_board(board_element *b) {
165     bool success = true;
166     for (unsigned i = 0; i < BOARD_SIZE; ++i) {
167         if (success && b[i].solved_element) { // element is fixed
168             unsigned row = i / BOARD_DIM, col = i % BOARD_DIM;
169             if (in_row(b, row, col, b[i].solved_element) ||
170                 in_col(b, row, col, b[i].solved_element) ||
171                 in_block(b, row, col, b[i].solved_element))
172                 success = false;
173         }
174     }
175     return success;
176 }
177 
178 bool examine_potentials(board_element *b, bool *progress) {
179     bool singletons = false;
180     for (unsigned i = 0; i < BOARD_SIZE; ++i) {
181         if (b[i].solved_element == 0 && b[i].potential_set == 0) // empty set
182             return false;
183         switch (b[i].potential_set) {
184             case 1: {
185                 b[i].solved_element = 1;
186                 singletons = true;
187                 break;
188             }
189             case 2: {
190                 b[i].solved_element = 2;
191                 singletons = true;
192                 break;
193             }
194             case 4: {
195                 b[i].solved_element = 3;
196                 singletons = true;
197                 break;
198             }
199             case 8: {
200                 b[i].solved_element = 4;
201                 singletons = true;
202                 break;
203             }
204             case 16: {
205                 b[i].solved_element = 5;
206                 singletons = true;
207                 break;
208             }
209             case 32: {
210                 b[i].solved_element = 6;
211                 singletons = true;
212                 break;
213             }
214             case 64: {
215                 b[i].solved_element = 7;
216                 singletons = true;
217                 break;
218             }
219             case 128: {
220                 b[i].solved_element = 8;
221                 singletons = true;
222                 break;
223             }
224             case 256: {
225                 b[i].solved_element = 9;
226                 singletons = true;
227                 break;
228             }
229         }
230     }
231     *progress = singletons;
232     return valid_board(b);
233 }
234 
235 void partial_solve(board_element *b, unsigned first_potential_set) {
236     if (fixed_board(b)) {
237         if (find_one)
238             g->cancel();
239         if (++nSols == 1 && verbose) {
240             print_board(b);
241         }
242         free(b);
243         return;
244     }
245     calculate_potentials(b);
246     bool progress = true;
247     bool success = examine_potentials(b, &progress);
248     if (success && progress) {
249         partial_solve(b, first_potential_set);
250     }
251     else if (success && !progress) {
252         board_element *new_board;
253         while (b[first_potential_set].solved_element != 0)
254             ++first_potential_set;
255         for (unsigned short potential = 1; potential <= BOARD_DIM; ++potential) {
256             if (1 << (potential - 1) & b[first_potential_set].potential_set) {
257                 new_board = (board_element *)malloc(BOARD_SIZE * sizeof(board_element));
258                 copy_board(b, new_board);
259                 new_board[first_potential_set].solved_element = potential;
260                 g->run([=] {
261                     partial_solve(new_board, first_potential_set);
262                 });
263             }
264         }
265         free(b);
266     }
267     else {
268         free(b);
269     }
270 }
271 
272 unsigned solve(int p) {
273     oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, p);
274     nSols = 0;
275     board_element *start_board = (board_element *)malloc(BOARD_SIZE * sizeof(board_element));
276     init_board(start_board, init_values);
277     g = new oneapi::tbb::task_group;
278     oneapi::tbb::tick_count t0 = oneapi::tbb::tick_count::now();
279     partial_solve(start_board, 0);
280     g->wait();
281     solve_time = (oneapi::tbb::tick_count::now() - t0).seconds();
282     delete g;
283     return nSols;
284 }
285 
286 int main(int argc, char *argv[]) {
287     oneapi::tbb::tick_count mainStartTime = oneapi::tbb::tick_count::now();
288 
289     utility::thread_number_range threads(utility::get_default_num_threads);
290     std::string filename = "";
291     bool silent = false;
292 
293     utility::parse_cli_arguments(
294         argc,
295         argv,
296         utility::cli_argument_pack()
297             //"-h" option for displaying help is present implicitly
298             .positional_arg(threads, "n-of-threads", utility::thread_number_range_desc)
299             .positional_arg(filename, "filename", "input filename")
300 
301             .arg(verbose, "verbose", "prints the first solution")
302             .arg(silent, "silent", "no output except elapsed time")
303             .arg(find_one, "find-one", "stops after finding first solution\n"));
304 
305     if (silent)
306         verbose = false;
307 
308     if (!filename.empty())
309         read_board(filename.c_str());
310     // otherwise (if file name not specified), the default statically initialized board will be used.
311     for (int p = threads.first; p <= threads.last; p = threads.step(p)) {
312         unsigned number = solve(p);
313 
314         if (!silent) {
315             if (find_one) {
316                 printf("Sudoku: Time to find first solution on %d threads: %6.6f seconds.\n",
317                        p,
318                        solve_time);
319             }
320             else {
321                 printf("Sudoku: Time to find all %u solutions on %d threads: %6.6f seconds.\n",
322                        number,
323                        p,
324                        solve_time);
325             }
326         }
327     }
328 
329     utility::report_elapsed_time((oneapi::tbb::tick_count::now() - mainStartTime).seconds());
330 
331     return 0;
332 };
333