C++ Program to Solve Sudoku Problem using BackTracking

«
»
This C++ Program demonstrates the Sudoku Problem using Backtracking.

Here is source code of the C++ Program to solve the Sudoku Problem using BackTracking. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Solve Sudoku Problem using BackTracking
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <cstdlib>
  8. using namespace std;
  9. #define UNASSIGNED 0
  10. #define N 9
  11.  
  12. bool FindUnassignedLocation(int grid[N][N], int &row, int &col);
  13. bool isSafe(int grid[N][N], int row, int col, int num);
  14.  
  15. /* assign values to all unassigned locations for Sudoku solution  
  16.  */
  17. bool SolveSudoku(int grid[N][N])
  18. {
  19.     int row, col;
  20.     if (!FindUnassignedLocation(grid, row, col))
  21.        return true;
  22.     for (int num = 1; num <= 9; num++)
  23.     {
  24.         if (isSafe(grid, row, col, num))
  25.         {
  26.             grid[row][col] = num;
  27.             if (SolveSudoku(grid))
  28.                 return true;
  29.             grid[row][col] = UNASSIGNED;
  30.         }
  31.     }
  32.     return false;
  33. }
  34.  
  35. /* Searches the grid to find an entry that is still unassigned. */
  36. bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
  37. {
  38.     for (row = 0; row < N; row++)
  39.         for (col = 0; col < N; col++)
  40.             if (grid[row][col] == UNASSIGNED)
  41.                 return true;
  42.     return false;
  43. }
  44.  
  45. /* Returns whether any assigned entry n the specified row matches 
  46.    the given number. */
  47. bool UsedInRow(int grid[N][N], int row, int num)
  48. {
  49.     for (int col = 0; col < N; col++)
  50.         if (grid[row][col] == num)
  51.             return true;
  52.     return false;
  53. }
  54.  
  55. /* Returns whether any assigned entry in the specified column matches 
  56.    the given number. */
  57. bool UsedInCol(int grid[N][N], int col, int num)
  58. {
  59.     for (int row = 0; row < N; row++)
  60.         if (grid[row][col] == num)
  61.             return true;
  62.     return false;
  63. }
  64.  
  65. /* Returns whether any assigned entry within the specified 3x3 box matches 
  66.    the given number. */
  67. bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
  68. {
  69.     for (int row = 0; row < 3; row++)
  70.         for (int col = 0; col < 3; col++)
  71.             if (grid[row+boxStartRow][col+boxStartCol] == num)
  72.                 return true;
  73.     return false;
  74. }
  75.  
  76. /* Returns whether it will be legal to assign num to the given row,col location. 
  77.  */
  78. bool isSafe(int grid[N][N], int row, int col, int num)
  79. {
  80.     return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) &&
  81.            !UsedInBox(grid, row - row % 3 , col - col % 3, num);
  82. }
  83.  
  84. /* print grid  */
  85. void printGrid(int grid[N][N])
  86. {
  87.     for (int row = 0; row < N; row++)
  88.     {
  89.         for (int col = 0; col < N; col++)
  90.             cout<<grid[row][col]<<"  ";
  91.         cout<<endl;
  92.     }
  93. }
  94.  
  95. /* Main */
  96. int main()
  97. {
  98.     int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
  99.                       {5, 2, 0, 0, 0, 0, 0, 0, 0},
  100.                       {0, 8, 7, 0, 0, 0, 0, 3, 1},
  101.                       {0, 0, 3, 0, 1, 0, 0, 8, 0},
  102.                       {9, 0, 0, 8, 6, 3, 0, 0, 5},
  103.                       {0, 5, 0, 0, 9, 0, 6, 0, 0},
  104.                       {1, 3, 0, 0, 0, 0, 2, 5, 0},
  105.                       {0, 0, 0, 0, 0, 0, 0, 7, 4},
  106.                       {0, 0, 5, 2, 0, 6, 3, 0, 0}};
  107.     if (SolveSudoku(grid) == true)
  108.           printGrid(grid);
  109.     else
  110.         cout<<"No solution exists"<<endl;
  111.     return 0;
  112. }

advertisement
$ g++ sudoku.cpp
$ a.out
 
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
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn