37. 解数独

<?php
class Solution {
    /**
     * @param String[][] $board
     * @return NULL
     */
    function solveSudoku(&$board) {
        $n = count($board);
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($board[$i][$j] != '.') continue;
                for ($num = 1; $num < 10; $num++) {
                    $board[$i][$j] = $num;
                    if ($this->isValidSudoku($board) && $this->solveSudoku($board)) {
                        return true;
                    }
                    // 先填入的值，在递归后续不满足，需要重置
                    $board[$i][$j] = '.';
                }
                // 上面循环的值（1 - 9）没有满足的情况，则返回false，回溯到上一次填值。（表示此路不通）
                return false;
            }
        }
        return true;
    }
    public function isValidSudoku(array $sudo) {
        $n = count($sudo);
        $littleSquare = [];
        $col = [];
        for ($i = 0; $i < $n; $i++) {
            $row = [];
            for ($j = 0; $j < $n; $j++) {
                // '.' 跳过
                if ($sudo[$i][$j] == '.') continue;
                // 检查行
                if (isset($row[$sudo[$i][$j]])) {
                    return false;
                } else {
                    $row[$sudo[$i][$j]] = 1;
                }
                // 检查列
                if (isset($col[$j][$sudo[$i][$j]])) {
                    return false;
                } else {
                    $col[$j][$sudo[$i][$j]] = 1;
                }
                // 检查小正方形
                if (isset($littleSquare[floor($i / 3)][floor(($j / 3))][$sudo[$i][$j]])) {
                    return false;
                } else {
                    $littleSquare[floor($i / 3)][floor(($j / 3))][$sudo[$i][$j]] = 1;
                }
            }
        }
        return true;
    }
}
$sudo = [
    ["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"]
];
$cls = new Solution();
$ret = $cls->solveSudoku($sudo);
if ($ret) {
    array_walk($sudo, function (&$v) {
        $v = implode(',', $v);
    });
    echo implode("\n", $sudo);
} else {
    echo 'false';
}