Simple Sudoku Solver using Back-Tracking Algorithm

sudoku-solver.php

<?php
$board = [
    [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]
];

function sudokuSolver($board) {
    $nonPossibilities = [];
    $impossibleNumbers = [];
    $emptySpaces = 1; // this is just a random truthy number to get the loop started

    while($emptySpaces) {
        $emptySpaces = 0;

        for($vertical = 0; $vertical < sizeof($board) ; $vertical++) {
            for($horizontal = 0; $horizontal < sizeof($board) ; $horizontal++) {

                if(!$board[$vertical][$horizontal]) { //find solution possiblities for a field only when it is 0
                    $nonPossibilities = []; // the final solution for a field can not be equal to any of the values stored in this array
                    for($i = 0; $i < 9; $i++) {
                        //checkRow
                        if($board[$vertical][$i] > 0) {
                            $nonPossibilities[$board[$vertical][$i]] = true;
                        }
                        //checkColumn
                        if($board[$i][$horizontal] > 0) {
                            $nonPossibilities[$board[$i][$horizontal]] = true;
                        }
                    }

                    //checkBox - there are 9 3x3 square boxes in the 9x9 sudoku i.e. the computation below
                    for($vBox = floor($vertical / 3) * 3; $vBox < floor($vertical / 3) * 3 + 3; $vBox++) {
                        for($hBox = floor($horizontal / 3) * 3; $hBox < floor($horizontal / 3) * 3 + 3; $hBox++) {
                            if($board[$vBox][$hBox]) {
                                $nonPossibilities[$board[$vBox][$hBox]] = true;
                            }
                        }
                    }

                    $impossibleNumbers = array_keys($nonPossibilities);
                    if(sizeof($impossibleNumbers) === 8){ // if the impossible solutions are 8 in total, the 9th one is forcibly the correct solution
                        for($i = 0; $i < 10; $i++) {
                            if(!in_array($i, $impossibleNumbers)) {
                                $board[$vertical][$horizontal] = $i;
                            }
                        }
                    } else {
                        $emptySpaces++;
                    }                
                }
            }
        }       
    }
    return $board;
}

print_r(sudokuSolver($board));

//result
// [
//     [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]
// ];