37. 解数独

题意：

解题思路：

思路：
1. 先遍历行，再遍历列，最后遍历3*3方块；
2. 当board[i][j] == '.'时，填充1-9的数，判断该数所在的行、列、单元格是否已有该数，
    如果已存在则尝试下一个数，否则将当前数放置该位置，然后继续放下一个数，
    放置下一个数成功返回true

PHP代码实现：

class Solution {
    function solveSudoku(&$board) {
        if (!$board) return;
        $this->solve($board);
    }
    function solve(&$board) {
        for ($i = 0; $i < count($board); $i++) {
            for ($j = 0; $j < count($board[0]); $j++) {
                if ($board[$i][$j] == '.') {
                    for ($c = '1'; $c <= '9'; $c++) {
                        if ($this->valid($board, $i, $j, $c)) {
                            $board[$i][$j] = (string) $c;
                            if ($this->solve($board)) {
                                return true;
                            }
                            $board[$i][$j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    function valid($board, $row, $col, $c) {
        for ($i = 0; $i < 9; $i++) {
            if ($board[$i][$col] != "." && $board[$i][$col] == $c) return false;
            if ($board[$row][$i] != "." && $board[$row][$i] == $c) return false;
            $x = 3 * floor($row / 3) + floor($i / 3);
            $y = 3 * floor($col / 3) + floor($i % 3);
            if ($board[$x][$y] != '.' && $board[$x][$y] == $c) return false;
        }
        return true;
    }
}

GO代码实现：

func solveSudoku(board [][]byte)  {
    solve(board)
}
func solve(board [][]byte) bool {
    var c byte
    for i := 0; i < 9; i++ { // 行
        for j := 0; j < 9; j++ { // 列
            if board[i][j] == '.' {
                // 要填充的1-9的数字
                for c = '1'; c <= '9'; c++ {
                    // 如果可以放置c
                    if valid(board, i, j, c) {
                        board[i][j] = c
                         // 放置下一个数
                        if solve(board) {
                            return true
                        } else {
                            board[i][j] = '.'
                        }
                    }
                }
                return false
            }
        }
    }
    return true
}
// 检查当前行、列、单元格能否放置c
func valid(board [][]byte, row, col int, c byte) bool {
    for i := 0; i < 9; i++ {
        if board[i][col] == c {
            return false
        }
        if board[row][i] == c {
            return false
        }
        if board[3 * (row/3) + i/3][3 * (col/3) + i%3] == c {
            return false
        }
    }
    return true
}