Algo holics
GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary
Contents
Project Name Goes here
Team Members
- Sukhbeer Dhillon, Responsibilities...
- Gurpreet Singh, Some other responsibility
- Edgar Giang, Some other other responsibility
- Email All
Progress
Assignment 1
Sudoku Solver
Is it a program that solves Sudoku puzzles(9X9) using Bruteforce algorithm. The user can either pass a Sudoku files as an input or enter the values manually. Moreover, the file or the manual entry must strictly have 9 rows and 9 columns in them. Last but not the least, all the cells must be separated by a space and the cells that needs to be solved must have 0 in them as their value.
The original source code can be found at Link
Logic
In this program the Bruteforce algorithm first put 1 in the first cell. Then it moves to the second cell and put 1 in there and check if it satisfies all the rules and conditions. If it don't, then the algorithm will increment it's value to 2 and then check again. The value can change from 0-9 to find the correct value for a cell. If none of the value from the range of 0-9 satisfies the cell, then the program will iterate back and change the value of the first cell to 2 and then try the whole process again. In this way it will solve the puzzle.
Compiling the program
Enter the following commands:
g++ -std=c++0x -pg solver.cpp checks.cpp checksolution.cpp -o a a fileName
-pg directs the compiler to include the executable code required for profiling.
-o directs the compiler to name the executable a.
If we run the sample-puzzle-1 (level- easy) file, which has the following text inside it:
0 6 0 0 0 0 9 7 2
0 5 0 0 0 2 0 0 3
0 7 0 3 9 0 5 0 0
2 0 0 0 0 5 4 0 8
0 0 0 0 0 0 0 0 0
3 0 1 8 0 0 0 0 6
0 0 4 0 2 3 0 8 0
7 0 0 9 0 0 0 2 0
9 2 5 0 0 0 0 4 0
The output will be:
1 6 3 4 5 8 9 7 2
4 5 9 7 1 2 8 6 3
8 7 2 3 9 6 5 1 4
2 9 7 1 6 5 4 3 8
5 8 6 2 3 4 1 9 7
3 4 1 8 7 9 2 5 6
6 1 4 5 2 3 7 8 9
7 3 8 9 4 1 6 2 5
9 2 5 6 8 7 3 4 1
Analysis
To analyze the call graph, enter the following command:
gprof -q -b a> a.clg
-q directs the profiler (gprof) to output a call graph.
-b directs the profiler to omit detailed explanations of the column headings from the output.
The call graph for the above execution looks like:
Call graph
granularity: each sample hit covers 2 byte(s) no time propagated
index % time self children called name
0.00 0.00 4539/4539 placeNum(int, int) [10]
[8] 0.0 0.00 0.00 4539 checkRow(int, int) [8]
-----------------------------------------------
0.00 0.00 1620/1620 placeNum(int, int) [10]
[9] 0.0 0.00 0.00 1620 checkColumn(int, int) [9]
-----------------------------------------------
0.00 0.00 1120/1120 solveSudoku() [16]
[10] 0.0 0.00 0.00 1120 placeNum(int, int) [10]
0.00 0.00 4539/4539 checkRow(int, int) [8]
0.00 0.00 1620/1620 checkColumn(int, int) [9]
0.00 0.00 698/698 checkSquare(int, int, int) [11]
-----------------------------------------------
0.00 0.00 698/698 placeNum(int, int) [10]
[11] 0.0 0.00 0.00 698 checkSquare(int, int, int) [11]
-----------------------------------------------
0.00 0.00 476/476 solveSudoku() [16]
[12] 0.0 0.00 0.00 476 goBack(int&, int&) [12]
-----------------------------------------------
0.00 0.00 2/2 main [6]
[13] 0.0 0.00 0.00 2 print(int (*) [9]) [13]
-----------------------------------------------
0.00 0.00 1/1 __libc_csu_init [30]
[14] 0.0 0.00 0.00 1 _GLOBAL__sub_I_sudoku [14]
0.00 0.00 1/1 __static_initialization_and_destruction_0(int, int) [18]
-----------------------------------------------
0.00 0.00 1/1 __libc_csu_init [30]
[15] 0.0 0.00 0.00 1 _GLOBAL__sub_I_temp [15]
0.00 0.00 1/1 __static_initialization_and_destruction_0(int, int) [19]
-----------------------------------------------
0.00 0.00 1/1 main [6]
[16] 0.0 0.00 0.00 1 solveSudoku() [16]
0.00 0.00 1120/1120 placeNum(int, int) [10]
0.00 0.00 476/476 goBack(int&, int&) [12]
-----------------------------------------------
0.00 0.00 1/1 main [6]
[17] 0.0 0.00 0.00 1 storePositions() [17]
-----------------------------------------------
0.00 0.00 1/1 _GLOBAL__sub_I_sudoku [14]
[18] 0.0 0.00 0.00 1 __static_initialization_and_destruction_0(int, int) [18]
-----------------------------------------------
0.00 0.00 1/1 _GLOBAL__sub_I_temp [15]
[19] 0.0 0.00 0.00 1 __static_initialization_and_destruction_0(int, int) [19]
-----------------------------------------------
Index by function name
[14] _GLOBAL__sub_I_sudoku [16] solveSudoku() [13] print(int (*) [9])
[15] _GLOBAL__sub_I_temp [17] storePositions() [12] goBack(int&, int&)
[9] checkColumn(int, int) [18] __static_initialization_and_destruction_0(int, int) [8] checkRow(int, int)
[11] checkSquare(int, int, int) [19] __static_initialization_and_destruction_0(int, int) [10] placeNum(int, int)
From the above Call graph we can see that the program took no time in finding the solution and the maximum number of calls were made to the checkRow, checkColumn and checkSquare function. However, to get a better understanding of the program let's try a harder Sudoku puzzle.
If we run the sample-puzzle-2-hard (Level- hard) file, which has the following text inside it:
0 0 0 0 0 0 0 0 0
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 0 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
0 0 0 0 4 0 0 0 9
The output will be:
9 8 7 6 5 4 3 2 1
2 4 6 1 7 3 9 8 5
3 5 1 9 2 8 7 4 6
1 2 8 5 3 7 6 9 4
6 3 4 8 9 2 1 5 7
7 9 5 4 6 1 8 3 2
5 1 9 2 8 6 4 7 3
4 7 2 3 1 9 5 6 8
8 6 3 7 4 5 2 1 9
The Call graph for the following looks like:
Call graph
granularity: each sample hit covers 2 byte(s) for 0.04% of 26.79 seconds
index % time self children called name
<spontaneous>
[1] 100.0 0.00 26.78 main [1]
0.68 26.09 1/1 solveSudoku() [2]
0.01 0.00 1/1 storePositions() [9]
0.00 0.00 2/2 print(int (*) [9]) [17]
-----------------------------------------------
0.68 26.09 1/1 main [1]
[2] 99.9 0.68 26.09 1 solveSudoku() [2]
3.64 21.56 157353814/157353814 placeNum(int, int) [3]
0.89 0.00 69175252/69175252 goBack(int&, int&) [7]
-----------------------------------------------
3.64 21.56 157353814/157353814 solveSudoku() [2]
[3] 94.1 3.64 21.56 157353814 placeNum(int, int) [3]
13.31 0.00 622577597/622577597 checkRow(int, int) [4]
5.04 0.00 223365661/223365661 checkColumn(int, int) [5]
3.21 0.00 100608583/100608583 checkSquare(int, int, int) [6]
-----------------------------------------------
13.31 0.00 622577597/622577597 placeNum(int, int) [3]
[4] 49.7 13.31 0.00 622577597 checkRow(int, int) [4]
-----------------------------------------------
5.04 0.00 223365661/223365661 placeNum(int, int) [3]
[5] 18.8 5.04 0.00 223365661 checkColumn(int, int) [5]
-----------------------------------------------
3.21 0.00 100608583/100608583 placeNum(int, int) [3]
[6] 12.0 3.21 0.00 100608583 checkSquare(int, int, int) [6]
-----------------------------------------------
0.89 0.00 69175252/69175252 solveSudoku() [2]
[7] 3.3 0.89 0.00 69175252 goBack(int&, int&) [7]
-----------------------------------------------
0.01 0.00 1/1 __libc_csu_init [10]
[8] 0.0 0.01 0.00 1 _GLOBAL__sub_I_sudoku [8]
0.00 0.00 1/1 __static_initialization_and_destruction_0(int, int) [19]
-----------------------------------------------
0.01 0.00 1/1 main [1]
[9] 0.0 0.01 0.00 1 storePositions() [9]
-----------------------------------------------
<spontaneous>
[10] 0.0 0.00 0.01 __libc_csu_init [10]
0.01 0.00 1/1 _GLOBAL__sub_I_sudoku [8]
0.00 0.00 1/1 _GLOBAL__sub_I_temp [18]
-----------------------------------------------
0.00 0.00 2/2 main [1]
[17] 0.0 0.00 0.00 2 print(int (*) [9]) [17]
-----------------------------------------------
0.00 0.00 1/1 __libc_csu_init [10]
[18] 0.0 0.00 0.00 1 _GLOBAL__sub_I_temp [18]
0.00 0.00 1/1 __static_initialization_and_destruction_0(int, int) [20]
-----------------------------------------------
0.00 0.00 1/1 _GLOBAL__sub_I_sudoku [8]
[19] 0.0 0.00 0.00 1 __static_initialization_and_destruction_0(int, int) [19]
-----------------------------------------------
0.00 0.00 1/1 _GLOBAL__sub_I_temp [18]
[20] 0.0 0.00 0.00 1 __static_initialization_and_destruction_0(int, int) [20]
-----------------------------------------------
Index by function name
[8] _GLOBAL__sub_I_sudoku [2] solveSudoku() [17] print(int (*) [9])
[18] _GLOBAL__sub_I_temp [9] storePositions() [7] goBack(int&, int&)
[5] checkColumn(int, int) [19] __static_initialization_and_destruction_0(int, int) [4] checkRow(int, int)
[6] checkSquare(int, int, int) [20] __static_initialization_and_destruction_0(int, int) [3] placeNum(int, int)
From the above Call graph we can see that for a harder Sudoku puzzle, the time increased significantly. Moreover, it can also be seen that almost 50% of the time is consumed by the checkRow function, 18.8% by checkColumn and finally 12% by the checkSquare function. Thousand of calls were made to these 3 functions, if we parallelizing these functions then the efficiency of the program can be increased significantly.
