Open main menu

CDOT Wiki β

Changes

Semi-Team

2,215 bytes added, 16:48, 11 April 2017
→‎Challenges
== Assignment 1 ==
===Rules to play Sudoku===
Sudoku is a logic puzzle where a grid composed of mini grids is presented to the player to fill each cell with a number unique to its column, row and mini-grid.
 
===Sudoku Backtrack Algorithm===
===Serial Sudoku Performance=== Find row, col of an unassigned cellDifficulty Medium: If there is none, return true 0 7 0 5 0 0 0 8 0 0 0 4 9 0 0 0 0 0 3 0 6 0 2 7 0 0 0 0 0 For digits from 1 0 7 to 9 6 3 0 7 0 0 8 0 6 0 0 4 a) If there is no conflict for digit at row,col 0 6 2 3 5 0 7 0 0 assign digit to row,col and recursively try fill in rest of grid 0 0 0 9 9 0 8 0 3 b) If recursion successful, return true 0 0 0 0 0 5 9 0 0 c) Else, remove digit and try another 0 2 0 0 0 3 0 6 0 If all digits have been tried and nothing worked, return false ===Sudoku Solved - took - 1 millisecsBacktrack Function===
Difficulty Hard: /* Takes a partially filled-in grid and attempts to assign values to 0 0 0 7 9 0 4 0 0all unassigned locations in such a way to meet the requirements 0 0 0 1 0 3 7 0 0for Sudoku solution (non-duplication across rows, columns, and boxes) */ 0 8 0 0 0 2 0 3 0bool SolveSudoku(int grid[N]) 0 0 6 0 0 4 8 0 0{ int row, col; // If there is no unassigned location, we are done if (!FindUnassignedLocation(grid, row, col)) return true; // success! 0 7 0 0 // consider digits 1 0 0 2 0to 16 0 0 4 3 0 0 for (int num = 1 0 0; 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; 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 return false; // this triggers backtracking Sudoku Solved - took - 7 millisecs}
Difficulty Evil===Source===http: 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 2 4 0 4 0 0 0 //www.geeksforgeeks.org/backtracking-set-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 Sudoku Solved - took - 6 millisecssuduku/
== 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
=== Assignment 3 ===Created By Arto Inkala
Mfainshtein2
62
edits
Retrieved from "https://wiki.cdot.senecapolytechnic.ca/wiki/Special:MobileDiff/124971...125440"