Sudoku Validation in Java


  • 0
    H

    Since the problem only requires validation rather than solution, we can easily check the redundancy of the Soduku matrix. Based on Soduku's rule, each number from '0' to '9' should appear only once. Thus we can basically traverse every row, column and grid.

    Due to array representation of matrix, it is simple to check validity of row and column. It is a little tricky to check validity of grid. To solve this branch, we only need to figure out accurate start position of row and column for a grid. And then, the problem is solved.

    Following is the source code based on Java.

    class Solution {
        public boolean isValidSudoku(char[][] board) { 
            int n = board.length;
            for( int i = 0 ; i < n; i++ ){
                if( !checkRow(board, i) )
                    return false;
                if( !checkCol(board, i) )
                    return false;
                if( !checkGrid(board, i) )
                    return false;
            }
            return true;
        }
        
        private boolean checkRow(char[][] board, int row){
            int n = board.length;
            int value = 0;
            HashSet<Integer> distinct = new HashSet<Integer>();
            for( int i = 0 ; i < n; i++ ){
                char item = board[row][i];
                if( item == '.' )
                    continue;
                if( distinct.contains((int)item) )
                    return false;
                distinct.add((int)item);
            }
            return true; 
        }
        
        private boolean checkCol(char[][] board, int col){
            int n = board.length;
            int value = 0;
            HashSet<Integer> distinct = new HashSet<Integer>();
            for( int i = 0 ; i < n; i++ ){
                char item = board[i][col];
                if( item == '.' )
                    continue;
                if( distinct.contains((int)item) )
                    return false;
                distinct.add((int)item);
            }
            return true; 
        }
         
        private boolean checkGrid(char[][] board, int g){
            int n = board.length;
            int gridSize = (int)Math.sqrt(n);
            int value = 0;
            int rowBase = (int)Math.floor( g / gridSize );
            int colBase = g % gridSize;
            HashSet<Integer> distinct = new HashSet<Integer>();
            for( int i = 0 ; i < gridSize; i++ ){
                for( int j = 0 ; j < gridSize; j++ ){ 
                    char item = board[rowBase*gridSize+i][colBase*gridSize+j];
                    if( item == '.' )
                        continue;
                    if( distinct.contains((int)item) )
                        return false;
                    distinct.add((int)item);
                }
            }
            return true; 
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.