HJ44 Sudoku

题目描述

给出一个9x9的数独矩阵，数字0代表要填写1~9中的某个数字，使得每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。

示例

输入：
0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1

输出：
5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1

思路

使用递归搜索，在0的位置上尝试填入1~9中的某个数字，非0位置不处理。然后对下一个位置进行同样的操作。

如果走到了最后，证明填写成功了。

如果某个位置填入1~9中任意数字都不行，则证明前面填错了，则将本位置重设为0后回溯。

Code

#include <cstdio>
#include <iostream>
using namespace std;

int a[15][15];
bool flag;

bool check(int num, int pos) {
    int x = pos / 9;
    int y = pos % 9;
    for(int i = 0; i < 9; ++i) {
        // if(i == x) continue;
        if(a[i][y] == num) return 0;
    }
    for(int i = 0; i < 9; ++i) {
        // if(i == y) continue;
        if(a[x][i] == num) return 0;
    }
    int start_x = x / 3 * 3;
    int start_y = y / 3 * 3;
    for(int i = start_x; i < start_x + 3; ++i) {
        for(int j = start_y; j < start_y + 3; ++j) {
            // if(i == x && j == y) continue;
            if(a[i][j] == num) return 0;
        }
    }
    return 1;
}

void dfs(int pos) {
    if(pos == 81) {
        flag = true;
        return;
    }
    int x = pos / 9;
    int y = pos % 9;
    if(a[x][y] != 0) {
        dfs(pos + 1);
    } else {
        for(int i = 1; i <= 9; ++i) {
            if(check(i, pos)) {
                a[x][y] = i;
                dfs(pos + 1);
                if(flag) return;
            }
        }
        if(!flag) {
            //9个数字都尝试了还是失败，说明前面就错了
            a[x][y] = 0;
            return;
        }
    }
}

int main() {
    flag = false;
    for(int i = 0; i < 9; ++i) {
        for(int j = 0; j < 9; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    dfs(0);
    for(int i = 0; i < 9; ++i) {
        for(int j = 0; j < 9; ++j) {
            printf("%d%c", a[i][j], j == 8 ? '\n' : ' ');
        }
    }
    return 0;
}