php生成和解决数独

&lt;?php

namespace numbers;

require "SudokuGenerator.php";

class SudokuSolve
{
    /**
     * 解数独
     * @param String[][] $board
     * @return NULL
     */
    public function solveSudoku(&amp;$board)
    {
        if (count($board) != 9 || count($board[0]) != 9) return false;
        //初始化
        $rows = $columns = $blocks = [];
        $nums = array_flip(range(1, 9));
        for ($i = 0; $i &lt; 9; $i++) {
            $rows[$i] = $nums;
            $columns[$i] = $nums;
            $blocks[$i] = $nums;
        }
        //收集需要填数的位置
        $empty = [];
        for ($i = 0; $i &lt; 9; $i++) {
            for ($j = 0; $j &lt; 9; $j++) {
                if ($board[$i][$j] != '.') {
                    $num = $board[$i][$j];
                    $b = intval($i / 3) * 3 + intval($j / 3);
                    unset($rows[$i][$num], $columns[$j][$num], $blocks[$b][$num]);
                } else {
                    $empty[] = [$i, $j];
                }
            }
        }
        return $this-&gt;backtrack($board, $empty, $rows, $columns, $blocks);
    }

    private function backtrack(&amp;$board, $empty, $rows, $columns, $blocks, $index = 0)
    {
        if ($index == count($empty)) {
            return true;
        }
        [$i, $j] = $empty[$index];
        $b = intval($i / 3) * 3 + intval($j / 3);
        $nums = array_intersect(array_keys($rows[$i]), array_keys($columns[$j]), array_keys($blocks[$b]));
        foreach ($nums as $num) {
            unset($rows[$i][$num], $columns[$j][$num], $blocks[$b][$num]);
            $board[$i][$j] = (int)$num;
            if ($this->backtrack($board, $empty, $rows, $columns, $blocks, $index + 1))
                return true;
            $rows[$i][$num] = $num;
            $columns[$j][$num] = $num;
            $blocks[$b][$num] = $num;
        }
        return false;
    }

    // 对前端传来的数独结果进行检测
    public function isValidSudoku($board)
    {
        $rows = array_fill(0, 9, array_fill(0, 9, false));
        $columns = array_fill(0, 9, array_fill(0, 9, false));
        $subBoxes = array_fill(0, 3, array_fill(0, 3, array_fill(0, 9, false)));
        foreach ($board as $i => $row) {
            foreach ($row as $j => $c) {
                if ($c !== 0) {
                    $index = ord($c) - ord('1');

                    if ($rows[$i][$index] || $columns[$j][$index] || $subBoxes[$i / 3][$j / 3][$index]) {
                        return false;
                    }

                    $rows[$i][$index] = true;
                    $columns[$j][$index] = true;
                    $subBoxes[$i / 3][$j / 3][$index] = true;
                }
            }
        }
        return true;
    }
}

$solution = new SudokuSolve();
$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"]];
// $board = [[4, 7, 0, 3, 9, 1, 5, 6, 2], [0, 0, 0, 0, 5, 6, 4, 1, 7], [6, 1, 0, 4, 7, 2, 9, 8, 3], [0, 0, 6, 2, 0, 3, 1, 7, 0], [8, 2, 1, 7, 6, 0, 0, 9, 4], [3, 5, 7, 1, 4, 9, 0, 2, 0], [1, 9, 4, 5, 2, 0, 6, 3, 8], [7, 8, 0, 6, 1, 4, 2, 0, 9], [0, 6, 2, 9, 0, 0, 0, 4, 1]];
$sudokuGenerator = new SudokuGenerator();
$sudoku = $sudokuGenerator->generateSudoku();
$board = $sudokuGenerator->removeNumbers(60);  // 难度级别，可以调整，越大越难
var_dump(json_encode($board, 320));

$isValidSudoku = $solution->isValidSudoku($board);
if (!$isValidSudoku) {
    echo '数独不合法！';
    die();
}
echo '数独合法！解答如下：';
$solution->solveSudoku($board);

// 数独结果
var_dump(json_encode($board, 320));