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
129
130
131
132
133
134
|
#define SIZE 6
//sudoku problem
char col1up = 4, col2up = 3, col3up = 2, col4up = 1, col1down = 1, col2down = 2, col3down = 2, col4down = 2, row1left = 4, row2left = 3, row3left = 2, row4left = 1, row1right = 1, row2right = 2, row3right = 2, row4right = 2;
char a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, i = 0, j = 0, k = 0, l = 0, m = 0, n = 0, o = 0, p = 0;
char matrix[6][6] = {
{0, col1up,col2up,col3up,col4up, 0},
{row1left,a,b,c,d,row1right},
{row2left,e,f,g,h,row2right},
{row3left,i,j,k,l,row3right},
{row4left,m,n,o,p,row4right},
{0, col1down,col2down,col3down,col4down, 0},
};
//function to print sudoku
void print_sudoku()
{
int i,j;
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
printf("%d\t",matrix[i][j]);
}
printf("\n\n");
}
}
//function to check if all cells are assigned or not
//if there is any unassigned cell (cell that is set to 0)
//then this function will change the values of
//row and col accordingly
int number_unassigned(int *row, int *col)
{
int num_unassign = 0;
int i,j;
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
//cell is unassigned
if(matrix[i][j] == 0)
{
//changing the values of row and col
*row = i;
*col = j;
//there is one or more unassigned cells
num_unassign = 1;
return num_unassign;
}
}
}
return num_unassign;
}
//function to check if we can put a
//value in a paticular cell or not
int is_safe(int n, int r, int c)
{
int i,j;
//checking in row
for(i=0;i<SIZE;i++)
{
//there is a cell with same value
if(matrix[r][i] == n)
return 0;
}
//checking column
for(i=0;i<SIZE;i++)
{
//there is a cell with the value equal to i
if(matrix[i][c] == n)
return 0;
}
//checking sub matrix
int row_start = (r/3)*3;
int col_start = (c/3)*3;
for(i=row_start;i<row_start+3;i++)
{
for(j=col_start;j<col_start+3;j++)
{
if(matrix[i][j]==n)
return 0;
}
}
return 1;
}
//function to solve sudoku
//using backtracking
int solve_sudoku()
{
int row;
int col;
//if all cells are assigned then the sudoku is already solved
//pass by reference because number_unassigned will change the values of row and col
if(number_unassigned(&row, &col) == 0)
return 1;
int n,i;
//number between 1 to 9
for(i=1;i<=SIZE;i++)
{
//if we can assign i to the cell or not
//the cell is matrix[row][col]
if(is_safe(i, row, col))
{
matrix[row][col] = i;
//backtracking
if(solve_sudoku())
return 1;
//if we can't proceed with this solution
//reassign the cell
matrix[row][col]=0;
}
}
return 0;
}
int main()
{
if (solve_sudoku())
print_sudoku();
else
printf("No solution\n");
return 0;
}
|
