22
edits
Changes
→Assignment 1: Sudoku Solver
// A Backtracking program in C++ to solve Sudoku problem
return 0;
}
Obtaining flat profiles and call graphs on matrix environment:
$ g++ sudokuC.cpp -std=c++0x -o Sudoku
$ ./Sudoku
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
$ gprof -p -b ./Sudoku gmon.out > 9x9.flt
$ gprof -q -b ./Sudoku gmon.out > 9x9.clg
$ g++ sudokuC16.cpp -std=c++0x -pg -o Sudoku16
$ ./Sudoku16
12 8 6 516 1 2 31314 410 9 71115
11 915131210 7 5 2 6 816 414 1 3
4 316 71514 813 91211 1 6 5 210
114 210 911 4 615 3 5 7 8131216
16 6 415 5 213 7 1 910 811 31412
511 9 2 4 312151416 613 7 110 8
1012 3 8 1 61114 4 5 7 216 91513
13 1 714 8 91016 3111215 2 4 5 6
2 71316 6 4 51211 8 9141015 3 1
6 411 914 7 3 210 1151213 816 5
141510 11113 9 8 5 416 312 2 6 7
3 5 812101516 1 7 213 61411 4 9
7 2 5 313121411 610 1 91516 8 4
91014 6 7 8 1 41615 2 5 3121311
813 1 4 216151012 7 311 5 6 914
15161211 3 5 6 9 81314 4 110 7 2
$ gprof -p -b ./Sudoku16 gmon.out > 16x16.flt
$ gprof -q -b ./Sudoku16 gmon.out > 16x16.clg
$ g++ sudokuC25.cpp -std=c++0x -pg -o Sudoku25
$ ./Sudoku25
111 42025241915171021 8181422 612 9 316 2 71323 5
5 2192324 82212 9 316 6 7201718212514131011 4 115
1714 9 6 32521 5 7201110 2 113 4 82423151812162219
16 721 818 4 2131123 51915241210201722 1 9 62514 3
101315122214 118 61623 925 4 3 7 51911 2 824202117
12 11110 6 513232415 716 817212519 3 4 92214 22018
8191321 916 42512 215 3 511201417231822 110 724 6
4171418 7 9 322211925 124 223 5132010 61615 81112
22 3241523182011 1 71013 4 61416 21221 8 5191725 9
2016 225 510 8 61417 922121819 11115 724 3232113 4
1325 3 510 22314 418221517192420 7 1 9211216 6 811
1423 124121916 815 6 2 7202510 3 413171121 9 51822
7 818111720242122 9 3 4 11216 2 61419 52513151023
22216 9211711 71025 8 51413 6122418152319 4 1 320
6152019 41312 3 5 118112321 9 822162510 71724 214
211812 216 71019 313 12422 9 41115 6201417 823 525
924 813 1 625 420121714 3 718231622 51911211015 2
231022 71521 5 91814 62016 81117 1 21325 4 3191224
25 5 61411 117 2 8241321192315 9 31012 420182216 7
32017 4192215162311122510 5 22118 824 7 6 114 913
19 62322 81518 125 414 2 9 3 7131011162024 5121721
15 4 51714 3 72419 8202311102522 921 11213 218 616
1112 7162023 617 22124181315 11925 5 8 31422 9 410
18 925 1 21114101322 4122116 52423 7 6171520 319 8
242110 31312 92016 51917 622 81514 4 218232511 7 1
$ gprof -p -b ./Sudoku25 gmon.out > 25x25.flt
$ gprof -q -b ./Sudoku25 gmon.out > 25x25.clg
For 9x9 Sudoku Puzzle (3x3 squares)
0.00 0.00 0.00 1 0.00 0.00 SolveSudoku(int (*) [9])
0.00 0.00 0.00 1 0.00 0.00 printGrid(int (*) [9])
Call graph
granularity: each sample hit covers 2 byte(s) no time propagated
index % time self children called name
0.00 0.00 6732/6732 SolveSudoku(int (*) [9]) [13]
[8] 0.0 0.00 0.00 6732 isSafe(int (*) [9], int, int, int) [8]
0.00 0.00 6732/6732 UsedInRow(int (*) [9], int, int) [9]
0.00 0.00 2185/2185 UsedInCol(int (*) [9], int, int) [10]
0.00 0.00 1078/1078 UsedInBox(int (*) [9], int, int, int) [11]
-----------------------------------------------
0.00 0.00 6732/6732 isSafe(int (*) [9], int, int, int) [8]
[9] 0.0 0.00 0.00 6732 UsedInRow(int (*) [9], int, int) [9]
-----------------------------------------------
0.00 0.00 2185/2185 isSafe(int (*) [9], int, int, int) [8]
[10] 0.0 0.00 0.00 2185 UsedInCol(int (*) [9], int, int) [10]
-----------------------------------------------
0.00 0.00 1078/1078 isSafe(int (*) [9], int, int, int) [8]
[11] 0.0 0.00 0.00 1078 UsedInBox(int (*) [9], int, int, int) [11]
-----------------------------------------------
0.00 0.00 770/770 SolveSudoku(int (*) [9]) [13]
[12] 0.0 0.00 0.00 770 FindUnassignedLocation(int (*) [9], int&, int&) [12]
-----------------------------------------------
769 SolveSudoku(int (*) [9]) [13]
0.00 0.00 1/1 main [6]
[13] 0.0 0.00 0.00 1+769 SolveSudoku(int (*) [9]) [13]
0.00 0.00 6732/6732 isSafe(int (*) [9], int, int, int) [8]
0.00 0.00 770/770 FindUnassignedLocation(int (*) [9], int&, int&) [12]
769 SolveSudoku(int (*) [9]) [13]
-----------------------------------------------
0.00 0.00 1/1 main [6]
[14] 0.0 0.00 0.00 1 printGrid(int (*) [9]) [14]
-----------------------------------------------
Index by function name
[13] SolveSudoku(int (*) [9]) [11] UsedInBox(int (*) [9], int, int, int) [14] printGrid(int (*) [9])
[12] FindUnassignedLocation(int (*) [9], int&, int&) [10] UsedInCol(int (*) [9], int, int)
[8] isSafe(int (*) [9], int, int, int) [9] UsedInRow(int (*) [9], int, int)
For 16x16 Sudoku Puzzle (4x4 squares)
0.01 38.40 0.01 frame_dummy
0.00 38.40 0.00 1 0.00 0.00 printGrid(int (*) [16])
Call graph
granularity: each sample hit covers 2 byte(s) for 0.03% of 36.85 seconds
index % time self children called name
<spontaneous>
[1] 100.0 0.00 36.85 main [1]
1.93 34.93 1/1 SolveSudoku(int (*) [16]) [2]
0.00 0.00 1/1 printGrid(int (*) [16]) [14]
-----------------------------------------------
28071635 SolveSudoku(int (*) [16]) [2]
1.93 34.93 1/1 main [1]
[2] 100.0 1.93 34.93 1+28071635 SolveSudoku(int (*) [16]) [2]
1.69 19.09 449145092/449145092 isSafe(int (*) [16], int, int, int) [3]
14.14 0.00 28071636/28071636 FindUnassignedLocation(int (*) [16], int&, int&) [4]
28071635 SolveSudoku(int (*) [16]) [2]
-----------------------------------------------
1.69 19.09 449145092/449145092 SolveSudoku(int (*) [16]) [2]
[3] 56.4 1.69 19.09 449145092 isSafe(int (*) [16], int, int, int) [3]
13.58 0.00 449145092/449145092 UsedInRow(int (*) [16], int, int) [5]
3.54 0.00 120354547/120354547 UsedInCol(int (*) [16], int, int) [6]
1.98 0.00 41212484/41212484 UsedInBox(int (*) [16], int, int, int) [7]
-----------------------------------------------
14.14 0.00 28071636/28071636 SolveSudoku(int (*) [16]) [2]
[4] 38.4 14.14 0.00 28071636 FindUnassignedLocation(int (*) [16], int&, int&) [4]
-----------------------------------------------
13.58 0.00 449145092/449145092 isSafe(int (*) [16], int, int, int) [3]
[5] 36.8 13.58 0.00 449145092 UsedInRow(int (*) [16], int, int) [5]
-----------------------------------------------
3.54 0.00 120354547/120354547 isSafe(int (*) [16], int, int, int) [3]
[6] 9.6 3.54 0.00 120354547 UsedInCol(int (*) [16], int, int) [6]
-----------------------------------------------
1.98 0.00 41212484/41212484 isSafe(int (*) [16], int, int, int) [3]
[7] 5.4 1.98 0.00 41212484 UsedInBox(int (*) [16], int, int, int) [7]
-----------------------------------------------
0.00 0.00 1/1 main [1]
[14] 0.0 0.00 0.00 1 printGrid(int (*) [16]) [14]
-----------------------------------------------
Index by function name
[2] SolveSudoku(int (*) [16]) [7] UsedInBox(int (*) [16], int, int, int) [14] printGrid(int (*) [16])
[4] FindUnassignedLocation(int (*) [16], int&, int&) [6] UsedInCol(int (*) [16], int, int)
[3] isSafe(int (*) [16], int, int, int) [5] UsedInRow(int (*) [16], int, int)
For 25x25 Sudoku Puzzle (5x5 squares)
0.01 2167.56 0.17 frame_dummy
0.00 2167.56 0.00 1 0.00 0.00 printGrid(int (*) [25])
Call graph
granularity: each sample hit covers 2 byte(s) for 0.00% of 2085.44 seconds
index % time self children called name
<spontaneous>
[1] 100.0 0.00 2085.30 main [1]
97.03 1988.27 1/1 SolveSudoku(int (*) [25]) [2]
0.00 0.00 1/1 printGrid(int (*) [25]) [14]
-----------------------------------------------
876012757 SolveSudoku(int (*) [25]) [2]
97.03 1988.27 1/1 main [1]
[2] 100.0 97.03 1988.27 1+876012757 SolveSudoku(int (*) [25]) [2]
101.19 1361.55 425478951/425478951 isSafe(int (*) [25], int, int, int) [3]
525.53 0.00 876012758/876012758 FindUnassignedLocation(int (*) [25], int&, int&) [5]
876012757 SolveSudoku(int (*) [25]) [2]
-----------------------------------------------
101.19 1361.55 425478951/425478951 SolveSudoku(int (*) [25]) [2]
[3] 70.1 101.19 1361.55 425478951 isSafe(int (*) [25], int, int, int) [3]
1011.03 0.00 425478951/425478951 UsedInRow(int (*) [25], int, int) [4]
259.56 0.00 590817023/590817023 UsedInCol(int (*) [25], int, int) [6]
90.96 0.00 1355081265/1355081265 UsedInBox(int (*) [25], int, int, int) [7]
-----------------------------------------------
1011.03 0.00 425478951/425478951 isSafe(int (*) [25], int, int, int) [3]
[4] 48.5 1011.03 0.00 425478951 UsedInRow(int (*) [25], int, int) [4]
-----------------------------------------------
525.53 0.00 876012758/876012758 SolveSudoku(int (*) [25]) [2]
[5] 25.2 525.53 0.00 876012758 FindUnassignedLocation(int (*) [25], int&, int&) [5]
-----------------------------------------------
259.56 0.00 590817023/590817023 isSafe(int (*) [25], int, int, int) [3]
[6] 12.4 259.56 0.00 590817023 UsedInCol(int (*) [25], int, int) [6]
-----------------------------------------------
90.96 0.00 1355081265/1355081265 isSafe(int (*) [25], int, int, int) [3]
[7] 4.4 90.96 0.00 1355081265 UsedInBox(int (*) [25], int, int, int) [7]
-----------------------------------------------
<spontaneous>
[8] 0.0 0.14 0.00 frame_dummy [8]
-----------------------------------------------
0.00 0.00 1/1 main [1]
[14] 0.0 0.00 0.00 1 printGrid(int (*) [25]) [14]
-----------------------------------------------
Index by function name
[2] SolveSudoku(int (*) [25]) [7] UsedInBox(int (*) [25], int, int, int) [14] printGrid(int (*) [25])
[5] FindUnassignedLocation(int (*) [25], int&, int&) [6] UsedInCol(int (*) [25], int, int) [8] frame_dummy
[3] isSafe(int (*) [25], int, int, int) [4] UsedInRow(int (*) [25], int, int)
=== Assignment 1: EasyBMP ===