Ac solution code


  • 3

    The rules of Sudoku game can be found here:
    Grids: 9 x 9

    1) 1-9 only occurs once in each ROW/COLUMN
    2) 1-9 only occurs once in each 3 x 3 square (9 squares totally with splitter of length 3)
    

    One pass solution: Special thanks for Lorraine921's one pass idea.

    public boolean isValidSudoku(char[][] board) {		
    	for (int i= 0; i < board.length; i++) {
    		Set<Character>row = new HashSet<Character>();// Check row
    		Set<Character>col = new HashSet<Character>();// Check column
    		Set<Character>square = new HashSet<Character>();// Check sub square
    		for (int j = 0; j < board[0].length; j++) {
    			if (board[i][j] != '.' && !row.add(board[i][j]))//row.add=false, means the element already existed in the set
    				return false;
    			if (board[j][i] != '.' && !col.add(board[j][i]))
    				return false;				
    			int rowIndex = 3 * (i/3), colIndex = 3 * (i % 3);				
    			if (board[rowIndex + j/3][colIndex + j % 3] != '.' && !square.add(board[rowIndex + j/3][colIndex + j % 3]))
    				return false; 
    		}
    	}		
    	return true;
    }
    

    Three passes solution:

    public boolean isValidSudoku(char[][] board) {
    	boolean visited[] = new boolean[9];
    	for (int i = 0; i < board.length; i++) {//Row
    		Arrays.fill(visited, false);
    		for (int j = 0; j < board[0].length; j++) {
    			if (board[i][j] != '.') {    				
    				if (visited[board[i][j] - '0' - 1])
    					return false;    				
    				visited[board[i][j] - '0' - 1] = true;
    			}
    		}    		    		
    	}	
    	for (int i = 0; i < board[0].length; i++) {//Column
    		Arrays.fill(visited, false);
    		for (int j = 0; j < board.length; j++) {
    			if (board[j][i] != '.') {   				
    				if (visited[board[j][i] - '0' - 1])
    					return false;    				
    				visited[board[j][i] - '0' - 1] = true;
    			}
    		}    		    		
    	}	
    	for (int i = 0; i < board.length; i+=3) {//Sub square
    		for (int j = 0; j < board[0].length; j+=3) {
        		Arrays.fill(visited, false);
    			for (int k = 0; k < 9; k++) {
        			if (board[i+k/3][j+k%3] != '.') {    				
        				if (visited[board[i+k/3][j+k%3] - '0' - 1])
        					return false;    				
        				visited[board[i+k/3][j+k%3] - '0' - 1] = true;
        			}
    			} 
    		}    		    		
    	}
    	return true;
    }
    

Log in to reply
 

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