解数独程序分享,有问题求解!!!

gs272 · 2013-05-02 13:59:38 · 4286 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2013-05-02 13:59:38 的主题,其中的信息可能已经有所发展或是发生改变。

下面是我写的解数独的代码,呵呵,水平有限,比较乱,但感觉解题还是比较快的,代码中的那个题号称史上最难的11级数独,不到2秒也能解出。 我有个问题,我这个程序只能得出一组答案,怎么才能得出成立的多个答案呢? 求大神帮忙看看!

package main

import "fmt"

//数独中的单元格
type Box struct {
    Figure uint8
    Lock   bool
    //未填数的格可以填写的数字数目
    nOp int
    //未填数的格可以填写的数字列表
    Op []int
}

//数独题
type Form [9][9]Box

var (
    Num     int
    readbuf string = "800000000003600000070090200050007000000045700000100030001000068008500010090000400"
)

func main() {
    form := new(Form)
    form.InitShudu(readbuf)
    fmt.Println("已读取数独题:")
    form.Print()
    if form.Answer() {
        fmt.Println("成功解答,共计算了", Num, "次!")
        form.Print()
    }
}

//填充Box
func (form *Form) InitShudu(buf string) {
    //计算次数初始化
    Num = 0
    //填充数列
    i := 0
    j := 0
    for _, v := range buf {
        form[i][j].Figure = uint8(v) - 48
        if v != '0' {
            form[i][j].Lock = true
        }
        j++
        if j > 8 {
            j = 0
            i++
        }
    }
}

//验证是否数独是否成立
func (form *Form) CheckAll() bool {
    row := [9]uint8{}
    //横向检查
    for _, vform := range form {
        for j, v := range vform {
            row[j] = v.Figure
        }
        if !CheckLine(row) {
            return false
        }
        row = [9]uint8{}
    }
    //竖向检查
    n := 0
    for i := 0; i < 9; i++ {
        for _, vform := range form {
            for j, v := range vform {
                if j == i {
                    row[n] = v.Figure
                    n++
                }
            }
        }
        if !CheckLine(row) {
            return false
        }
        row = [9]uint8{}
        n = 0
    }
    //块检查
    for i := 0; i < 9; i += 3 {
        for j := 0; j < 9; j += 3 {
            nx := getx(i)
            ny := gety(j)
            for _, vx := range nx {
                for _, vy := range ny {
                    row[n] = form[vx][vy].Figure
                    n++
                }
            }
            if !CheckLine(row) {
                return false
            }
            row = [9]uint8{}
            n = 0
        }
    }
    return true
}

//检查某一序列的数字是否合格
func CheckLine(line [9]uint8) bool {
    for _, v := range line {
        if v == 0 {
            return false
        }
    }
    state := [9]bool{}
    for _, v := range line {
        state[v-1] = true
    }
    for _, v := range state {
        if v == false {
            return false
        }
    }
    return true
}
func getx(x int) (n [3]int) {
    switch x {
    case 0, 1, 2:
        {
            n = [3]int{0, 1, 2}
            return
        }
    case 3, 4, 5:
        {
            n = [3]int{3, 4, 5}
            return
        }
    case 6, 7, 8:
        {
            n = [3]int{6, 7, 8}
            return
        }
    }
    return
}
func gety(y int) (n [3]int) {
    switch y {
    case 0, 1, 2:
        {
            n = [3]int{0, 1, 2}
            return
        }
    case 3, 4, 5:
        {
            n = [3]int{3, 4, 5}
            return
        }
    case 6, 7, 8:
        {
            n = [3]int{6, 7, 8}
            return
        }
    }
    return
}

//填充空格的可选数字列表
func (form *Form) FillOption() {
    form.ReBox()
    for i, vform := range form {
        for j, _ := range vform {
            if !form[i][j].Lock {
                form.GetOption(i, j)
            }
        }
    }
}

//获取某个空格的可选数字列表
func (form *Form) GetOption(x, y int) {
    state := [9]bool{}
    for i := 0; i < 9; i++ {
        //横向判断
        if form[x][i].Figure != 0 {
            state[form[x][i].Figure-1] = true
        }
        //竖向判断
        if form[i][y].Figure != 0 {
            state[form[i][y].Figure-1] = true
        }
    }
    nx := getx(x)
    ny := gety(y)
    for _, vx := range nx {
        for _, vy := range ny {
            if form[vx][vy].Figure != 0 {
                state[form[vx][vy].Figure-1] = true
            }
        }
    }
    n := 0
    for i, v := range state {
        if !v {
            form[x][y].Op = append(form[x][y].Op, i+1)
            n++
        }
    }
    form[x][y].nOp = n
}

func (form *Form) ReBox() {
    for j, vform := range form {
        for i, _ := range vform {
            if !form[i][j].Lock {
                form[i][j].Figure = 0
                form[i][j].nOp = 0
                l := len(form[i][j].Op)
                //删除form[i][j].State.Option切片中的所有元素
                form[i][j].Op = append(form[i][j].Op[:0], form[i][j].Op[l:]...)
            }
        }
    }
}
func (form *Form) Getmin() (x, y int) {
    init := false
    for i, vform := range form {
        for j, _ := range vform {
            if form[i][j].Figure == 0 {
                if !init {
                    x, y = i, j
                    init = true
                }
                if form[i][j].nOp < form[x][y].nOp {
                    x, y = i, j
                }
            }
        }
    }
    return
}
func (form *Form) End() bool {
    for _, vform := range form {
        for _, v := range vform {
            if v.Figure == 0 {
                return false
            }
        }
    }
    return true
}

//递归求值
func (form *Form) Answer() bool {
    form.FillOption()
    x, y := form.Getmin()
    var vop []int
    vop = append(vop, form[x][y].Op...)
    for _, v := range vop {
        form[x][y].Figure = uint8(v)
        form[x][y].Lock = true
        if !form.End() {
            if form.Answer() {
                return true
            } else {
                form[x][y].Lock = false
                Num++
            }
        } else {
            fmt.Println("结束")
            if form.CheckAll() {
                return true
            }
        }
    }
    return false
}

//打印结果
func (form *Form) Print() {
    for _, vform := range form {
        for _, v := range vform {
            fmt.Print(v.Figure, "  ")
        }
        fmt.Println("")
    }
    fmt.Println("")
}

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

4286 次点击  
加入收藏 微博
1 回复  |  直到 2013-05-02 15:47:29
lovegolang
lovegolang · #1 · 12年之前

没玩过数独……

添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传