Valid Sudoku - Java Solution

1. Introduction

In this post, we explore a classic problem from the world of puzzle games: validating a Sudoku board. The challenge lies in checking whether a given 9x9 Sudoku board is valid according to the standard Sudoku rules.

Problem

We need to determine if a 9x9 Sudoku board is valid. A valid board adheres to these 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 3x3 sub-boxes of the grid must also contain the digits 1-9 without repetition.

The validation should only consider the filled cells.

2. Solution Steps

1. Use hash sets to track the numbers present in each row, column, and box.

2. Iterate over each cell of the Sudoku board.

3. For each cell, check if the value violates the rules for its row, column, or box.

4. Return false if any violation is found.

5. Return true if no violations are found after checking all cells.

3. Code Program

public class ValidSudoku {
    public static void main(String[] args) {
        char[][] 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'}
        };
        System.out.println(isValidSudoku(board)); // Test the function
    }

    // Function to validate a Sudoku board
    public static boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            Set<Character> rows = new HashSet<>();
            Set<Character> columns = new HashSet<>();
            Set<Character> cubes = new HashSet<>();

            for (int j = 0; j < 9; j++) {
                // Validate row
                if (board[i][j] != '.' && !rows.add(board[i][j])) return false;

                // Validate column
                if (board[j][i] != '.' && !columns.add(board[j][i])) return false;

                // Validate 3x3 sub-box
                int rowIndex = 3 * (i / 3);
                int colIndex = 3 * (i % 3);
                if (board[rowIndex + j / 3][colIndex + j % 3] != '.' && !cubes.add(board[rowIndex + j / 3][colIndex + j % 3])) return false;
            }
        }
        return true;
    }
}

Output:

true

Explanation:

1. isValidSudoku: This function checks the validity of a Sudoku board.

2. It uses three hash sets to track the numbers present in each row, column, and 3x3 sub-box.

3. The function iterates over each cell, checking if the value already exists in the corresponding row, column, or box set.

4. If a duplicate is found or a rule is violated (indicating an invalid board), the function returns false.

5. If no violations are detected after checking all cells, the board is considered valid, and the function returns true.