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