题解 | #Sudoku#

package main

import (
    "fmt"
)

func main() {
    a := [9][9]int{}
    row := [9]map[int]bool{}
    col := [9]map[int]bool{}
    block := [3][3]map[int]bool{}

    for i := 0; i < 9; i++ {
        row[i] = map[int]bool{}
        col[i] = map[int]bool{}
    }

    for i := 0; i < 3; i++ {
        for j := 0; j < 3; j++ {
            block[i][j] = map[int]bool{}
        }
    }

    zeros := [][]int{}


    for i := 0 ; i < 9; i ++ {
        for j := 0; j < 9; j++ {
            fmt.Scan(&a[i][j])

            if a[i][j] != 0 {
                row[i][a[i][j]] = true
                col[j][a[i][j]] = true
                block[i/3][j/3][a[i][j]] = true
            } else {
                zeros = append(zeros, []int{i,j})
            }
        }
    }

    var dfs func(zs [][]int) bool
    dfs = func(zs [][]int) bool {
        if len(zs) == 0 {
            return true
        }
        zero := zs[0]
        x, y := zero[0], zero[1]
        for i := 1; i <= 9; i++ {
            if !row[x][i] && !col[y][i] && !block[x/3][y/3][i] {
                row[x][i] = true
                col[y][i] = true
                block[x/3][y/3][i] = true
                a[x][y] = i
                if dfs(zs[1:]) {
                    return true
                }
                row[x][i] = false
                col[y][i] = false
                block[x/3][y/3][i] = false
                a[x][y] = 0
            } 
        }
        return false
    }

    dfs(zeros)

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