GPU610/gpuchill

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

GPU n' Chill

Team Members

1. Daniel Serpa, Some responsibility
2. Abdul Kabia, Some responsibility
3. Josh Tardif, Some responsibility
4. Andrew Faux, Some responsibility
5. Fardad Soleimanloo, Some other responsibility
6. ...

Email All

Progress

Sudoku Brute Force Solver

I decided to profile a simple brute force Sudoku solver, found here (https://github.com/regehr/sudoku). The solver uses a simple back tracking algorithm, inserting possible values into cells, iterating through the puzzles thousands of times, until it eventually produces an answer which does not violate any of the rules of Sudoku. As such the solver runs at the same speed regardless of the human difficulty rating, able to solve easy and 'insane' level puzzles at the same speed. The solver also works independent of the ratio between clues and white space, producing quick results with even the most sparsely populated puzzles.As such the following run of the program uses a puzzle which is specifically made to play against the back tracking algorithm and provides maximum time for the solver.

Test run with puzzle:

Original configuration:
-------------
|   |   |   |
|   |  3| 85|
|  1| 2 |   |
-------------
|   |5 7|   |
|  4|   |1  |
| 9 |   |   |
-------------
|5  |   | 73|
|  2| 1 |   |
|   | 4 |  9|
-------------
17 entries filled
solution:
-------------
|987|654|321|
|246|173|985|
|351|928|746|
-------------
|128|537|694|
|634|892|157|
|795|461|832|
-------------
|519|286|473|
|472|319|568|
|863|745|219|
-------------
found 1 solutions

real	0m33.652s
user	0m33.098s
sys	0m0.015s

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 46.42     10.04    10.04 622865043     0.00     0.00  check_row
 23.52     15.13     5.09        1     5.09    21.32  solve
 18.26     19.08     3.95 223473489     0.00     0.00  check_col
 10.02     21.25     2.17 100654218     0.00     0.00  check_region
  0.72     21.40     0.16        2     0.08     0.08  print
  0.39     21.49     0.09                             frame_dummy

I believe that if a GPU was used to enhance this program one would see a great increase of speed. All of the check functions essentially do the same thing, iterating through possible inserted values for any that violate the rules. If one is able to unload all of these iterations onto the GPU then there should be a corresponding increase in speed.