Solution For Valid Sudoku

Problem Statement:

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:

• 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.

Solution:

The problem statement is quite clear, we are given a 9×9 Sudoku board with partially filled cells, and we need to determine whether the given Sudoku board is valid or not.

We can iterate over the given board and check the validity of each row, each column, and each 3×3 sub-box. We can use a set to keep track of the digits 1-9 for each row, column, and sub-box. If we encounter a repeated digit, we can return False.

The first step is to iterate over the board and validate each row:

def is_valid_sudoku(board) -> bool:
for row in board:
nums = set()
for num in row:
if num in nums:
return False
if num != ".":
nums.add(num)
return True

Next, we need to validate each column. We can use the zip() function to transpose the board so that we can iterate over each column:

“`
def is_valid_sudoku(board) -> bool:
for row in board:
nums = set()
for num in row:
if num in nums:
return False
if num != “.”:
nums.add(num)

for col in zip(*board):
    nums = set()
    for num in col:
        if num in nums:
            return False
        if num != ".":
            nums.add(num)
return True

“`

Finally, we need to validate each 3×3 sub-box. We can use nested loops to iterate over each sub-box. To determine the sub-box boundaries, we can use integer division to get the indices of the starting row and column of each sub-box:

“`
def is_valid_sudoku(board) -> bool:
for row in board:
nums = set()
for num in row:
if num in nums:
return False
if num != “.”:
nums.add(num)

for col in zip(*board):
    nums = set()
    for num in col:
        if num in nums:
            return False
        if num != ".":
            nums.add(num)

for i in range(0, 9, 3):
    for j in range(0, 9, 3):
        nums = set()
        for k in range(3):
            for l in range(3):
                num = board[i+k][j+l]
                if num in nums:
                    return False
                if num != ".":
                    nums.add(num)
return True

“`

Finally, we can combine all the above code snippets in a single function:

“`
def is_valid_sudoku(board) -> bool:
for row in board:
nums = set()
for num in row:
if num in nums:
return False
if num != “.”:
nums.add(num)

for col in zip(*board):
    nums = set()
    for num in col:
        if num in nums:
            return False
        if num != ".":
            nums.add(num)

for i in range(0, 9, 3):
    for j in range(0, 9, 3):
        nums = set()
        for k in range(3):
            for l in range(3):
                num = board[i+k][j+l]
                if num in nums:
                    return False
                if num != ".":
                    nums.add(num)
return True

“`

Note that we are checking all three conditions in a single pass, so the time complexity is O(81) = O(1). The space complexity is also constant, so the solution is quite efficient.

Step by Step Implementation For Valid Sudoku

public boolean isValidSudoku(char[][] board) {
        // init data
        HashMap [] rows = new HashMap[9];
        HashMap [] columns = new HashMap[9];
        HashMap [] boxes = new HashMap[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashMap();
            columns[i] = new HashMap();
            boxes[i] = new HashMap();
        }

        // validate a board
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                if (num != '.') {
                    int n = (int)num;
                    int box_index = (i / 3 ) * 3 + j / 3;

                    // keep the current cell value
                    rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
                    columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
                    boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);

                    // check if this value has been already seen before
                    if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
                        return false;
                }
            }
        }

        return true;
    }

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # check each row
        for row in board:
            if not self.isValidList(row):
                return False
        
        # check each column
        for i in range(9):
            column = [row[i] for row in board]
            if not self.isValidList(column):
                return False
        
        # check each 3x3 sub-grid
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                subgrid = [board[x][y] for x in range(i, i+3) for y in range(j, j+3)]
                if not self.isValidList(subgrid):
                    return False
        
        return True
    
    def isValidList(self, lst: List[str]) -> bool:
        seen = set()
        for i in lst:
            if i != '.':
                if i in seen:
                    return False
                seen.add(i)
        return True

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    // check each column
    for(let i = 0; i < 9; i++) {
        let seen = {};
        for(let j = 0; j < 9; j++) {
            let num = board[j][i];
            if(num !== '.') {
                if(seen[num]) {
                    return false;
                }
                seen[num] = true;
            }
        }
    }
    
    // check each row
    for(let i = 0; i < 9; i++) {
        let seen = {};
        for(let j = 0; j < 9; j++) {
            let num = board[i][j];
            if(num !== '.') {
                if(seen[num]) {
                    return false;
                }
                seen[num] = true;
            }
        }
    }
    
    // check each 3 x 3 subgrid
    for(let i = 0; i < 9; i++) {
        let seen = {};
        for(let j = 0; j < 9; j++) {
            let r = Math.floor(i / 3) * 3 + Math.floor(j / 3);
            let c = i * 3 % 9 + j % 3;
            let num = board[r][c];
            if(num !== '.') {
                if(seen[num]) {
                    return false;
                }
                seen[num] = true;
            }
        }
    }
    
    return true;
};

bool isValidSudoku(vector>& board) {
        
        // check each row
        for(int i = 0; i < 9; i++){
            unordered_set row;
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.') continue;
                if(row.count(board[i][j])) return false;
                row.insert(board[i][j]);
            }
        }
        
        // check each column
        for(int j = 0; j < 9; j++){
            unordered_set col;
            for(int i = 0; i < 9; i++){
                if(board[i][j] == '.') continue;
                if(col.count(board[i][j])) return false;
                col.insert(board[i][j]);
            }
        }
        
        // check each sub-matrix
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                unordered_set subMatrix;
                for(int k = 0; k < 3; k++){
                    for(int l = 0; l < 3; l++){
                        if(board[3*i+k][3*j+l] == '.') continue;
                        if(subMatrix.count(board[3*i+k][3*j+l])) return false;
                        subMatrix.insert(board[3*i+k][3*j+l]);
                    }
                }
            }
        }
        return true;
    }

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        //validate row
        for(int i = 0; i < 9; i++){
            HashSet row = new HashSet();
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.' && !row.Add(board[i][j]))
                    return false;
            }
        }
        
        //validate column
        for(int j = 0; j < 9; j++){
            HashSet column = new HashSet();
            for(int i = 0; i < 9; i++){
                if(board[i][j] != '.' && !column.Add(board[i][j]))
                    return false;
            }
        }
        
        //validate 3*3 matrix
        for(int block = 0; block < 9; block++){
            HashSet threeByThree = new HashSet();
            for(int i = block / 3 * 3; i < block / 3 * 3 + 3; i++){
                for(int j = block % 3 * 3; j < block % 3 * 3 + 3; j++){
                    if(board[i][j] != '.' && !threeByThree.Add(board[i][j]))
                        return false;
                }
            }
        }
        
        return true;
    }
}