-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsuduku_backtrack.cpp
More file actions
114 lines (101 loc) · 2.67 KB
/
suduku_backtrack.cpp
File metadata and controls
114 lines (101 loc) · 2.67 KB
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
#include<bits/stdc++.h>
using namespace std;
#define UNASSIGNED 0
#define N 9
bool FindUnassignedLocation(int grid[N][N],int &row,int &col);
bool isSafe(int grid[N][N],int row,int col,int num);
bool SolveSudoku(int grid[N][N]){
int row,col;
if(!FindUnassignedLocation(grid,row,col))
return true;
for(int num=1;num<=9;num++){
if(isSafe(grid,row,col,num)){
grid[row][col] = num;
if(SolveSudoku(grid))
return true;
grid[row][col]= UNASSIGNED;
}
}
return false;
}
bool FindUnassignedLocation(int grid[N][N],int &row,int &col){
for(row=0;row<N;row++)
for(col=0;col<N; col++)
if(grid[row][col]==UNASSIGNED)
return true;
return false;
}
bool UsedInRow(int grid[N][N],int row,int num){
for(int col=0; col<N; col++)
if(grid[row][col]==num)
return true;
return false;
}
bool UsedInCol(int grid[N][N],int col,int num){
for(int row=0;row<N;row++)
if(grid[row][col]==num)
return true;
return false;
}
bool UsedInBox(int grid[N][N],int boxStartRow,int boxStartCol,int num){
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;
}
bool isSafe(int grid[N][N],int row,int col,int num){
return !UsedInRow(grid,row,num)&&
!UsedInCol(grid,col,num)&&
!UsedInBox(grid,row-row%3,col-col%3,num)&&
grid[row][col] == UNASSIGNED;
}
void printGrid(int grid[N][N]){
for(int row=0; row<N;row++){
for(int col=0; col<N; col++)
cout<<grid[row][col]<<" ";
cout<<endl;
}
}
//Driver Code
int main(){
/*
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}};
*/
int grid[N][N];
ifstream inputfile("cross_input1.txt");
string line;
char matrix_original[N][N];
int row=0,col=0;
if(inputfile.is_open()){
while(getline(inputfile,line)){
col=0;
for(int i=0; i< line.size(); i++){
cout<<line[i]<<" ";
matrix_original[row][col] = line[i];
if(matrix_original[row][col] != '.'){
grid[row][col] = matrix_original[row][col] - '0';
}else{
grid[row][col] = UNASSIGNED;
}
col++;
}
cout<<endl;
row++;
}
}
inputfile.close();
if(SolveSudoku(grid)==true)
printGrid(grid);
else
cout<<"No Solution exists";
return 0;
}