Difference between revisions of "Semi-Team"

From CDOT Wiki
Jump to: navigation, search
(→‎Assignment 3)
(→‎Challenges)
 
(25 intermediate revisions by the same user not shown)
Line 8: Line 8:
 
== Assignment 1 ==
 
== Assignment 1 ==
 
===Rules to play Sudoku===
 
===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===
 
===Sudoku Backtrack Algorithm===
−
===Serial Sudoku Performance===
+
  Find row, col of an unassigned cell
−
Difficulty Medium:
+
  If there is none, return true
−
0 7 0 5 0 0 0 8 0
+
  For digits from 1 to 9
−
0 0 4 9 0 0 0 0 0
+
    a) If there is no conflict for digit at row,col
−
3 0 6 0 2 7 0 0 0
+
        assign digit to row,col and recursively try fill in rest of grid
−
0 0 1 0 7 9 6 3 0
+
    b) If recursion successful, return true
−
7 0 0 8 0 6 0 0 4
+
    c) Else, remove digit and try another
−
0 6 2 3 5 0 7 0 0
+
  If all digits have been tried and nothing worked, return false
−
0 0 0 9 9 0 8 0 3
+
===Sudoku Backtrack Function===
−
0 0 0 0 0 5 9 0 0
 
−
0 2 0 0 0 3 0 6 0
 
−
Sudoku Solved - took - 1 millisecs
 
  
−
Difficulty Hard:
+
/* Takes a partially filled-in grid and attempts to assign values to
−
  0 0 0 7 9 0 4 0 0
+
  all unassigned locations in such a way to meet the requirements
−
  0 0 0 1 0 3 7 0 0
+
  for Sudoku solution (non-duplication across rows, columns, and boxes) */
−
  0 8 0 0 0 2 0 3 0
+
  bool SolveSudoku(int grid[N])
−
  0 0 6 0 0 4 8 0 0
+
  {
−
0 7 0 0 1 0 0 2 0
+
    int row, col;
−
0 0 4 3 0 0 1 0 0
+
    // If there is no unassigned location, we are done
−
0 9 0 4 0 0 0 6 0
+
    if (!FindUnassignedLocation(grid, row, col))
−
0 0 3 8 0 5 0 0 0
+
      return true; // success!
−
0 0 7 0 6 9 0 0 0
+
    // consider digits 1 to 16
−
  Sudoku Solved - took - 7 millisecs
+
    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
 +
  }
  
−
Difficulty Evil:
+
===Source===
−
0 0 0 8 0 2 0 0 0
+
http://www.geeksforgeeks.org/backtracking-set-7-suduku/
−
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 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 millisecs
 
  
 
== Assignment 2 ==
 
== 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 ==
 
== 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

Latest revision as of 15:48, 11 April 2017


GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary

Semi-Team

Team Members

  1. Michael Fainshtein, Research, Development, Presentation

Email All

Progress

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

 Find row, col of an unassigned cell
 If there is none, return true
 For digits from 1 to 9
   a) If there is no conflict for digit at row,col
       assign digit to row,col and recursively try fill in rest of grid
   b) If recursion successful, return true
   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

Hardgraph.png 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

EvilGraph.png 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

Hardestgraph.png 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

Retrieved from "https://wiki.cdot.senecapolytechnic.ca/w/index.php?title=Semi-Team&oldid=125440"