37
edits
Changes
no edit summary
As we can see, negating the image as well as reflecting and enlarging it are all costly operations, and we believe that we can optimize it to take far less time.
== Sudoku Brute Force Solver ==
For this first assignment I decided to look into a brute force sudoku solver to see if it could benefit from parallel programming. The sudoku solver that was investigated was provided by Bryan Smith (https://github.com/bryanesmith/Sudoku-solver).
As is, this solver is quick to solve a 9x9 sudoku puzzle. The time taken to solve a sudoku puzzle is under a second as seen in our time results:
real 0m0.097s
user 0m0.072s
sys 0m0.016s
However if this we were to scale this solver up to solve nxn sized puzzles we would be able to see a use for optimizing this code.
Results from profiling:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
60.00 0.03 0.03 468316 0.00 0.00 SudokuPuzzle::verifyValue(int, int)
20.00 0.04 0.01 468316 0.00 0.00 SudokuPuzzle::printTracerTryingValue(int, int)
20.00 0.05 0.01 1 10.00 50.00 SudokuPuzzle::solve(int, int)
0.00 0.05 0.00 445799 0.00 0.00 SudokuPuzzle::setBoardValue(int, int, int)
0.00 0.05 0.00 2 0.00 0.00 SudokuPuzzle::print()
0.00 0.05 0.00 1 0.00 0.00 _GLOBAL__sub_I__ZN12SudokuPuzzleC2Ev
0.00 0.05 0.00 1 0.00 0.00 _GLOBAL__sub_I_main
0.00 0.05 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 0.05 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 0.05 0.00 1 0.00 50.00 SudokuPuzzle::solve()
0.00 0.05 0.00 1 0.00 0.00 SudokuPuzzle::SudokuPuzzle()
The profiling of this solver shows that the verifyValue function is taking up most of the execution time at 60% and would benefit from optimizing.
=== Assignment 2 ===
=== Assignment 3 ===
