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 '.'.
- A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Solution:
bool isValidSudoku(char** board, int boardRowSize, int boardColSize) {
int sign[27] = {0};
int i, j;
for (i = 0; i < boardRowSize; i++) {
for (j = 0; j < boardRowSize; j++) {
if (board[i][j] == '.') continue;
int flag = 1 << board[i][j];
if (sign[i] & flag || sign[9 + j] & flag || sign[18 + i / 3 * 3 + j / 3] & flag) return false;
sign[i] |= flag;
sign[9 + j] |= flag;
sign[18 + i / 3 * 3 + j / 3] |= flag;
}
}
return true;
}
Summary:
- There are 27 blocks which need to test.
- The key point is the relation between flag's index and i & j.
- 3ms, 49.45%
LeetCode: 36. Valid Sudoku
近期评论