62
edits
Changes
→Challenges
c) Else, remove digit and try another
If all digits have been tried and nothing worked, return false
===Sudoku Backtrack Function===
/* Takes a partially filled-in grid and attempts to assign values to
all unassigned locations in such a way to meet the requirements
for Sudoku solution (non-duplication across rows, columns, and boxes) */
bool SolveSudoku(int grid[N])
{
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
for (int num = 1; num <= n; num++)
{
// 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
grid[(row)+(col*n)] = UNASSIGNED;
}
}
return false; // this triggers backtracking
}
===Source===
http://www.geeksforgeeks.org/backtracking-set-7-suduku/
== Assignment 2 ==
===Challenges===
The 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.
===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
