# Sudoku Problem using BackTracking in C++

«
»
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. `}`

```\$ 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)

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 