c) Else, remove digit and try another
If all digits have been tried and nothing worked, return false
===Sudoku Backtrack Function===
===Serial Sudoku Performance=== /* Takes a partially filled-in grid and attempts to assign values toDifficulty Medium: all unassigned locations in such a way to meet the requirements 0 7 0 5 0 0 0 8 0for Sudoku solution (non-duplication across rows, columns, and boxes) */ 0 0 4 9 0 0 0 0 0bool SolveSudoku(int grid[N]) 3 0 6 0 2 7 0 0 0{ int row, col; // If there is no unassigned location, we are done if (!FindUnassignedLocation(grid, row, col)) return true; // success! // consider digits 1 to 16 0 0 for (int num = 1 0 7 9 6 3 0; num <= n; num++) 7 0 0 8 0 6 0 0 4 { // if looks promising if (isSafe(grid, row, col, num)) { // make tentative assignment grid[(row)+(col*n)] = num; // return, if success if (SolveSudoku(grid)) return true; // failure, unmake & try again 0 6 2 3 5 0 7 0 0 grid[(row)+(col*n)] = UNASSIGNED; 0 0 0 9 9 0 8 0 3 } 0 0 0 0 0 5 9 0 0 } 0 2 0 0 0 3 0 6 0 return false; // this triggers backtracking Sudoku Solved - took - 1 millisecs}
Difficulty Hard===Source===http: 0 0 0 7 9 0 4 0 0 0 0 0 1 0 3 7 0 0 0 8 0 0 0 2 0 3 0 0 0 6 0 0 4 8 0 0 0 7 0 0 1 0 0 2 0 0 0 4 3 0 0 1 0 0 0 9 0 4 0 0 0 6 0 0 0 3 8 0 5 0 0 0 0 0 7 0 6 9 0 0 0 Sudoku Solved //www.geeksforgeeks.org/backtracking- took set- 7 millisecs-suduku/
Difficulty Evil: 0 0 0 8 0 2 0 0 0 7 0 0 0 0 0 0 0 9 0 0 1 0 0 9 0 6 2 0 7 0 6 0 0 0 5 0 3 0 0 0 0 0 0 == Assignment 2 4 0 4 0 0 0 7 0 8 0 8 1 0 3 0 0 5 0 0 5 0 0 0 0 0 0 0 8== 0 0 0 4 0 8 0 0 0===Challenges=== Sudoku Solved - took - 6 millisecsThe main issue I have run into when attempting to parallelize the back tracking function is that it is recursive function which does not translate into a kernel and since it focuses on progressing a single stack, it can't really benefit from thread as they can't all work off the same stack.
== Assignment 2 =Process======Kernel===
== Assignment 3 ==
===Optimization===
Global variables utilized in the backtrack kernel were copied into registered memory
//add registered memory
int *registeredBoards= boards;
int *registeredEmptySpaces = emptySpaces;
int *registeredNumEmptySpaces = numEmptySpaces;
For a device of computation capacity 5.2
- set the threads per block to 1024 from 512
- set the maximum blocks to 32 from 256
== Results ==
===Hard Generated Puzzle===
[[File:Hardgraph.png]] [[File:hardpuzzle.png]]
Arguments: 112 219 244 268 296 323 338 352 367 424 463 481 522 554 586 628 645 683 747 756 773 785 817 849 865 898 991
Generated at http://www.websudoku.com/
===Evil Generated Puzzle===
[[File:EvilGraph.png]] [[File:evilpuzzle.png]]
Arguments: 148 162 217 299 331 369 386 392 427 446 485 511 523 582 594 624 667 688 718 721 743 775 815 898 944 968
Generated at http://www.websudoku.com/
===Hardest Puzzle===
[[File:hardestgraph.png]] [[File:Hardestpuzzle.png]]
Arguments: 118 233 246 327 359 372 425 467 554 565 577 641 683 731 786 798 838 845 881 929 974
Created By Arto Inkala
