examples/task_group/sudoku/sudoku.cpp

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