package main

import (
    "bufio"
    "strconv"
    // "bufio"
    "fmt"
    "os"
    "io"
    // "io/ioutil"
)
type sudoku struct {
    d [9][9] int
    x, y int
}
//构造类型方法Get
func (sdk *sudoku) get() int {
    return sdk.d[sdk.y][sdk.x]
}
func (sdk *sudoku) put(num int) {
    sdk.d[sdk.y][sdk.x] = num
}
func (sdk *sudoku) next() {
    if sdk.x < 8 {
        sdk.x++
    } else {
        sdk.x = 0
        sdk.y++
    }
}

func main() {
    filePathIn := "./sudoku_in.txt"
    // filePathOut := "./sudoku_out.txt"
    // fmt.Println(strconv.Atoi("0"))

    var sdk sudoku;
    sdk = readfile(filePathIn)

    fmt.Println("数独in:")
    print(sdk)
    fmt.Println("数独out:")
    ret, bo := loop(sdk)
    if bo == true {
        print(ret)
    }else{
        fmt.Println("无解")
    }
}

func loop(sdk sudoku) (sudoku, bool){
    //递归截止
    if sdk.x == 8 && sdk.y == 8 {
        if sdk.get() != 0 {
            return sdk, true
        }
        calcList := calcOne(sdk)
        for _,v := range calcList {
            if v != 0 {
                sdk.put(v)
                return sdk, true
            }
        }
        return sdk, false
    }
    //当前是否为0
    if sdk.get() != 0 {
        sdk.next()
        return loop(sdk)
    }
    //当前值为0 遍历所有情况
    calcList := calcOne(sdk)
    for _,v := range calcList {
        if v != 0 {
            sdk.put(v)
            retSdk, bo := loop(sdk)
            if bo == true {
                return retSdk, true
            }
        }
    }
    return sdk, false
}

func calcOne(sdk sudoku) [10]int {
    var ret = [10]int {0,1,2,3,4,5,6,7,8,9}
    for i:=0; i<9; i++ {
        //判断x
        ret[sdk.d[sdk.y][i]] = 0
        //判断y
        ret[sdk.d[i][sdk.x]] = 0
        //判断小宫格
        ret[sdk.d[int(sdk.y / 3) * 3 + int(i / 3)][int(sdk.x / 3) * 3 + (i % 3)]] = 0
    }
    return ret
}

func readfile(filepath string) (sudoku){
    //读取文件
    f, _ := os.Open(filepath)
    defer f.Close()

    //逐行读取
    fileObj := bufio.NewReader(f)
    var ret sudoku
    var lineNum int = 0
    for {
        line, _, err := fileObj.ReadLine()
        if err != nil { //遇到任何错误立即返回，并忽略 EOF 错误信息
            if err == io.EOF {
                break
            }
        }
        // fmt.Println(string(line))
        for k,v := range string(line) {
            // fmt.Println(k,v)
            num, _ := strconv.Atoi(string(v))
            ret.d[lineNum][k] = num
            // fmt.Println(num)
        }
        lineNum++
    }
    return ret
}

func print(arr sudoku){
    var i,o int
    var pr string
    for i = 0; i < 9; i++ {
        pr = ""
        for o = 0; o < 9; o++ {
            pr = pr + strconv.Itoa(arr.d[i][o]) + " "
            // pr2 = pr2 + string(arr[i][o]) + " "
            // fmt.Println(arr[i][o])
        }
        fmt.Println(pr)
    }
}