出处： http://acm.hnu.cn:8080/online/?action=problem&type=show&id=11203&courseid=0
|
Sudoku
|
|
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
|
Total submit users: 10, Accepted users: 10 |
|
Problem 11203 :
Special judge
|
|
Problem description
|
 A Sudoku puzzle, once solved, is a 9x9 grid of digits organized as a 3x3 grid of smaller 3x3 units. Each of the nine rows must contain every positive digits exactly once, as do each column and also each 3x3 unit. The puzzle is to start from a partially filled 9x9 grid and to fill in the remaining cells using only logic. The puzzle maker usually makes sure that the solution will be unique and that it can be reached using deduction only, without guessing.
This number placing game is gaining popularity in the west, and every second newspaper publishes weekly instances of the puzzle. Somewhere at the head of one such newspaper, someone decided that buying individual instances from a puzzle maker would be too expansive, and instead decided to steal puzzles from other newspapers and also to print randomly generated Sudoku-like grids.
One week later, his assistant gets stuck with the job of printing the solution to the Sudoku puzzles his boss previously published. Unfortunately, his boss doesn’t have those solutions, the randomly generated problems don’t have any solution, and he doesn’t even remember which is which. In despair, the assistant calls for your help.
|
|
Input
|
The first line of the input will contain the number of test cases. Each test case will consist of a 9 by 9 grid of characters, where each character will either be ‘?’ or a digit between 1 and 9 inclusively.
|
|
Output
|
For each test case, you must print back the grid to the standard input, replacing each question mark with an appropriate digit to solve the Sudoku. If a test case does not allow any solution, output ”impossible” instead of a completed grid. If a test case do allow a solution, you can assume that the solution will be unique, and that theoretically it could be reached without guessing.
Test cases are separated by “---” both in the input and in the output.
|
|
Sample Input
|
3
??4??9??8
?3??5??1?
7??4??2??
3??8??1??
?5?????9?
??6??1??2
??8??3??1
?2??4??5?
6??1??7??
---
??4??9??8
?3??5??1?
7??4??2??
3??8??1??
?5?????9?
??6??1??2
??8??3??1
62??4??5?
6??1??7??
---
3?1????76
7??9?????
2?5?3????
?????64?1
???2?1???
1?25?????
????8?9?3
?????9??4
51????7?8
|
|
Sample Output
|
264319578
839257416
715486239
372894165
451632897
986571342
548763921
127948653
693125784
---
impossible
---
391452876
764918532
285637149
953876421
678241395
142593687
426785913
837169254
519324768
|
1
#include
<
iostream
>
2
3
using
namespace
std;
4
5
bool
x[
9
][
10
];
6
bool
y[
9
][
10
];
7
bool
z[
9
][
10
];
8
int
result[
9
][
9
];
9
int
num
=
0
;
10
11
12
int
GetID(
int
x,
int
y )
13
{
14
if
( x
<
3
&&
y
<
3
)
15
return
0
;
16
else
if
( x
<
3
&&
y
>=
3
&&
y
<
6
)
17
return
1
;
18
else
if
( x
<
3
&&
y
>=
6
&&
y
<
9
)
19
return
2
;
20
else
if
( x
>=
3
&&
x
<
6
&&
y
<
3
)
21
return
3
;
22
else
if
( x
>=
3
&&
x
<
6
&&
y
>=
3
&&
y
<
6
)
23
return
4
;
24
else
if
( x
>=
3
&&
x
<
6
&&
y
>=
6
&&
y
<
9
)
25
return
5
;
26
else
if
( x
>=
6
&&
x
<
9
&&
y
<
3
)
27
return
6
;
28
else
if
( x
>=
6
&&
x
<
9
&&
y
>=
3
&&
y
<
6
)
29
return
7
;
30
else
if
( x
>=
6
&&
x
<
9
&&
y
>=
6
&&
y
<
9
)
31
return
8
;
32
}
33
34
35
void
Print()
36
{
37
for
(
int
i
=
0
; i
<
9
;
++
i )
38
{
39
for
(
int
j
=
0
; j
<
9
;
++
j )
40
printf(
"
%d
"
,result[i][j] );
41
42
if
( i
<
8
) printf(
"
\n
"
);
43
}
44
}
45
46
47
bool
GetXY(
int
&
xx,
int
&
yy )
48
{
49
for
(
int
i
=
0
; i
<
9
; i
++
)
50
{
51
for
(
int
j
=
0
; j
<
9
; j
++
)
52
if
( result[i][j]
==
0
)
53
{
54
xx
=
i;
55
yy
=
j;
56
57
return
true
;
58
}
59
}
60
61
return
false
;
62
}
63
64
65
void
Try(
int
xx,
int
yy )
66
{
67
for
(
int
i
=
1
; i
<=
9
;
++
i )
68
{
69
if
(
!
x[xx][i]
&&
!
y[yy][i]
&&
!
z[ GetID(xx,yy) ][i] )
70
{
71
int
a, b;
72
73
result[xx][yy]
=
i;
74
75
x[xx][i]
=
true
;
76
y[yy][i]
=
true
;
77
z[ GetID(xx,yy) ][i]
=
true
;
78
79
if
(
!
GetXY( a, b ) )
80
{
81
Print();
82
num
=
1
;
83
return
;
84
}
85
86
Try( a, b );
87
result[xx][yy]
=
0
;
88
89
x[xx][i]
=
false
;
90
y[yy][i]
=
false
;
91
z[ GetID(xx,yy) ][i]
=
false
;
92
}
93
}
94
}
95
96
97
98
int
main()
99
{
100
int
n;
101
scanf(
"
%d
"
,
&
n);
102
char
aaa[
10
];
103
104
for
(
int
mm
=
0
; mm
<
n; mm
++
)
105
{
106
char
graph[
9
][
10
];
107
num
=
0
;
108
109
memset( x,
false
,
sizeof
(x) );
110
memset( y,
false
,
sizeof
(y) );
111
memset( z,
false
,
sizeof
(z) );
112
memset( result,
0
,
sizeof
( result ) );
113
114
for
(
int
i
=
0
; i
<
9
;
++
i )
115
scanf(
"
%s
"
, graph[i] );
116
117
for
(
int
i
=
0
; i
<
9
;
++
i )
118
{
119
for
(
int
j
=
0
; j
<
9
;
++
j )
120
if
( graph[i][j]
!=
'
?
'
)
121
{
122
int
t
=
graph[i][j]
-
'
0
'
;
123
result[i][j]
=
t;
124
125
x[i][t]
=
true
;
126
y[j][t]
=
true
;
127
z[ GetID( i, j ) ][t]
=
true
;
128
}
129
}
130
131
int
x, y;
132
133
GetXY( x, y );
134
Try( x, y );
135
136
if
( mm
<
n
-
1
)
137
{
138
printf(
"
\n---\n
"
);
139
scanf(
"
%s
"
,aaa);
140
}
141
142
if
( num
==
0
)
143
printf(
"
impossible
"
);
144
}
145
146
return
0
;
147
}
148
149
posted on 2008-08-19 08:14
Darren 阅读(315)
评论(0) 编辑 收藏 引用 所属分类:
搜索