Labels

Wednesday, March 4, 2015

Valid Sudoku

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.
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