题解 | #Sudoku#

package main

import (
    "fmt"
)

func isValid(matrix [][]int, row int, col int, k int) bool {
    m, n := len(matrix), len(matrix[0])
    // 检查行
    for j:=0; j<n; j++ {
        if matrix[row][j] == k {
            return false
        }
    }

    // 检查列
    for i:=0; i<m; i++ {
        if matrix[i][col] == k {
            return false
        }
    }

    // 检查一个小方格
    startX, startY := (row/3)*3, (col/3)*3
    for i:=startX; i<startX+3; i++ {
        for j:=startY; j<startY+3; j++ {
            if matrix[i][j] == k {
                return false
            }
        }
    }

    return true
}

func backtracking(matrix [][]int) bool {
    for i:=0; i<9; i++ {
        for j:=0; j<9; j++ {
            if matrix[i][j] != 0 {
                continue
            }

            for k:=1; k<=9; k++ {
                if isValid(matrix, i, j, k) {
                    matrix[i][j] = k
                    if backtracking(matrix) {
                        return true
                    }
                    matrix[i][j] = 0
                }
            }

            return false
        }
    }

    // fmt.Printf("matrix: %+v\n", matrix)

    return true
}

func main() {
    m, n := 9, 9

    matrix := make([][]int, m)
    for i:=0; i<m; i++ {
        matrix[i] = make([]int, n)
    }

    for i:=0; i<m; i++ {
        for j:=0; j<n; j++ {
            var num int
            fmt.Scan(&num)
            matrix[i][j] = num
        }
    }

    backtracking(matrix)

    for i:=0; i<9; i++ {
        for j:=0; j<9; j++ {
            fmt.Printf("%d ", matrix[i][j])
        }
        fmt.Println()
    }
}

// 本题输入为一个矩阵，所以采用 fmt.Scan(&num)