-
Notifications
You must be signed in to change notification settings - Fork 141
/
DSA.cpp
81 lines (81 loc) · 2.5 KB
/
DSA.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#define N 9
using namespace std;
int grid[N][N] = {
{3, 0, 6, 5, 0, 8, 4, 0, 0},
{5, 2, 0, 0, 0, 0, 0, 0, 0},
{0, 8, 7, 0, 0, 0, 0, 3, 1},
{0, 0, 3, 0, 1, 0, 0, 8, 0},
{9, 0, 0, 8, 6, 3, 0, 0, 5},
{0, 5, 0, 0, 9, 0, 6, 0, 0},
{1, 3, 0, 0, 0, 0, 2, 5, 0},
{0, 0, 0, 0, 0, 0, 0, 7, 4},
{0, 0, 5, 2, 0, 6, 3, 0, 0}
};
bool isPresentInCol(int col, int num){ //check whether num is present in col or not
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInRow(int row, int num){ //check whether num is present in row or not
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
bool isPresentInBox(int boxStartRow, int boxStartCol, int num){
//check whether num is present in 3x3 box or not
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
void sudokuGrid(){ //print the sudoku grid after solve
for (int row = 0; row < N; row++){
for (int col = 0; col < N; col++){
if(col == 3 || col == 6)
cout << " | ";
cout << grid[row][col] <<" ";
}
if(row == 2 || row == 5){
cout << endl;
for(int i = 0; i<N; i++)
cout << "---";
}
cout << endl;
}
}
bool findEmptyPlace(int &row, int &col){ //get empty location and update row and column
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == 0) //marked with 0 is empty
return true;
return false;
}
bool isValidPlace(int row, int col, int num){
//when item not found in col, row and current 3x3 box
return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3 ,
col - col%3, num);
}
bool solveSudoku(){
int row, col;
if (!findEmptyPlace(row, col))
return true; //when all places are filled
for (int num = 1; num <= 9; num++){ //valid numbers are 1 - 9
if (isValidPlace(row, col, num)){ //check validation, if yes, put the number in the grid
grid[row][col] = num;
if (solveSudoku()) //recursively go for other rooms in the grid
return true;
grid[row][col] = 0; //turn to unassigned space when conditions are not satisfied
}
}
return false;
}
int main(){
if (solveSudoku() == true)
sudokuGrid();
else
cout << "No solution exists";
}