1#ifndef SUDOKU_H 2#define SUDOKU_H 3 4// Represents a 9x9 Sudoku board with methods for solving it 5class Sudoku { 6public: 7 8 typedef int Board[9][9]; 9 10 // Copies board to the class's internal memory 11 void submit(const Board &board); 12 13 // Solves the Sudoku board stored in the class, storing 14 // the final board in solution. Returns true if a 15 // solution was found or false if one could not be found. 16 bool solve(Board &solution); 17 18private: 19 20 // Returns the discovered numbers found in the cell's row, column, and box. 21 // Note cell's value will not be included in the result. 22 // 23 // 'where' specifies where to look where 0 means the cell's row, 1 means 24 // the cell's column and 2 means the cell's box. 25 // 'cell' must be a pointer to an element in the 'board' array. 26 // Set completeOnly to false to get all bits owned by friends instead of 27 // only completed numbers. 28 // 29 // To check if 3 is a friend of cell, you would shift the return value right 30 // 2 and bitwise AND it with 1. 31 // To check if 5 is a friend of cell, you would shift the return value right 32 // 4 and bitwise AND it with 1. 33 // And so on until 9. 34 int getFriends(int where, int *cell, bool completeOnly = true); 35 36 Board board; 37}; 38 39#endif 40 41using namespace std; 42 43void Sudoku::submit(const Board &from) 44{ 45 /* First off, we set bits to represent the possible values 46 * each box on the board can have. 1 represents 1, 1 << 1 47 * represents 2, 1 << 2 represents 3 and so on. 48 * We set this bits while copying to the board array. 49 */ 50 51 for(int i = 0; i < 81; i++) { 52 53 if(!from[0]<i>) 54 board[0]<i> = 0x1ff; // Set all bits 1-9 55 else 56 board[0]<i> = (1 << (from[0]<i> - 1)); 57 } 58} 59 60bool Sudoku::solve(Board &answer) 61{ 62 // So we have two stages. In the first stage we narrow down the possible 63 // numbers for a given cell. In the second stage we iterate through the 64 // cells in a given row/column/box seeing how many can take a given number, 65 // if theres only 1 we set that number. 66 67 int stage1actions; 68 int stage2actions; 69 70 do { 71 72 stage1actions = 0; 73 stage2actions = 0; 74 75 // Stage 1 - Here we go through each cell on the board and update the 76 // cells list of possible numbers (in other words, further restrict 77 // the numbers a cell is allowed to be). 78 79 bool didChange = true; 80 81 do { 82 didChange = false; 83 84 for(int j = 0; j < 81; j++) { 85 86 int original = board[0][j]; 87 88 board[0][j] &= ~getFriends(0, board[0] + j) 89 & ~getFriends(1, board[0] + j) 90 & ~getFriends(2, board[0] + j); 91 92 if(board[0][j] != original) { 93 94 stage1actions++; 95 didChange = true; 96 } 97 } 98 99 } while(didChange); 100 101 // Stage 2 - Now we go through each cell on the board and check to see 102 // if the row/column/box its in has any numbers that only the cell could 103 // be. If this is the case we set the cell to that number. 104 105 // loop all cells 106 for(int j = 0; j < 81; j++) { 107 108 int bitsSet = 0; 109 110 for(int p = 8; p >= 0; p--) { 111 112 if((board[0][j] >> p) & 1) 113 bitsSet++; 114 } 115 116 if(bitsSet == 0) { 117 118 // Shit a cell is bad! 119 continue; 120 } 121 122 if(bitsSet == 1) { 123 124 // This cell is a complete number. 125 continue; 126 } 127 128 int bits = getFriends(0, board[0] + j, false) 129 & getFriends(1, board[0] + j, false) 130 & getFriends(2, board[0] + j, false); 131 132 for(int l = 8; l >= 0; l--) { 133 134 // If no friends have this bit set yet we do.. 135 if(!((bits >> l) & 1) && ((board[0][j] >> l) & 1)) { 136 137 board[0][j] = (1 << l); 138 stage2actions++; 139 140 break; 141 } 142 } 143 } 144 145 } while(stage1actions || stage2actions); 146 147 bool ret = true; 148 149 for(int i = 0; i < 81; i++) { 150 151 int &cell = board[0]<i>; 152 int &dest = answer[0]<i>; 153 154 if(!cell) { 155 156 ret = false; 157 158 continue; 159 } 160 161 // Check to see if this cell has more then one bit set and set dest at 162 // the same time. 163 bool bitFound = 0; 164 for(int l = 8; l >= 0; l--) { 165 166 if((cell >> l) & 1) { 167 168 if(bitFound) { 169 170 dest = 0; 171 ret = false; 172 } 173 else 174 dest = l + 1; 175 176 bitFound = true; 177 } 178 } 179 } 180 181 return ret; 182} 183 184int Sudoku::getFriends(int where, int *cell, bool completeOnly) 185{ 186 int ret = 0; 187 188 switch(where) { 189 case 0: 190 { 191 int *row = board[(cell - board[0]) / 9]; 192 193 // Loop through all elements in the row 194 for(int i = 0; i < 9; i++) { 195 196 if(row + i == cell) 197 continue; 198 199 int bit = 0; 200 201 // Loop through all bits in cell 202 for(int j = 0; j < 9; j++) { 203 204 if((row<i> >> j) & 1) { 205 206 if(bit && completeOnly) { 207 208 bit = 0; 209 break; 210 } 211 212 bit |= 1 << j; 213 } 214 } 215 216 ret |= bit; 217 } 218 219 break; 220 } 221 case 1: 222 { 223 int *col = &board[0][(cell - board[0]) % 9]; 224 225 // Loop through all elements in the column 226 for(int i = 0; i < 9; i++) { 227 228 if(col + i * 9 == cell) 229 continue; 230 231 int bit = 0; 232 233 // Loop through all bits in cell 234 for(int j = 0; j < 9; j++) { 235 236 if((col[i * 9] >> j) & 1) { 237 238 if(bit && completeOnly) { 239 240 bit = 0; 241 break; 242 } 243 244 bit |= 1 << j; 245 } 246 } 247 248 ret |= bit; 249 } 250 251 break; 252 } 253 case 2: 254 { 255 // Algorithm to find the upper left corner of the box cell is located in 256 int *box = &board[0][((cell - board[0]) % 9) / 3 * 3 + (cell - board[0]) / 9 / 3 * 27]; 257 258 int bit; 259 260 // Loop through all elements in the box 261 for(int i = 0; i < 21; i++) { 262 263 if(box + i == cell) 264 goto Cont; 265 266 bit = 0; 267 268 // Loop through all bits in cell 269 for(int j = 0; j < 9; j++) { 270 271 if((box<i> >> j) & 1) { 272 273 if(bit && completeOnly) { 274 275 bit = 0; 276 break; 277 } 278 279 bit |= 1 << j; 280 } 281 } 282 283 ret |= bit; 284 285 // 'continues' the loop 286 Cont:; 287 288 // If we're on the edge of the box jump ahead to the next row 289 if(i == 2 || i == 11) 290 i += 6; 291 } 292 293 break; 294 } 295 } 296 297 return ret; 298} 299 300 301#include <iostream> 302#include <iomanip> 303 304#ifdef WIN32 305#include <windows.h> 306#endif 307using namespace std; 308 309int main() 310{ 311 /* Medium level board *solved* */ 312 /* 313 int board[9][9] = 314 { 315 { 0, 6, 0, 1, 0, 4, 0, 5, 0 }, 316 { 0, 0, 8, 3, 0, 5, 6, 0, 0 }, 317 { 2, 0, 0, 0, 0, 0, 0, 0, 1 }, 318 { 8, 0, 0, 4, 0, 7, 0, 0, 6 }, 319 { 0, 0, 6, 0, 0, 0, 3, 0, 0 }, 320 { 7, 0, 0, 9, 0, 1, 0, 0, 4 }, 321 { 5, 0, 0, 0, 0, 0, 0, 0, 2 }, 322 { 0, 0, 7, 2, 0, 6, 9, 0, 0 }, 323 { 0, 4, 0, 5, 0, 8, 0, 7, 0 } 324 }; 325 */ 326 327 /* Hard level board *solved* */ 328 int board[9][9] = 329 { 330 { 0, 9, 1, 0, 0, 0, 8, 0, 0 }, 331 { 0, 0, 0, 2, 0, 0, 3, 0, 0 }, 332 { 2, 0, 5, 1, 0, 6, 9, 0, 0 }, 333 { 1, 0, 0, 0, 0, 0, 5, 0, 0 }, 334 { 0, 3, 0, 0, 5, 0, 0, 2, 0 }, 335 { 0, 0, 4, 0, 0, 0, 0, 0, 9 }, 336 { 0, 0, 3, 5, 0, 4, 2, 0, 6 }, 337 { 0, 0, 6, 0, 0, 8, 0, 0, 0 }, 338 { 0, 0, 8, 0, 0, 0, 7, 4, 0 } 339 }; 340 341 cout << "Intial board:\n"; 342 343 cout << "-------------------------\n| "; 344 345 for(int i = 0; i < sizeof(board) / sizeof(board[0][0]); i++) 346 cout << board[0]<i> 347 << ((i + 1) % 9 ? ((i + 1) % 3 ? " " : " | ") : ((i + 1) % 27 ? " |\n| " : " |\n| --------------------- |\n| ")); 348 349 Sudoku sudoku; 350 351#ifdef WIN32 352 time_t start = GetTickCount(); 353#endif 354 355 sudoku.submit(board); 356 if(sudoku.solve(board)) 357 cout << "Board solved!\n"; 358 else 359 cout << "Board unsolvable.\n"; 360 361#ifdef WIN32 362 time_t t = GetTickCount() - start; 363 364 cout << "Milliseconds to solve: " << t << endl; 365#endif 366 367 cout << "Final board:\n"; 368 369 cout << "-------------------------\n| "; 370 371 for(int i = 0; i < sizeof(board) / sizeof(board[0][0]); i++) 372 cout << board[0]<i> 373 << ((i + 1) % 9 ? ((i + 1) % 3 ? " " : " | ") : ((i + 1) % 27 ? " |\n| " : " |\n| --------------------- |\n| ")); 374 375 system("PAUSE"); 376 377 return 0; 378}

