Skip to content

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