PHP Coding Puzzle 10 : Sudoku Game

Possible Solution :

To solve a Sudoku puzzle in PHP, you can use a variety of algorithms and techniques to implement the logic and deduction required to fill in the cells of the grid. Here are some steps you can follow to create a basic Sudoku solver in PHP:

1. Create a 9×9 two-dimensional array to represent the Sudoku grid. You can initialize the array with the starting numbers from the puzzle, or leave the cells blank if you want to solve the puzzle from scratch.

$sudoku = array(
    array(5, 3, 0, 0, 7, 0, 0, 0, 0),
    array(6, 0, 0, 1, 9, 5, 0, 0, 0),
    array(0, 9, 8, 0, 0, 0, 0, 6, 0),
    array(8, 0, 0, 0, 6, 0, 0, 0, 3),
    array(4, 0, 0, 8, 0, 3, 0, 0, 1),
    array(7, 0, 0, 0, 2, 0, 0, 0, 6),
    array(0, 6, 0, 0, 0, 0, 2, 8, 0),
    array(0, 0, 0, 4, 1, 9, 0, 0, 5),
    array(0, 0, 0, 0, 8, 0, 0, 7, 9)
);


2. Implement a function to check if a given number is valid for a particular cell in the grid. To be valid, the number must not appear in the same row, column, or 3×3 box as any other number in the grid.

function isValid($sudoku, $row, $col, $num) {
    // Check row
    for ($i = 0; $i < 9; $i++) {
        if ($sudoku[$row][$i] == $num) {
            return false;
        }
    }
    // Check column
    for ($i = 0; $i < 9; $i++) {
        if ($sudoku[$i][$col] == $num) {
            return false;
        }
    }
    // Check box
    $box_row = floor($row / 3) * 3;
    $box_col = floor($col / 3) * 3;
    for ($i = 0; $i < 3; $i++) {
        for ($j = 0; $j < 3; $j++) {
            if ($sudoku[$box_row + $i][$box_col + $j] == $num) {
                return false;
            }
        }
    }
    return true;
}

3. Implement a recursive function to solve the puzzle. The function should take the current row and column as input, and recursively try to fill in the cells of the grid one by one. If a cell is already filled in, the function should move on to the next cell. If a cell is blank, the function should try all possible numbers from 1 to 9, and recursively call itself with the next row and column if a valid number is found. If no valid number is found, the function should backtrack and try a different number in the previous cell.

function solveSudoku(&$sudoku, $row, $col) {
    if ($row == 9) {
        return true;  // Solved
    }
    if ($sudoku[$row][$col] != 0) {
        // Cell is already filled in, move to next cell
        if ($col == 8) {
            return solveSudoku($sudoku, $row + 1, 0);
        } else {
            return solveSudoku($sudoku, $row, $col + 1);
        }
    } else {
        // Cell is blank, try all possible numbers
        for ($num = 1; $num <= 9; $num++) {
            if (isValid($sudoku, $row, $col, $num)) {
                $sudoku[$row][$col] = $num;
                if ($col == 8) {
                    $next_row = $row + 1;
                    $next_col = 0;
                } else {
                    $next_row = $row;
                    $next_col = $col + 1;
                }
                if (solveSudoku($sudoku, $next_row, $next_col)) {
                    return true;  // Solved
                } else {
                    // Backtrack
                    $sudoku[$row][$col] = 0;
                }
            }
        }
        return false;  // No valid number found
    }
}

4. To solve a Sudoku puzzle, you can call the solveSudoku() function with the initial row and column values (0, 0):

solveSudoku($sudoku, 0, 0);

This will modify the original $sudoku array to contain the solved puzzle.

Note that this is a basic algorithm for solving Sudoku puzzles, and may not be optimal or efficient for all cases. There are many more advanced techniques and algorithms that can be used to solve Sudoku puzzles more efficiently, such as backtracking with forward checking, constraint propagation, and more.