36. Valid Sudoku

Description

Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled Sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.

• Only the filled cells need to be validated according to the mentioned rules.

Constraints

• The given board contain only digits 1-9 and the character '.'

• The given board size is always 9x9.

Approach

Links

• GeeksforGeeks
• Leetcode
• ProgramCreek

• YouTube

Examples

Example 1

Input:

[

["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

Example 2

Input:

[

["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: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Solutions

Solution 1

/**
 * Time complexity : O(n*n)
 * Space complexity : O(n*n)
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        Set<String> seen = new HashSet<>();
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                char ch = board[i][j];
                if(ch != '.') {
                    if(!seen.add(ch + "-r-" + i) || 
                       !seen.add(ch + "-c-" + j) || 
                       !seen.add(ch + "-b-" + i/3 + "-" + j/3)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < SIZE; i++) {
            if(!(isValidRow(board, i) && isValidColumn(board, i))) return false;
        }
        for(int i = 0; i < SIZE; i += 3) {
            for(int j = 0; j < SIZE; j += 3) {
                if(!isValidBox(board, i, j)) return false;
            }
        }
        return true;
    }
    
    private boolean isValidRow(char[][] board, int row) {
        Set<Integer> rowValues = new HashSet<>();
        for(int i = 0; i < SIZE; i++) {
            int val = board[row][i]-'0';
            if(val == -2) continue;
            if(val < 1 || val > 9 || rowValues.add(val) == false) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isValidColumn(char[][] board, int col) {
        Set<Integer> colValues = new HashSet<>();
        for(int i =0; i < SIZE; i++) {
            int val = board[i][col]-'0';
            if(val == -2) continue;
            if(val < 1 || val > 9 || colValues.add(val) == false) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isValidBox(char[][] board, int row, int col) {
        Set<Integer> boxValues = new HashSet<>();
        for(int i = row; i < row+3; i++) {
            for(int j = col; j < col+3; j++) {
                int val = board[i][j]-'0';
                if(val == -2) continue;
                if(val < 1 || val > 9 || boxValues.add(val) == false) {
                    return false;
                }
            }
        }
        return true;
    }
}

Solution 3

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[SIZE][SIZE];
        boolean[][] cols = new boolean[SIZE][SIZE];
        boolean[][] boxes = new boolean[SIZE][SIZE];
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                int num = board[i][j]-'1';
                if(num >= 0) {
                    int box_index = (i / 3) * 3 + j / 3;
                    if(rows[i][num] || cols[j][num] || boxes[box_index][num]) {
                        return false;
                    }
                    rows[i][num] = true;
                    cols[j][num] = true;
                    boxes[box_index][num] = true;   
                }
            }
        }
        return true;
    }
}

Solution 4

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < SIZE; i++) {
            boolean[] row = new boolean[SIZE];
            boolean[] col = new boolean[SIZE];
            boolean[] box = new boolean[SIZE];
            for(int j = 0; j < SIZE; j++) {
                int num = board[i][j]-'1';
                if(board[i][j] != '.') {
                    if(row[board[i][j]-'1']) return false;
                    row[board[i][j]-'1'] = true;
                }
                if(board[j][i] != '.') {
                    if(col[board[j][i]-'1']) return false;
                    col[board[j][i]-'1'] = true;
                }
                int boxi = (i/3)*3 + j/3;
                int boxj = (i%3)*3 + j%3;
                if(board[boxi][boxj] != '.') {
                    if(box[board[boxi][boxj]-'1']) return false;
                    box[board[boxi][boxj]-'1'] = true;
                }
            }
        }
        return true;
    }
}

Follow up

• Program for Sudoku Generator - GFG
• Validity of a given Tic-Tac-Toe board configuration - GFG