Difference between revisions of "Algo holics"

From CDOT Wiki
Jump to: navigation, search
(→‎[Sudoku Solver](C++))
(→‎Team Members)
(49 intermediate revisions by one other user not shown)
Line 2: Line 2:
 
= Project Name Goes here =
 
= Project Name Goes here =
 
== Team Members ==  
 
== Team Members ==  
−
# [mailto:ssdhillon20@myseneca.ca?subject=GPU610 Sukhbeer Dhillon], Responsibilities...
+
# [mailto:ssdhillon20@myseneca.ca?subject=GPU610 Sukhbeer Dhillon], Simple Backpropogation Neural Network
−
# [mailto:gsingh520@myseneca.ca?subject=gpu610 Gurpreet Singh], Some other responsibility
+
# [mailto:gsingh520@myseneca.ca?subject=gpu610 Gurpreet Singh], Sudoku Puzzle Solver
 
# [mailto:egiang1@myseneca.ca?subject=gpu610 Edgar Giang], Some other other responsibility
 
# [mailto:egiang1@myseneca.ca?subject=gpu610 Edgar Giang], Some other other responsibility
 
#[mailto:ssdhillon20@myseneca.ca;gsingh520@myseneca.ca;egiang1@myseneca.ca?subject=GPU610 Email All]
 
#[mailto:ssdhillon20@myseneca.ca;gsingh520@myseneca.ca;egiang1@myseneca.ca?subject=GPU610 Email All]
Line 10: Line 10:
 
=== Assignment 1 ===
 
=== Assignment 1 ===
  
−
[https://github.com/shafeeq/Sudoku here] == [Sudoku Solver](C++) ==
 
  
−
Is it a program that solves Sudoku puzzles(9X9) using Bruteforce algorithm. Either the user can pass a Sudoku files as an input or enter the values manually. Moreover, the file or the manual entry should have strictly 9 rows and 9 columns in them and all the cells should be separated by a space and the cells that needs to be solved should have 0 in them as their value.
+
<h5>SUDOKU PUZZLE SOLVER by Gurpreet Singh</h5>
  
−
== LOGIC ==
+
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.
  
−
In this program the Bruteforce algorithm first put 1 in the first cell and then check if it is violating any rules. If yes, then it increment the value to 2 and check again (The value can vary from 1-9) until it finds the appropriate value. After finding a suitable value for the first cell, it moves to the second cell and put 1 in there and again check again if it violating any rules. If it is discovers that 1 is not allowed in that cell, then the algorithm will increment it to 2 and check again.
+
The original source code can be found at [https://github.com/shafeeq/Sudoku Link]
  
 +
<h5>Logic</h5>
 +
 +
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.
 +
 +
<h5>Compiling the program</h5>
 +
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
 +
 +
 +
<h5>Analysis</h5>
 +
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.
 +
 +
 +
----
  
 
=== Assignment 2 ===
 
=== Assignment 2 ===
 
=== Assignment 3 ===
 
=== Assignment 3 ===

Revision as of 09:11, 22 February 2019


GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary

Project Name Goes here

Team Members

  1. Sukhbeer Dhillon, Simple Backpropogation Neural Network
  2. Gurpreet Singh, Sudoku Puzzle Solver
  3. Edgar Giang, Some other other responsibility
  4. Email All

Progress

Assignment 1

SUDOKU PUZZLE SOLVER by Gurpreet Singh

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.


Assignment 2

Assignment 3

Retrieved from "https://wiki.cdot.senecapolytechnic.ca/w/index.php?title=Algo_holics&oldid=137960"