关键字:搜索、数独 - 难度:难 - 题目大意:对于一个给出的数独问题,保证其有且仅有一组可行解,请求出这组解。

题目描述

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

alter-text

A sudoku puzzle...

alter-text

...and its solution numbers marked in red.

解法

这道题目虽然在LeetCode中的难度排在Hard一级,但是也主要是考察代码的编写能力,实际上对于搜索的剪枝能力考察的并不算多,只需要使用基本的可行性剪枝就可以顺利的通过此题。

数独问题是一个非常有趣的问题,在现实生活中,笔者经常会在手机上玩一些简单的数独。通常来说,我们会选择“可能性”最少的格子开始枚举——这样的格子不会在少数,经常可以通过串联的几个逻辑判断确定某个格子的值,但是对于计算机来说,想让程序自动发现这样的逻辑判断还是相对麻烦。

于是在这里,我们不妨直接采用最为简单直接的枚举方式:从左上角开始,依次枚举每个空白格子的取值,直到枚举到右下角,这时我们检查每一行、每一列、每一个3*3方块中是否存在相同的数字,如果不存在,就说明这样的方案是合法的。

但是显然的是,这样的方式是会超时的!

所以我们需要在这个搜索的过程中进行一定程度的剪枝!一个非常好的方法,就是在枚举每一个空白格子的时候,就直接检查每一行、每一列、每一个3*3方块中是否存在相同的数字,如果存在过,就不需要在这组方案的基础上继续枚举了。

那么怎么样判断一个数字是否在每一行、每一列、每一个3*3方块中是否出现过某个数字呢?

很简单,对于每一行,我们用h[i][j]表示第i行中是否已经出现过j这个数字,用v[i][j]表示第i列中是否已经出现过j这个数字,用b[i][j]表示第i个方块(按照行为第一关键字,列为第二关键字的顺序)中是否已经出现过j这个数字,然后在搜索的过程中,每当枚举一个值之后(不妨设枚举第i行第j列为k),就用

h[i][k] = true; v[j][k] = true; b[i / 3 * 3 + j / 3][k] = true;

的操作来维护这三个数组,然后在枚举时通过

if (!h[i][k] && !v[j][k] && !b[i / 3 * 3 + j / 3][k])

来确保不会枚举出重复的数字,这样就可以非常简洁明了的避免在枚举的过程中出现重复的数字,一方面剪去了不必要的搜索,另一方面则避免了最后的同一判断。

在加上了这样的剪枝方案之后,就可以顺利的通过这道题在LeetCode上的测试数据。

值得注意的是,这仅仅只是因为LeetCode的数据偏简单而已,数独问题还存在着更多优美高效的剪枝方法,不过这就有待读者们自己探寻了!

参考代码

class Solution {
public:
    int n;
    int h[9][10], v[9][10], b[9][10];
    void solveSudoku(vector<vector<char>>& board) {
        n = board.size();
        // 初始化h,v,b三个数字,将已经出现的数字进行处理
        memset(h, 0, sizeof(h));
        memset(v, 0, sizeof(v));
        memset(b, 0, sizeof(b));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (board[i][j] != '.') {
                    h[i][board[i][j] - '0'] = true;
                    v[j][board[i][j] - '0'] = true;
                    b[i / 3 * 3 + j / 3][board[i][j] - '0'] = true;
                }
        // 以回溯的方式枚举所有可能的方案,从左上角开始枚举
        solve(0, 0, board);
    }
    bool solve(int i, int j, vector<vector<char>>& a) {
        // 当已经枚举完整个棋盘时,说明已经构成了一组解
        if (i == n) {
            return true;
        }
        // 枚举到一行的最后一列时,跳转到下一行的第一列进行枚举
        if (j == n) {
            return solve(i + 1, 0, a);
        }
        // 如果是已经存在的数字,则进行跳过
        if (a[i][j] != '.') return solve(i, j + 1, a);
        // 否则枚举这个格子可能出现的数字
        for (int k = 1; k <= 9; k++) {
            // 检查以避免出现相同的数字
            if (!h[i][k] && !v[j][k] && !b[i / 3 * 3 + j / 3][k]) {
                // 将(i, j)处设置为k,并更新h,v,b数组
                a[i][j] = '0' + k;
                h[i][k] = true; v[j][k] = true; b[i / 3 * 3 + j / 3][k] = true;
                // 枚举下一个格子
                if (solve(i, j + 1, a)) return true;
                // 恢复造成的修改,以进行下一种可能的枚举或者进行回溯
                h[i][k] = false; v[j][k] = false; b[i / 3 * 3 + j / 3][k] = false;
                a[i][j] = '.';
            }
        }
        // 如果所有方案都不可行说明之前的方案存在问题,进行回溯
        return false;
    }
};

登录发表评论 注册

反馈意见