Sudoku problem |Leet Code

Sudoku is a logic-based combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids (also called “boxes”, “regions”, or “blocks”) contain all of the digits from 1 to 9 without repetition.

Here’s what makes a valid Sudoku problem:

Grid Size: The Sudoku grid is always 9×9, divided into nine 3×3 subgrids.
Initial Setup: A valid Sudoku problem starts with some cells filled with numbers, forming a puzzle. These initial numbers must follow these rules:
- Each number from 1 to 9 appears exactly once in each row.
- Each number from 1 to 9 appears exactly once in each column.
- Each number from 1 to 9 appears exactly once in each 3×3 subgrid.
Unique Solution: There should be only one way to solve the Sudoku puzzle. In other words, there should not be multiple valid solutions.
Logical Deduction: A valid Sudoku puzzle can be solved using logic and deduction alone, without requiring guesswork or backtracking. Each step in the solution can be logically justified.

Now, let’s visualize the solution process. I’ll provide a simple Sudoku puzzle and its step-by-step solution:

Sudoku Puzzle:

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

Solution Steps:

Look for Obvious Placements: Start by filling in any obvious numbers. Look for rows, columns, or 3×3 subgrids where there’s only one missing number. For example, in the first row, there’s only one empty cell, so we can place the missing number (1) there.

5 3 . | . 7 . | . . .
...

Scan Rows, Columns, and Subgrids: Continuously scan the rows, columns, and subgrids for any numbers that can be logically placed. For example, in the first row, the missing numbers are 1, 4, 6, and 8. However, 1 is already placed, so we can logically deduce the placements for other missing numbers.

5 3 1 | 2 7 8 | 4 9 6
...

Iterate and Repeat: Keep iterating through the puzzle, filling in numbers based on logic and deduction. Use techniques like “sole candidate”, “unique candidate”, “naked pairs”, etc., to deduce the placements.
Cross-check for Errors: After placing a number, double-check the rows, columns, and subgrids to ensure no violations of the Sudoku rules have occurred.
Persistence: Sudoku puzzles can vary in difficulty, so persistence and patience are key. Sometimes you may need to backtrack if you encounter contradictions, but a valid Sudoku puzzle should ultimately be solvable through logical deduction alone.

By following these steps, you can solve a valid Sudoku puzzle. Remember, practice makes perfect!

public class SudokuSolver {

    private static final int GRID_SIZE = 9;

    // Helper function to check if a number can be placed in a cell
    private static boolean isValid(int[][] grid, int row, int col, int num) {
        // Check if num is already present in the current row or column
        for (int i = 0; i < GRID_SIZE; i++) {
            if (grid[row][i] == num || grid[i][col] == num) {
                return false;
            }
        }
        // Check if num is already present in the current 3x3 subgrid
        int subgridRowStart = row - row % 3;
        int subgridColStart = col - col % 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[subgridRowStart + i][subgridColStart + j] == num) {
                    return false;
                }
            }
        }
        return true;
    }

    // Recursive function to solve the Sudoku puzzle using brute force
    private static boolean solveSudoku(int[][] grid) {
        for (int row = 0; row < GRID_SIZE; row++) {
            for (int col = 0; col < GRID_SIZE; col++) {
                if (grid[row][col] == 0) { // Found an empty cell
                    for (int num = 1; num <= 9; num++) {
                        if (isValid(grid, row, col, num)) {
                            grid[row][col] = num; // Place the number in the cell
                            if (solveSudoku(grid)) { // Recur to solve the rest of the puzzle
                                return true;
                            }
                            grid[row][col] = 0; // Backtrack if no valid solution found
                        }
                    }
                    return false; // No valid number found for the cell
                }
            }
        }
        return true; // Puzzle solved
    }

    // Function to print the Sudoku grid
    private static void printGrid(int[][] grid) {
        for (int row = 0; row < GRID_SIZE; row++) {
            for (int col = 0; col < GRID_SIZE; col++) {
                System.out.print(grid[row][col] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] sudokuGrid = {
            {5, 3, 0, 0, 7, 0, 0, 0, 0},
            {6, 0, 0, 1, 9, 5, 0, 0, 0},
            {0, 9, 8, 0, 0, 0, 0, 6, 0},
            {8, 0, 0, 0, 6, 0, 0, 0, 3},
            {4, 0, 0, 8, 0, 3, 0, 0, 1},
            {7, 0, 0, 0, 2, 0, 0, 0, 6},
            {0, 6, 0, 0, 0, 0, 2, 8, 0},
            {0, 0, 0, 4, 1, 9, 0, 0, 5},
            {0, 0, 0, 0, 8, 0, 0, 7, 9}
        };

        if (solveSudoku(sudokuGrid)) {
            System.out.println("Sudoku puzzle solved:");
            printGrid(sudokuGrid);
        } else {
            System.out.println("No solution exists for the given Sudoku puzzle.");
        }
    }
}

This code defines a SudokuSolver class with methods to validate the puzzle, solve it using a brute force approach, and print the solution. The main method initializes a Sudoku grid with the provided puzzle and attempts to solve it. If a solution exists, it prints the solved Sudoku grid; otherwise, it indicates that no solution exists.

Please note that while the brute force approach works fine for this example, it may not be efficient for more complex Sudoku puzzles.

Leave a Reply Cancel reply