Valid Sudoku

Share

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
  1. A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  2. Only the filled cells need to be validated according to the mentioned rules.

Example 1
Input: board = [["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Explanation: Sudoku board will look like below one, and each row, column and 3 X 3 matrix has 1-9 unique values.
123456789
53     7        
6     195       
  98          6  
8       6      3
4     8  3     1
7       2       6
  6          28  
       419     5
         8     79
Example 2
Input: board = [["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Sudoku board will look like below one, circled 8's in the first 3 X 3 matrix as well as in the 1st column are repeated, so the answer is false in this case.
123456789
83     7         
6     195       
  98          6  
8       6      3
4     8  3     1
7       2       6
  6          28  
       419     5
         8     79

Contents

Solution 1 - Check duplicates using a HashSet

In this approach, we are going to store numbers from the board into a HashSet and check if the current numebr appeared before either in the same row or same column or 3 X 3 matrix that the current number is in.

Inorder to check the duplicates for 3 conditions, we could one HashSet for checking rows, another one for checking columns and another one for checking 3 X 3 matrix values. But, instead of creating three different HashSets, we are going to create just one in below implementation and make the value such way that it appends or prepends row , column as well as 3 X 3 grid that the current element is in. If the any element with same key is repeated then that is not a valid sudoku board.

Java
import java.util.HashSet;

public class ValidSudoku {

    static boolean isValidSudoku(char[][] board) {
        HashSet<String> set = new HashSet<>(9 * 9);
        for(int i=0; i< board.length; i++) {
            for(int j=0; j<board[i].length; j++) {

                if(board[i][j] == '.') {
                    continue;
                }

                // check if the number seen in the same row
                if(!set.add("ROW : "+i+ " NUM :"+board[i][j])) {
                    return false;
                }

                // check if the number seen in the same row
                if(!set.add("COLUMN : "+j+ " NUM :"+board[i][j])) {
                    return false;
                }

                // check if the number seen in the 3 X 3 matrix that the current cell is in
                // use i/3 and j/3 to get the current that matrix
                if(!set.add("ROW :"+ i/3 +"COLUMN : "+ j/3 + " NUM :"+board[i][j])) {
                    return false;
                }
            }
        }
        return true;
    }

}
Complexity Analysis:

Time complexity: Above code runs in O(n * m) time where n is the length of input array board row's length and m is the board columns's length, since we are looping through every row and column.
Space complexity: O(n * m) for the HashSet since we are caching every cell in the board to check if it is repeated.

Above implementations source code can be found at GitHub link for Java code