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 partially filled sudoku which is valid.
A: 就是道简单的实现题
public class Solution { public boolean isValidSudoku(char[][] board) { // if(board==null || board.length ==0 || board.length !=9 || board[0].length!=9) // return false; for(int i =0;i<board.length;i++){ for(int j =0;j< board[0].length;j++) if( !isValid(i,j,board)) return false; } return true; } private boolean isValid(int row, int col , char[][] board){ char ch = board[row][col]; if(ch == '.') return true; for(int i = row+1; i<board.length;i++) if(board[i][col] == ch) return false; for(int j = col+1;j<board[0].length;j++) if(board[row][j] == ch) return false; board[row][col] = '.';// temporaryly change it for(int i = 0;i<3;i++) for(int j = 0;j<3;j++) if(board[row/3 * 3 +i][col/3*3+j] == ch) return false; board[row][col]=ch; return true; } }这里,在小方框里,忘记check是否是原来的位置。
public class ValidSudoku { public boolean isValidSudoku(char[][] board) { // we only check valid, but not solvable if(board==null || board.length ==0 || board.length !=9 || board[0].length!=9){ return false; } // check valid row & check valid chars boolean[] validArray; for (int i = 0; i < 9; i++) { // for each row validArray = new boolean[10]; for (int j = 0; j < 9; j++) { // check valid of chars if (! (board[i][j] >= '0' && board[i][j] <= '9') && board[i][j] != '.') { return false; } if(board[i][j]=='.')continue; int value = Integer.valueOf("" + board[i][j]); if (validArray[value]) { return false; } else { validArray[value] = true; } } } // check valid col for (int j = 0; j < 9; j++) { validArray = new boolean[10]; for (int i = 0; i < 9; i++) { // for each row if(board[i][j]=='.')continue; int value = Integer.valueOf("" + board[i][j]); if (validArray[value]) { return false; } else { validArray[value] = true; } } } // check valid square for (int outerI = 0; outerI < 3; outerI++) { for (int outerJ = 0; outerJ < 3; outerJ++) { validArray = new boolean[10]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if(board[3*outerI+i][3*outerJ+j]=='.')continue; int value = Integer.valueOf("" + board[3*outerI+i][3*outerJ+j]); if (validArray[value]) { return false; } else { validArray[value] = true; } } } } } return true; } }
Mistakes:
1: 对每个board上的数字, 当转换到int类型的时候,忘了检查,是否为'.' , 造成了 Exception
2: 在检查小方格的时候, 忘了算上outerI, outerJ的基数, 哎, SB啊
int value = Integer.valueOf("" + board[3*outerI+i][3*outerJ+j]);
Learned:
No comments:
Post a Comment