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)] =Serial Sudoku Performance==num; // return, if success if (SolveSudoku(grid)) return true; // failure, unmake & try again grid[(row)+(col*n)] =UNASSIGNED; } } return false; // this triggers backtracking }
Difficulty Medium===Source===http:02 00 00 |00 00 00 |00 00 0009 00 00 |04 00 08 |00 00 0600 03 08 |00 02 07 |00 00 00____________________________00 04 00 |00 00 03 |00 01 0000 02 00 |00 04 00 |00 06 0000 08 00 |05 00 00 |00 03 00____________________________00 00 00 |07 06 00 |03 05 0007 00 00 |09 00 05 |00 00 0800 00 00 |00 00 00 |00 00 01//www.geeksforgeeks.org/backtracking-set-7-suduku/
Sudoku Solved == 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 - took set the threads per block to 1024 from 512 - 6 millisecsset 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
Difficulty HardGenerated at http:00 00 00 |08 00 02 |00 00 0007 00 00 |00 00 00 |00 00 0900 00 01 |00 00 09 |00 06 02_____________________________00 07 00 |06 00 00 |00 05 0001 03 00 |00 00 00 |00 02 0400 04 00 |00 00 07 |00 08 00____________________________08 01 00 |03 00 00 |05 00 0005 00 00 |00 00 00 |00 00 0800 00 00 |04 00 08 |00 00 00 Sudoku Solved - took - 16 millisecs//www.websudoku.com/
== Assignment 2 =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
== Assignment 3 ==Created By Arto Inkala
