11106: 【原1106】sudoku
题目
题目描述
author: Guangda Huzhang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1106
sudoku
Description
数独（すうどく，Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。 每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。 ――摘自百度百科
数独是老少咸宜的游戏。现在我们想知道，我们给定的数独是否是合格的数独（也就是说有解且唯一）。
Input Format
输入的第一行包含一个不超过10的整数T，表示数据的组数。 接下来有T个部分，每两个部分之间用一个换行符隔开，每个部分描述一个数独局面。 每个局面由9*9的方阵描述，若方阵中的数字为1~9，则说明该位置是已经被填好；若是0,则表示该位置为空。
Output Format
输出包含T行，每行包括一个“Yes”或“No”表示该数独是否合格。
Sample Input
2
0 7 2 1 0 0 4 0 0
0 1 0 8 0 4 0 2 0
0 4 0 3 0 0 5 9 0
1 0 0 9 0 0 0 4 7
3 0 0 5 0 6 0 0 9
4 2 0 0 3 0 0 0 8
0 5 1 0 0 7 0 3 0
0 9 0 2 0 3 0 6 0
0 0 4 0 0 9 8 7 0
0 0 0 0 7 0 0 0 6
2 0 4 0 5 1 0 7 0
8 0 0 0 0 2 0 1 9
5 0 0 6 0 0 2 0 0
0 0 1 0 0 4 9 5 0
0 0 8 0 0 0 0 0 1
3 7 0 1 0 0 0 0 5
0 1 0 3 0 0 7 0 2
9 0 0 0 2 0 1 0 0
Sample Output
Yes
No
FineArtz's solution
#include <iostream>
#include <cstring>
using namespace std;
const int MAXNODE = 2000005, MAXN = 1050;
const int SLOT = 0, ROW = 1, COL = 2, SUB = 3;
class DancingLink{
private:
int n, m;
int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];
int row[MAXNODE], col[MAXNODE];
int head[MAXN], sum[MAXN];
int ansd, size;
public:
int solution;
void init(int n = 0, int m = 0){
this->n = n;
this->m = m;
size = m + 1;
solution = 0;
memset(sum, 0, sizeof(sum));
memset(head, -1, sizeof(head));
for (int i = 0; i <= m; ++i){
L[i] = i - 1;
R[i] = i + 1;
U[i] = i;
D[i] = i;
}
L[0] = m;
R[m] = 0;
}
void addNode(int r, int c){
row[size] = r;
col[size] = c;
U[size] = U[c];
D[size] = c;
U[D[size]] = size;
D[U[size]] = size;
if (head[r] == -1){ //empty row
L[size] = size;
R[size] = size;
head[r] = size;
}
else{
L[size] = L[head[r]];
R[size] = head[r];
L[R[size]] = size;
R[L[size]] = size;
}
++sum[col[size++]];
}
void delNode(int x){
R[L[x]] = R[x];
L[R[x]] = L[x];
for (int i = D[x]; i != x; i = D[i]){
for (int j = R[i]; j != i; j = R[j]){
U[D[j]] = U[j];
D[U[j]] = D[j];
--sum[col[j]];
}
}
}
void resNode(int x){
for (int i = U[x]; i != x; i = U[i]){
for (int j = L[i]; j != i; j = L[j]){
U[D[j]] = j;
D[U[j]] = j;
++sum[col[j]];
}
}
R[L[x]] = x;
L[R[x]] = x;
}
void dfs(int depth){
if (R[0] == 0){
++solution;
return;
}
int x = R[0];
for (int i = R[0]; i != 0; i = R[i]){
if (sum[x] > sum[i])
x = i;
}
delNode(x);
for (int i = D[x]; i != x; i = D[i]){
for (int j = R[i]; j != i; j = R[j])
delNode(col[j]);
dfs(depth + 1);
if (solution >= 2)
return;
for (int j = L[i]; j != i; j = L[j])
resNode(col[j]);
}
resNode(x);
}
};
inline int encode(int x, int y, int z){
return 81 * x + 9 * y + z + 1;
}
inline void decode(int code, int &x, int &y, int &z){
--code;
z = code % 9;
code /= 9;
y = code % 9;
code /= 9;
x = code % 9;
}
DancingLink dlx;
void solve(){
int a[9][9];
dlx.init(9 * 9 * 9, 9 * 9 * 4);
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j)
cin >> a[i][j];
for (int i = 0; i < 9; ++i){
for (int j = 0; j < 9; ++j){
for (int k = 0; k < 9; ++k){
if (a[i][j] == 0 || a[i][j] == k + 1){
int x = encode(i, j, k);
dlx.addNode(x, encode(0, i, j));
dlx.addNode(x, encode(1, i, k));
dlx.addNode(x, encode(2, j, k));
dlx.addNode(x, encode(3, i / 3 * 3 + j / 3, k));
}
}
}
}
dlx.dfs(0);
if (dlx.solution == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
int main(){
int t;
cin >> t;
while (t--){
solve();
}
return 0;
}
yyong119's solution
#include <iostream>
#include <cstring>
using namespace std;
bool block[10][3][3], row[10][9], col[10][9];
bool isOk(int n, int i, int j) {
return (block[n][i / 3][j / 3] && row[n][i] && col[n][j]);
}
int ansNum(int arr[][9], int i, int j) {
int count = 0;
if (i == 9) return 1;//终止条件。
if (arr[i][j] == 0) {//为0才填入。
for (int n = 1;n <= 9;++n) {
if (isOk(n, i, j)) {
block[n][i / 3][j / 3] = row[n][i] = col[n][j] = false;
switch (ansNum(arr, i + (j + 1) / 9, (j + 1) % 9)) {
case 1:
if (++count > 1) return 2;
break;
case 2:
return 2;
}
block[n][i / 3][j / 3] = row[n][i] = col[n][j] = true;//回溯。
}
}
return count;
}
else return ansNum(arr, i + (j + 1) / 9, (j + 1) % 9);
}
bool initBool(int arr[][9]) {
int count = 0;
for (int n = 1;n <= 9;++n) {
int i, j;
for (i = 0;i < 3;++i)
for (j = 0;j < 3;++j)
block[n][i][j] = true;
for (i = 0;i < 9;++i) row[n][i] = col[n][i] = true;
for (i = 0;i<9;++i)
for (j = 0;j<9;++j)
if (arr[i][j] == n) {
++count;
if (!block[n][i / 3][j / 3] || !row[n][i] || !col[n][j]) return false;//检查初始数据是否违规。
block[n][i / 3][j / 3] = row[n][i] = col[n][j] = false;
}
}
return (count >= 17);//至少17个已知数据。
}
int main() {
ios::sync_with_stdio(false);
int T; cin >> T;
int sudoku[9][9];
memset(sudoku, sizeof(sudoku), 0);
for (int i = 0; i < T; ++i) {
for (int j = 0; j < 9; ++j)
for (int k = 0; k < 9; ++k) cin >> sudoku[j][k];
if (!initBool(sudoku)) cout << "No" << endl;
else cout << (ansNum(sudoku, 0, 0) == 1 ? "Yes" : "No") << endl;
}
return 0;
}