Semi-Team

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

Semi-Team

Team Members

1. Michael Fainshtein, Research, Development, Presentation

Email All

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

Serial Sudoku Performance

Difficulty Medium:

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 1 0 7 9 6 3 0
7 0 0 8 0 6 0 0 4
0 6 2 3 5 0 7 0 0
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
Sudoku Solved - took - 1 millisecs

Difficulty Hard:

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 - took - 7 millisecs

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 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