The Sudoku board could be partially filled, where empty cells are filled with the character
'.'
.
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.
Naive Way: The statement "A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated. " makes this question much easier as we just need to check validation for each empty cell.
public class Solution {
public boolean isValidSudoku(char[][] board) {
for(int i = 0;i < 9;i++)
for(int j = 0;j < 9;j++)
if(board[i][j] != '.')
if(!isValidCell(board, i, j))
return false;
return true;
}
private boolean isValidCell(char[][] board, int x, int y){
// its block
int center_x = x/3 * 3 + 1;
int center_y = y/3 * 3 + 1;
for(int i = -1;i <= 1;i++)
for(int j = -1;j <= 1;j++)
if(board[center_x+i][center_y+j]==board[x][y] && center_x+i!=x && center_y+j!=y)
return false;
// its row
for(int i = 0;i < 9 && i!=x;i++)
if(board[i][y]==board[x][y])
return false;
// its column
for(int j = 0;j < 9 && j!=y;j++)
if(board[x][j]==board[x][y])
return false;
return true;
}
}
Using a HashSet may help reduce the run time, but it's at most 9*9=81 cells. Can be regarded as O(1) I think. And accessing array is of high efficiency in Java.
No comments:
Post a Comment