-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku.c
117 lines (101 loc) · 1.61 KB
/
sudoku.c
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
#include <stdio.h>
#include <stdlib.h>
void printBoard();
void readstdin();
void solve(int,int);
int checkRow(int,int);
int checkCol(int,int);
int checkBox(int,int,int);
int board[81];
void main(){
readstdin();
solve(0,0);
printf("Unsolvable sudoku");
}
void solve(int inrow, int incol){
int row,col;
row = inrow;
col = incol;
if(row > 8){
row = 0;
col = col+1;
}
if(col > 8){
printBoard();
exit(0);
}
int value;
if(board[row+col*9] == 0){
for(value = 1; value <= 9; ++value){
if(try(row,col,value) == 0){
board[row+col*9] = value;
solve(row+1,col);
board[row+col*9] = 0;
}
}
}
else{
solve(row+1,col);
}
}
int try(int row, int col, int value){
if(checkRow(row,value) == 1){
return 1;
}
if(checkCol(col,value) == 1){
return 1;
}
if(checkBox(row,col,value) == 1){
return 1;
}
return 0;
}
int checkRow(int row, int value){
int i;
for(i = 0; i < 9; ++i) {
if(board[row+i*9] == value){
return 1;
}
}
return 0;
}
int checkCol(int col, int value){
int i;
for(i = 0; i < 9; ++i) {
if(board[i+col*9] == value){
return 1;
}
}
return 0;
}
int checkBox(int row, int col, int value){
int startx = row/3;
startx = startx*3;
int starty = col/3;
starty = starty*3;
int ix,iy;
for(iy = 0; iy < 3; ++iy){
for(ix = 0; ix < 3; ++ix){
if(board[startx+ix+(starty+iy)*9] == value){
return 1;
}
}
}
return 0;
}
void printBoard(){
int ix,iy;
for(iy = 0; iy < 9; ++iy){
for(ix = 0; ix < 9; ++ix){
printf("%d ",board[ix+iy*9]);
}
printf("\n");
}
}
void readstdin(){
int i,c;
for(i = 0; i < 81; i++) {
c = getchar() - '0';
board[i] = c;
}
}