coding-problems/sudoku.cpp at main · Masterroy1210/coding-problems · GitHub

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>

using namespace std;

#define N 9


bool findemptylocation(int grid[N][N],int &row,int &column){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(grid[i][j]==0){
                row=i;
                column=j;
                return true;
            }
        }
    }
    return false;
}


bool issaferow(int grid[N][N],int row,int num){
    for(int i=0;i<N;i++){
        if(grid[row][i]==num){
            return false;
        }
    }
    return true;
}
bool issafecolumn(int grid[N][N],int column,int num){
    for(int i=0;i<N;i++){
        if(grid[i][column]==num){
            return false;
        }

    }
    return true;
}

bool issafebox(int grid[N][N],int row,int column,int num)
{
    int rowfactor=row-(row%3);
    int columnfactor=column-(column%3);
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(grid[i+rowfactor][j+columnfactor]==num){
                return false;
            }
        }
    }
return true;
}
bool issafe(int grid[N][N],int row,int column,int num){

    if(issaferow(grid,row,num)&& issafecolumn(grid,column,num)&&issafebox(grid,row,column,num)){
        return true;
    }
    return false;


}


bool solvesudoku(int grid[N][N]){
    int row,column;

    if(!findemptylocation(grid,row,column)){
        return true;
    }
    for(int i=1;i<=9;i++){
        if(issafe(grid,row,column,i)){
            grid[row][column]=i;
            if(solvesudoku(grid)){
                return true;

            }
            grid[row][column]=0;


        }
    }
    return false;

}


int main(){

    int grid[N][N];
    for(int i=0;i<N;i++){
        string s;
        cin>>s;
        for(int j=0;j<s.length();j++){

            grid[i][j]=s[j]-'0';
        }


    }
    bool result= solvesudoku(grid);
    if(result){
    cout<<"Displaying the Grid"<<endl;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout<<grid[i][j];

        }
        cout<<endl;
    }
    }
    return 0;


}