isValidSudoku.cpp

#include <vector>

using namespace std;

class Solution
{
public:
    //遍历行
    bool row(vector<vector<char>> &board)
    {
        //用来记录元素的数组
        vector<char> temp;
        //一层循环---代表第几行
        for(int i = 0;i < 9;i++)
        {
            //二层循环，代表一行内的那个数组的第几个元素
            for(int j = 0;j < 9;j++)
            {
                if(board[i][j] != '.')
                {
                    //循环遍历记录元素的数组
                    for(int k = 0;k < temp.size();k++)
                    {
                        //发现重复，不是有效数独
                        if (board[i][j] == temp[k])
                        {
                            return false;
                        }
                    }
                    // 没发现，放入记录数组
                    temp.push_back(board[i][j]);
                }
            }
            //退出循环后，清空数组，用于第二行记录
            temp.clear();
        }

        //经过遍历，任何一行都没有发现一样的元素，因此它过关
        return true;
    }
    //遍历列
    bool column(vector<vector<char>> &board)
    {
        //实现思路：依旧是双重循环 + 临时数组
        vector<char> temp;
        //外层，代表第几列
        for(int i = 0;i < 9;i++)
        {
            //内层：代表这一列第几个元素
            for(int j = 0;j < 9;j++)
            {
                //检查是否为.
                if(board[j][i] != '.')
                {
                    //看是否重复
                    for(int k = 0;k < temp.size();k++)
                    {
                        if (board[j][i] == temp[k])
                        {
                            return false;
                        }
                    }
                    temp.push_back(board[j][i]);
                }
            }
            //清空
            temp.clear();
        }

        //没找到，过关
        return true;
    }
    //每一个九宫格
    bool grid(vector<vector<char>> &board)
    {
        // 第几行/列
        int aGridRowMax = 0;
        int aGridColumnMax = 0;
        //记录数组
        vector<char> temp;
        //外层循环：第几个九宫格
        for(int i = 1;i <= 9;i++)
        {
            //外层行内层列
            //根据特定条件，我们要对Column和Row进行 + 3操作
            aGridRowMax = ((i - 1) % 3 + 1) * 3;
            aGridColumnMax = ((i - 1) / 3 + 1) * 3;
            for (int j = aGridColumnMax - 3; j < aGridColumnMax; j++)
            {
                for (int k = aGridRowMax - 3; k < aGridRowMax; k++)
                {
                    if(board[j][k] != '.')
                    {
                        for(int l = 0;l < temp.size();l++)
                        {
                            if(board[j][k] == temp[l])
                            {
                                return false;
                            }
                        }
                        temp.push_back(board[j][k]);
                    }
                }
            }
            //遍历完每一个九宫格，清空该数组
            temp.clear();
        }

        //没找到，满足
        return true;
    }
    bool isValidSudoku(vector<vector<char>> &board)
    {
        // 先行，后列，再九宫格，遍历，每个循环用数组进行记录是否有相同的
        if (row(board) && column(board) && grid(board))
        {
            //全部成立，是有效的九宫格
            return true;
        }
        //可能某一个不成立，不是有效的数独
        return false;
    }
};