# 11106: 【原1106】sudoku

### 题目描述

author: Guangda Huzhang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1106

# sudoku

## 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;

private:
int n, m;
int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];
int row[MAXNODE], col[MAXNODE];
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));
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;
}

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;
}
else{
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;
}

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(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;
}
``````