Go语言实现的最简单数独解法

soduku.go

package main
import (
    "fmt"
)
type node []int
var sudokumay [9][9]node
var sudoku = [9][9]int{
    {0, 0, 0, 0, 0, 0, 8, 0, 0},
    {0, 8, 2, 4, 0, 0, 0, 0, 0},
    {1, 9, 0, 0, 6, 3, 0, 0, 0},
    {0, 5, 0, 0, 8, 0, 7, 0, 0},
    {6, 7, 8, 2, 0, 9, 1, 4, 3},
    {0, 0, 3, 0, 4, 0, 0, 8, 0},
    {0, 0, 0, 6, 2, 0, 0, 9, 4},
    {0, 0, 0, 0, 0, 5, 6, 1, 0},
    {0, 0, 0, 6, 0, 0, 0, 0, 0}}
func main() {
    n := inited(sudoku)
    sudokusure, _ := sure(sudokumay)
    for n > 0 {
        n = subinit(sudokusure)
        // output(sudokumay)
        // fmt.println(n)
        sudokusure, _ = sure(sudokumay)
    }
    output(sudokumay)
    fmt.println(isenable(sudokumay))
    // test()
}
func isenable(tn [9][9]node) bool {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if len(tn[i][j]) == 0 {
                return false
            }
        }
    }
    return true
}
func sure(may [9][9]node) (sure [9][9]int, n int) {
    n = 0
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if len(may[i][j]) == 1 {
                sure[i][j] = may[i][j][0]
                n++
            } else {
                sure[i][j] = 0
            }
        }
    }
    return
}
func test() {
    i, j := 1, 3
    fmt.println(sudoku[i][j])
    for k := ((i / 3) * 3); k < ((i/3)*3)+3; k++ {
        for l := ((j / 3) * 3); l < ((j/3)*3)+3; l++ {
            fmt.print(sudoku[k][l])
        }
        fmt.println(" ")
    }
}
func inited(sud [9][9]int) (changecount int) {
    tmp := 0
    changecount = 0
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if sud[i][j] != 0 {
                sudokumay[i][j] = append(sudokumay[i][j], sud[i][j])
            } else {
                for k := 0; k < 9; k++ {
                    sudokumay[i][j] = append(sudokumay[i][j], k+1)
                }
                sudokumay[i][j], tmp = excludemay(i, j, sudokumay[i][j], sud)
                changecount += tmp
            }
        }
    }
    return
}
func subinit(sud [9][9]int) (changecount int) {
    tmp := 0
    changecount = 0
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if sud[i][j] != 0 {
                sudokumay[i][j][0] = sud[i][j]
            } else {
                sudokumay[i][j], tmp = excludemay(i, j, sudokumay[i][j], sud)
                changecount += tmp
            }
        }
    }
    return
}
func excludemay(ti, tj int, t node, s [9][9]int) (rmay node, changecount int) {
    changecount = 0
    var tmpchangecount int
    for i := 0; i < 9; i++ {
        if s[i][tj] != 0 {
            t, tmpchangecount = exclude(t, s[i][tj])
            changecount += tmpchangecount
        }
        if s[ti][i] != 0 {
            t, tmpchangecount = exclude(t, s[ti][i])
            changecount += tmpchangecount
        }
    }
    for k := ((ti / 3) * 3); k < ((ti/3)*3)+3; k++ {
        for l := ((tj / 3) * 3); l < ((tj/3)*3)+3; l++ {
            if s[k][l] != 0 {
                t, tmpchangecount = exclude(t, s[k][l])
                changecount += tmpchangecount
            }
        }
    }
    rmay = t
    return
}
func excludefirstone(smay node, n int) (rmay node, changecount int) {
    changecount = 0
    rmay = smay
    for i := 0; i < len(smay); i++ {
        if smay[i] == n {
            changecount++
            rmay = append(smay[:i], smay[i+1:]...)
            return
        }
        if i == len(smay)-1 {
            return
        }
    }
    return
}
func exclude(smay node, n int) (tmp node, changecount int) {
    var nc int
    changecount = 0
    tmp, nc = excludefirstone(smay, n)
    for nc > 0 {
        tmp, nc = excludefirstone(tmp, n)
        changecount++
    }
    return
}
func output(sudoku [9][9]node) {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            fmt.print(sudokumay[i][j])
        }
        fmt.println("")
    }
}

以上就是本文给大家分享的代码的全部内容了，希望大家能够喜欢。