题解 | #Sudoku#

package main

import (
	"fmt"
)

func main() {
	var Map [9][9]int
	var XYArrInXY []InXY
	var intvalMap = make(map[string][]int, 0)
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			a := 0
			fmt.Scan(&a)
			if a == 0 {
				XYArrInXY = append(XYArrInXY, InXY{
					X: i,
					Y: j,
				})
			}
			Map[i][j] = a
		}
	}
	var i = 0
	var length = len(XYArrInXY)

	for i < length {
		xy := XYArrInXY[i]
		Map[xy.X][xy.Y] = 0
		if res, ok := intvalMap[fmt.Sprintf("%d-%d", xy.X, xy.Y)]; ok {
			if len(res) == 0 {
				delete(intvalMap, fmt.Sprintf("%d-%d", xy.X, xy.Y))
				xy = XYArrInXY[i-1]
				res1 := intvalMap[fmt.Sprintf("%d-%d", xy.X, xy.Y)]
				res1 = res1[1:]
				intvalMap[fmt.Sprintf("%d-%d", xy.X, xy.Y)] = res1
				i--
			} else {
				Map[xy.X][xy.Y] = res[0]
				i++
			}

		} else {
			//扫描
			res := Scan(Map, xy)
			intvalMap[fmt.Sprintf("%d-%d", xy.X, xy.Y)] = res
		}

	}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			fmt.Printf("%d", Map[i][j])
			if j < 8 {
				fmt.Printf(" ")
			} else {
				fmt.Printf("\n")
			}
		}
	}
}

type InXY struct {
	X int
	Y int
}

func Scan(Map [9][9]int, xy InXY) (res []int) {
	var boolMap = make(map[int]bool)
	for i := 0; i < 9; i++ {
		if Map[i][xy.Y] != 0 {
			boolMap[Map[i][xy.Y]] = true
		}
		if Map[xy.X][i] != 0 {
			boolMap[Map[xy.X][i]] = true
		}
	}
	for i := xy.X / 3 * 3; i < xy.X/3*3+3; i++ {
		for j := xy.Y / 3 * 3; j < xy.Y/3*3+3; j++ {
			if Map[i][j] != 0 {
				boolMap[Map[i][j]] = true
			}
		}
	}
	for i := 1; i <= 9; i++ {
		if !boolMap[i] {
			res = append(res, i)
		}
	}
	return res
}