1Intial board: 2------------------------- 3| 0 7 3 | 0 9 0 | 0 4 0 | 4| 9 0 0 | 4 0 3 | 0 0 7 | 5| 0 0 0 | 6 0 0 | 0 0 8 | 6| --------------------- | 7| 0 4 0 | 0 0 0 | 3 6 0 | 8| 7 0 0 | 0 0 0 | 0 0 1 | 9| 0 2 9 | 0 0 0 | 0 5 0 | 10| --------------------- | 11| 5 0 0 | 0 0 1 | 0 0 0 | 12| 0 0 6 | 0 0 8 | 0 0 3 | 13| 0 3 0 | 0 4 0 | 1 7 0 | 14| --------------------- | 15| Board unsolvable. 16Milliseconds to solve: 10 17Final board: 18------------------------- 19| 6 7 3 | 8 9 2 | 0 4 5 | 20| 9 8 2 | 4 5 3 | 6 1 7 | 21| 1 5 4 | 6 7 0 | 9 3 8 | 22| --------------------- | 23| 8 4 1 | 7 2 5 | 3 6 9 | 24| 7 6 5 | 9 3 4 | 8 2 1 | 25| 3 2 9 | 1 8 6 | 7 5 4 | 26| --------------------- | 27| 5 9 7 | 3 6 1 | 4 8 2 | 28| 4 1 6 | 2 0 8 | 5 9 3 | 29| 2 3 8 | 5 4 9 | 1 7 6 | 30| --------------------- | 31| Press any key to continue . . .