37
edits
Changes
→Sudoku Brute Force Solver
The profiling of this solver shows that the verifyValue function is taking up most of the execution time at 60% which is expected as this function checks all for all of the collisions for the guessed values. This would be the function we would want to optimize however this may not be the easiest of tasks as it seems it has some data dependencies.
After modifying the code to handle nxn size sudoku puzzles we can get a better look at the execution time of the algorithm.
These are the time results for solving a 16x16 puzzle:
real 0m7.631s
user 0m7.592s
sys 0m0.012s
And Profiling results:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
90.35 5.38 5.38 35639645 0.00 0.00 SudokuPuzzle::verifyValue(int, int)
5.79 5.73 0.34 1 0.34 5.95 SudokuPuzzle::solve(int, int)
2.35 5.87 0.14 34877040 0.00 0.00 SudokuPuzzle::setBoardValue(int, int, int)
1.34 5.95 0.08 35639645 0.00 0.00 SudokuPuzzle::printTracerTryingValue(int, int)
0.17 5.96 0.01 1 0.01 5.96 SudokuPuzzle::solve()
0.00 5.96 0.00 2 0.00 0.00 SudokuPuzzle::print()
0.00 5.96 0.00 1 0.00 0.00 _GLOBAL__sub_I__ZN12SudokuPuzzleC2Ev
0.00 5.96 0.00 1 0.00 0.00 _GLOBAL__sub_I_main
0.00 5.96 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 5.96 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
0.00 5.96 0.00 1 0.00 0.00 SudokuPuzzle::CreateBoard()
0.00 5.96 0.00 1 0.00 0.00 SudokuPuzzle::SudokuPuzzle(int)
0.00 5.96 0.00 1 0.00 0.00 SudokuPuzzle::~SudokuPuzzle()
It is clear that the verifyValue function takes up majority of the execution time being called 356,39,645 times and taking 5.38 seconds of the total execution time.
=== Assignment 2 ===
=== Assignment 3 ===
