7
edits
Changes
→Assignment 1
== Progress ==
=== Assignment 1 ===
===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. The following run of the program uses a puzzle which is specifically made to play against a back tracking algorithm.
Test run with puzzle:
<pre>
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
</pre>
Flat profile:
<pre>
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
</pre>
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.
=== Assignment 2 ===
=== Assignment 3 ===