一、问题描述
Example 1:
Example 2:
Note :
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
- The given board contain only digits 1-9 and the character
'.'. - The given board size is always
9x9.
二、解题思路
咋一看以为是解数独，会很复杂。读完题目后，发现只要求判断当前的棋盘上的数字是不是有效的，不需要考虑最终这个数独是不是可以解。所以相当于只需要判断当前这个已经存在的棋盘是否满足数独规则的要求。
数独的规则要求，每行，每列，以及每个3x3的子棋盘上，是否包括1-9这9个数字且不重复。现在考虑，肯定是需要把整个棋盘扫描一遍的，那么我们可以设置三个状态数组，来分别记录下以及扫描过的 行/列/子棋盘 中已经出现过的数，如果扫描到某 行/列/子棋盘 中有重复的元素前面已经出现过，直接返回false；若直到扫描结束，也为发现重复元素，说明棋盘有效，返回true。但是由于要记录每 行/列/子棋盘 的状态，需要声明三个较大的数组，所以对空间的消耗较高，应该还有更优化的解法。
评论区解题的大致思路都差不多，区别主要再求如何存储状态数组。有一种很优化的方法是利用位操作实现的，这种方法只使用一个short就存储了一行的状态，节省了很多空间，效率也得到了提升。
参考：
C++ very simple and easy understand. using bit operation
My C++ code (O(n2) time and space)
三、代码
解法1
利用位操作
解法3
原文:大专栏 LeetCode--36. Valid Sudoku