leetcode笔记：Valid Sudoku

一.题目描述

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules：
http://sudoku.com.au/TheRules.aspx .
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

The following figure: A partially filled sudoku which is valid.

二.题目分析

关于Sudoku矩阵的性质，可以简单概括为：对于矩阵中每一行、每一列以及每个3×3的九宫格区域是否存在唯一的0~9排列组合，如果存在相同的元素，则该Sudoku矩阵不合法。

这道题比较简单，就是遍历Sudoku矩阵的所有元素，检查各元素是否满足Sudoku的性质。对于判断一个元素是否在某一行，某一列或者某个小区域内，我定义了一个用于存放0~9数字出现次数的map，使用‘1‘，‘2‘，...，‘9‘作为关键字只要某个关键字的储存对象大于1，表示在该行、列或3×3的九宫格区域中有重复的某个关键字，通过这种方式进行遍历即可判断矩阵是否合法。

三.示例代码

#include <iostream>
#include <vector>
#include <map>
using namespace std;

class Solution
{
public:
    bool isValidSudoku(vector<vector<char> >& board)
    {
        map<char, int> sudokuMap;
        for (int i = 0; i < 9; i++)
        {
            sudokuMap.clear();
            for (int j = 0; j < 9; j++)
            {
                sudokuMap[board[i][j]]++;
                if ((board[i][j] != ‘.‘) && (sudokuMap[board[i][j]] > 1))
                    return false;
            }
        }

        for (int i = 0; i < 9; i++)
        {
            sudokuMap.clear();
            for (int j = 0; j < 9; j++)
            {
                sudokuMap[board[j][i]]++;
                if ((board[j][i] != ‘.‘) && (sudokuMap[board[j][i]] > 1))
                    return false;
            }
        }

        for (int i = 0; i < 9; i += 3)
        {
            for (int j = 0; j < 9; j += 3)
            {
                sudokuMap.clear();
                for (int k = i; k < i + 3; k++)
                {
                    for (int l = j; l < j + 3; l++)
                    {
                        sudokuMap[board[k][l]]++;
                        if ((board[k][l] != ‘.‘) && (sudokuMap[board[k][l]] > 1))
                            return false;
                    }
                }
            }
        }
        return true;
    }
};

运行结果如下：

1.一个正确的数独矩阵：

2.一个错误的数独矩阵：

四.小结

这道题不要求实现什么算法，只需设计一下矩阵运算，使用map用于存放每行、每列或每个九宫格中1~9每个数出现的次数，只要发现有大于一的，即可立即否定这个Sudoku，只有遍历整个Sudoku矩阵且符合要求，才判定为valid sudoku。

相关题目：Sudoku solver