题解 | #Sudoku# go#acm模式

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)


func check(matrix [][]int, row, col, value int) bool {
    /*
            检测在(row,col)放value是否合适
            1.每行含1-9,不含重复值value
            2.每列含1-9,不含重复值value
            3.3*3区块含1-9,不含重复值value
    */
    for j := 0; j < 9; j ++ {
        // 检测每行
        if matrix[row][j] == value {
            return false
        }
        // 检测每列
        if matrix[j][col] == value {
            return false
        }
    }
    // 检测元素所在3*3区域
    area_row := (row / 3) * 3
    area_col := (col / 3) * 3
    for i := area_row; i < area_row +3; i ++ {
        for j := area_col; j < area_col +3; j ++ {
            if matrix[i][j] == value {
                return false
            }
        }

    }
    return true
}


func solveSudoku(matrix [][]int, count int) bool {
    if count == 81 {
        return true
    }
    row := count / 9 // 行标
    col := count % 9 // 列表

    if matrix[row][col] != 0 { // 已填充
        return solveSudoku(matrix, count+1)
    }
    for i := 1; i < 10; i++ {
        if check(matrix, row, col, i) { // 找到可填充的数
            matrix[row][col] = i
            if solveSudoku(matrix, count+1) {
                return true
            }
            matrix[row][col] = 0
        }

    }
    return false
}


func main() {
    r := bufio.NewScanner(os.Stdin)
    matrix := make([][]int, 0)
    for  {
        r.Scan()
        str := r.Text()
        if str == "" {
            break
        }
        n := make([]int, 0, 9)
        for _, v := range strings.Split(str, " ") {
            s, _ := strconv.Atoi(v)
            n = append(n, s)
        }
        matrix = append(matrix, n)
    }
    solveSudoku(matrix, 0)
    for _, v := range matrix {
        res := ""
        for _, j := range v {
            res += fmt.Sprintf("%d ", j)

        }
        fmt.Println(res)

    }
}