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:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

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

Examples

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

Solutions

/**
 * 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;
    }
}

/**
 * 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;
    }
}

/**
 * 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;
    }
}

/**
 * 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

Previous34. Find First and Last Position of Element in Sorted Array Next37. Sudoku Solver

Last updated 4 years ago

Was this helpful?