37. Sudoku Solver

[mah-shamim]

Topics: Array, Hash Table, Backtracking, Matrix

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Example 1:

• Input: 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"]]
• Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
• Explanation: The input board is shown above and the only valid solution is shown below:

Example 2:

• Input: board = [[".",".",".",".",".",".",".",".","."],[".","9",".",".","1",".",".","3","."],[".",".","6",".","2",".","7",".","."],[".",".",".","3",".","4",".",".","."],["2","1",".",".",".",".",".","9","8"],[".",".",".",".",".",".",".",".","."],[".",".","2","5",".","6","4",".","."],[".","8",".",".",".",".",".","1","."],[".",".",".",".",".",".",".",".","."]]
• Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

[mah-shamim]

We need to optimize the Sudoku solver by reducing the time complexity of validity checks. The previous approach checked each digit's validity by scanning the entire row, column, and 3x3 box, which is inefficient. Instead, we can use arrays to keep track of which digits are already present in each row, column, and box. This allows us to check the validity of a digit in constant time.

Approaches

1. Initialization: Initialize three arrays ($rows, $cols, $boxes) to keep track of digits present in each row, column, and 3x3 box.
2. Preprocessing: Populate these arrays based on the initial board configuration.
3. Backtracking with Memoization: Use backtracking to try digits 1-9 for each empty cell, but now use the precomputed arrays to check validity in constant time.
4. Recursion: Recursively attempt to fill empty cells, backtracking when no valid digit is found.

Let's implement this solution in PHP: 37. Sudoku Solver

<?php
/**
 * @param String[][] $board
 * @return NULL
 */
function solveSudoku(&$board) {
    $rows = array_fill(0, 9, array_fill(0, 10, false));
    $cols = array_fill(0, 9, array_fill(0, 10, false));
    $boxes = array_fill(0, 9, array_fill(0, 10, false));

    // Initialize the arrays based on the current board
    for ($i = 0; $i < 9; $i++) {
        for ($j = 0; $j < 9; $j++) {
            if ($board[$i][$j] != '.') {
                $num = (int)$board[$i][$j];
                $boxIndex = intdiv($i, 3) * 3 + intdiv($j, 3);
                $rows[$i][$num] = true;
                $cols[$j][$num] = true;
                $boxes[$boxIndex][$num] = true;
            }
        }
    }

    solve($board, 0, $rows, $cols, $boxes);
}

/**
 * @param $board
 * @param $index
 * @param $rows
 * @param $cols
 * @param $boxes
 * @return bool
 */
private function solve(&$board, $index, &$rows, &$cols, &$boxes) {
    if ($index == 81) {
        return true;
    }

    $row = intdiv($index, 9);
    $col = $index % 9;

    if ($board[$row][$col] != '.') {
        return solve($board, $index + 1, $rows, $cols, $boxes);
    }

    $boxIndex = intdiv($row, 3) * 3 + intdiv($col, 3);
    for ($c = 1; $c <= 9; $c++) {
        if (!$rows[$row][$c] && !$cols[$col][$c] && !$boxes[$boxIndex][$c]) {
            $board[$row][$col] = (string)$c;
            $rows[$row][$c] = true;
            $cols[$col][$c] = true;
            $boxes[$boxIndex][$c] = true;

            if (solve($board, $index + 1, $rows, $cols, $boxes)) {
                return true;
            }

            $board[$row][$col] = '.';
            $rows[$row][$c] = false;
            $cols[$col][$c] = false;
            $boxes[$boxIndex][$c] = false;
        }
    }

    return false;
}

// Test cases
// Example 1
$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"]
];

solveSudoku($board);

// Print solved board
foreach ($board as $row) {
    echo implode(" ", $row) . PHP_EOL;
}

// Example 2
$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"]
];

solveSudoku($board);

// Print solved board
foreach ($board as $row) {
    echo implode(" ", $row) . PHP_EOL;
}
?>

Explanation:

1. Initialization: We initialize three arrays ($rows, $cols, $boxes) to keep track of digits present in each row, column, and 3x3 box.
2. Preprocessing: We populate these arrays by iterating through the initial board, marking digits that are already present.
3. Backtracking: The solve function uses backtracking to fill empty cells. For each cell, it checks digits 1-9 using the precomputed arrays to ensure validity in constant time.
4. Recursion: If a digit is valid, it is placed in the cell, and the function recurses to the next cell. If the recursion fails, the digit is removed, and the next digit is tried.
5. Termination: The function returns true when all cells are filled correctly, ensuring the solution meets all Sudoku rules.

This optimized approach significantly reduces the time complexity of validity checks, making the solution efficient enough to handle the constraints.

[kovatz]

Thanks for solving the problem of "Sudoku Solver"

[mah-shamim]

Thanks