-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sudoku.cpp
94 lines (81 loc) · 1.85 KB
/
Sudoku.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
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
//Conditional Functional to choose for Safe Spot for the remaining grid numbers
bool isSafe(int mat[][9], int i, int j, int no, int n)
{
//Check for rows and columns
for(int k=0;k<n;k++)
{
if(mat[k][j]==no or mat[i][k]==no)
return false;
}
//Check for SubGrid (SubGrid formula)
int sx= (i/3)*3;
int sy= (j/3)*3;
for(int x=sx;x<sx+3;x++)
{
for(int y=sy;y<sy+3;y++)
{
if(mat[x][y]==no)
return false;
}
}
return true;
}
bool solveSudoku(int mat[][9], int i, int j, int n)
{
//Base case
if(i==n)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
return true;
}
//Recursive Case
if(j==n)
{
return solveSudoku(mat, i+1, 0, n);
}
//Skip PreFilled Cells
if(mat[i][j]!=0)
return solveSudoku(mat, i, j+1, n);
//Cell to be filled, try all possibilities
for(int no=1;no<=9;no++)
{
if(isSafe(mat,i,j,no,n))
{
mat[i][j] = no;
bool solveSubProblem = solveSudoku(mat,i,j+1,n);
if(solveSubProblem==true)
return true;
}
}
//Backtrack step
mat[i][j]=0;
return false;
}
int main()
{
int n=9;
int mat[9][9]=
{{5,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}
};
if(!solveSudoku(mat, 0, 0, n))
cout<<" No Solution Exists!";
return 0;
}