valid sudoku(数独)

时间:2023-12-12 09:24:44

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 '.'.

valid sudoku(数独)

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.

数独规则:每行只能出现一次0-9,即不能重复;每列只能出现一次0-9;每个九宫格只能出现一次0-9。这里没有什么太好的方法,就是用数据结构将对应数据存起来判断。因为判断不能重复,所以可以使用set。每行一个set,每列一个set,每个九宫格一个set。。总共9个行set,9个列set,9个九宫格set。这样可以在遍历行左边i=0,..9时,每次初始化这三个set。这里行和列set都好处理,那些元素放行set,哪些放列set都很好确定。但是九宫格set的元素有点麻烦。这需要寻找规律。
注意,这里外层遍历i,每个i对应一个行set、列set、九宫格set。
只要找到每个行、列、九宫格和i,j的练习/.
观察行号规律:与i和j联系起来。i对应每个九宫格,j对应每个九宫格中的每个格子。
第0个九宫格:000111222; 第1个九宫格:000111222; 第2个九宫格:000111222;
第3个九宫格:333444555; 第4个九宫格:333444555; 第5个九宫格:333444555;
第6个九宫格:666777888; 第7个九宫格:666777888; 第8个九宫格:666777888;
可见对于每三个九宫格行号增3;对于单个九宫格,每三个格点行号增1。
因此第i个九宫格的第j个格点的行号可表示为i/3*3+j/3
观察列号规律:
第0个九宫格:012012012; 第1个九宫格:345345345; 第2个九宫格:678678678;
第3个九宫格:012012012; 第4个九宫格:345345345; 第5个九宫格:678678678;
第6个九宫格:012012012; 第7个九宫格:345345345; 第8个九宫格:678678678;
可见对于每个九宫格列号增3,循环周期为3;对于单个九宫格,每个格点行号增1,周期也为3。
周期的数学表示就是取模运算mod。
因此第i个九宫格的第j个格点的列号可表示为i%3*3+j%3

因此第i个九宫格的第j个格点的列号可表示为i%3*3+j%3

class Solution {
public boolean isValidSudoku(char[][] board) {
for(int i=0;i<9;i++){//每个i对应一个行、列、九宫格set
HashSet<Character> rows=new HashSet<>();
HashSet<Character> cols=new HashSet<>();
HashSet<Character> cube=new HashSet<>();
for(int j=0;j<9;j++){
if(board[i][j]!='.'&&!rows.add(board[i][j]))
return false;
if(board[j][i]!='.'&&!cols.add(board[j][i]))
return false; int RowIndex=i/3*3+j/3;
int ColIndex=i%3*3+j%3;
if(board[RowIndex][ColIndex]!='.'&&!cube.add(board[RowIndex][ColIndex]))
return false;
}
} return true;
}
}