题目
请判定一个数独是否有效。
该数独可能只填充了部分数字,其中缺少的数字用 . 表示。
http://www.lintcode.com/zh-cn/problem/valid-sudoku/
分析
判断数独填充是否有效,主要看3方面:
- 每一行内,填充的数字不重复
- 每一列中,填充的数字不重复
- 每一个小的九宫格中,填充的数字不重复
暴力枚举即可,逐个考察九宫格中的每一个元素,如果该元素为'.',则合法,继续下一个。
如果格子里是数字,就要进行三方面的判断,分别用三个独立的函数判断即可。
代码
public class Solution {
boolean isValidRow(char[][] board, int row, int col) {
for(int i=0; i < board[row].length; i++) {
if (i == col || board[row][i] == '.') {
continue;
}
if ( board[row][i] == board[row][col] )
return false;
}
return true;
}
boolean isValidCol(char[][] board, int row, int col) {
for(int i=0; i < board.length; i++) {
if (i == row || board[i][col] == '.') {
continue;
}
if ( board[i][col] == board[row][col] )
return false;
}
return true;
}
boolean isValidSquare(char[][] board, int row, int col) {
int srow = row / 3;
int scol = col / 3;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
int r = srow * 3 + i;
int c = scol * 3 + j;
if( board[r][c] == '.' || (row == r && col == c) ) {
continue;
}
if (board[r][c] == board[row][col]) return false;
}
}
return true;
}
boolean isValidCharacter(char[][] board, int row, int col) {
if (board[row][col] == '.') return true;
return isValidRow(board, row, col)
&& isValidCol(board, row, col)
&& isValidSquare(board, row, col);
}
/**
* @param board: the board
* @return: whether the Sudoku is valid
*/
public boolean isValidSudoku(char[][] board) {
// write your code here
for(int row=0; row < board.length; row++){
for(int col=0; col < board[row].length; col++) {
if(isValidCharacter(board, row, col)) {
continue;
}else{
return false;
}
}
}
return true;
}
}