qgbian
BAN USERSince we know the there are only 9 numbers, we do not need to use hash table. An array is enough.
public boolean isValidSudoku(char[][] board) {
if(board == null)
return false;
for(int i = 0; i < 9; i++){
boolean[] flag = new boolean[9];
for(int j = 0; j < 9; j++){
int val = board[i][j] - 49;
if(board[i][j] == '.'){
continue;
} else if (flag[val] == true){
return false;
}else{
flag[val] = true;
}
}
}
for(int i = 0; i < 9; i++){
boolean[] flag = new boolean[9];
for(int j = 0; j < 9; j++){
int val = board[j][i] - 49;
if(board[j][i] == '.'){
continue;
} else if (flag[val] == true){
return false;
}else{
flag[val] = true;
}
}
}
for(int i = 0; i <= 6; i += 3){
for(int j = 0; j <=6; j += 3){
boolean[] flag = new boolean[9];
for(int m = i; m < i+3; m++){
for(int n = j; n < j+3; n++){
int val = board[m][n] - 49;
if(board[m][n] == '.'){
continue;
}else if(flag[val] == true){
return false;
}else{
flag[val] = true;
}
}
}
}
}
return true;
}
"A second pass would be needed to detect false positives, but by that point the dataset should be very pruned."
- qgbian February 13, 2014I don't think a second pass can detect false positives. If an element is detected to be a duplicate, it can be a duplicate or not a duplicate(false positive). So we can not delete it when we find a element is detected, that is dataset can not be pruned. I didn't find a paper on line that proposes a method to make sure bloom filter can achieve 100% accuracy. If some one knows it, I'm very glad to hear that.