题目

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

A partially filled sudoku which is valid.

Note:

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

分析

这是一道关于数独游戏的题目，首先要了解数独游戏的规则：



所以，对于该题目，有些空格中是’.’ 字符，我们只需要考虑当前状态下是否满足数独即可。

也就是说，我们要按行、按列，按每个3*3宫格，检验三次。

AC代码

class Solution {

public:

    bool isValidSudoku(vector<vector<char>>& board) {

        if (board.empty())

            return false;

        //数独游戏符合9宫格，也就是为一个9*9的矩阵

        int size = board.size();

        //根据数独游戏的规则，需要进行三次检验（按行、按列、按照3*3块）

        //利用哈希的思想，记录每个关键字的出现次数，若是次数>1，则返回false

        vector<int> count;

        for (int i = 0; i < size; ++i)

        {

            //每行开始前，将记录次数的vector清零,元素1~9分别对应下标0~8,对应vector中值为该元素的出现次数

            count.assign(9, 0);

            for (int j = 0; j < size; j++)

            {

                if (board[i][j] != '.')

                {

                    int pos = board[i][j] - '1';

                    if (count[pos] > 0)

                        return false;

                    else

                        ++count[pos];

                }

                else

                    continue;

            }//for

        }//for

        //同理，按列检验

        for (int j = 0; j < size; j++)

        {

            count.assign(9, 0);

            for (int i = 0; i < size; i++)

            {

                if (board[i][j] != '.')

                {

                    int pos = board[i][j] - '1';

                    if (count[pos] > 0)

                        return false;

                    else

                        ++count[pos];;

                }

                else

                    continue;

            }//for

        }//for

        //按3*3小块检验

        for (int i = 0; i < size; i += 3)

        {

            for (int j = 0; j < size; j += 3)

            {

                count.assign(9, 0);

                //每个块又是一个3*3的矩阵

                for (int row = i; row < i + 3;row++)

                for (int col = j; col < j + 3; col++)

                {

                    if (board[row][col] != '.')

                    {

                        int pos = board[row][col] - '1';

                        if (count[pos] > 0)

                            return false;

                        else

                            ++count[pos];;

                    }

                    else

                        continue;

                }

            }//for

        }//for

        return true;

    }

};

GitHub测试程序源码