Algo holics

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

Project Name Goes here

Team Members

1. Sukhbeer Dhillon, Responsibilities...
2. Gurpreet Singh, Some other responsibility
3. Edgar Giang, Some other other responsibility
4. Email All

Progress

Assignment 1

Sudoku Solver

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. Lastly, 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.

The original source code can be found at Link

LOGIC

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 and if not even a single value from the range of 0-9 satisfies the cell, then the algorithm will iterate back to the previous cell and increment the value and try the whole process again. By following the same logic it will solve the whole 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.

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 Flat profile we can see that the program took no time in finding the solution. 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 Flat profile for the following looks like:

Flat profile:
Each sample counts as 0.01 seconds.
 %   cumulative   self              self     total
time   seconds   seconds    calls   s/call   s/call  name
47.61     13.27    13.27 622577597     0.00     0.00  checkRow(int, int)
19.27     18.63     5.37 223365661     0.00     0.00  checkColumn(int, int)
14.41     22.65     4.01 157353814     0.00     0.00  placeNum(int, int)
12.09     26.01     3.37 100608583     0.00     0.00  checkSquare(int, int, int)
 3.53     27.00     0.98 69175252     0.00     0.00  goBack(int&, int&)
 3.02     27.84     0.84        1     0.84    27.84  solveSudoku()
 0.04     27.85     0.01        1     0.01     0.01  _GLOBAL__sub_I_sudoku
 0.04     27.86     0.01        1     0.01     0.01  storePositions()
 0.00     27.86     0.00        2     0.00     0.00  print(int (*) [9])
 0.00     27.86     0.00        1     0.00     0.00  _GLOBAL__sub_I_temp
 0.00     27.86     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)
 0.00     27.86     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)

---