37解数独.md

func solveSudoku(board [][]byte)  {
    backtrack(board)
}

func backtrack(board [][]byte) bool {
    // 对于每一行每一列的每一个数，，确定是否合适
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            // 若已填入数则跳过
            if board[i][j] != '.' {
                continue
            }
            // 需要对1-9进行回溯递归找到合适的值
            for k := '1'; k <= '9'; k++ {
                if isValid(i, j, byte(k), board) {
                    board[i][j] = byte(k)
                    // 当递归返回true时，找到了当前cell合适的值，直接返回
                    if backtrack(board) {
                        return true
                    }
                    board[i][j] = '.'
                }
            }
            // 当1-9所有值都不符合时，没有正确答案，返回false
            return false
        }
    }
    // 遍历完了全部棋盘，返回true
    return true
}

func isValid(row, col int, val byte, board [][]byte) bool {
    // 检查行
    for i := 0; i < 9; i++ {
        if board[i][col] == val {
            return false
        }
    }
    // 检查列
    for i := 0; i < 9; i++ {
        if board[row][i] == val {
            return false
        }
    }
    // 检查九宫格
    startRow := (row / 3) * 3
    startCol := (col / 3) * 3
    for i := startRow; i < startRow + 3; i++ {
        for j := startCol; j < startCol + 3; j++ {
            if board[i][j] == val {
                return false
            }
        }
    }
    return true
}