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

gs272 · · 3683 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

下面是我写的解数独的代码,呵呵,水平有限,比较乱,但感觉解题还是比较快的,代码中的那个题号称史上最难的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

3683 次点击  
加入收藏 微博
1 回复  |  直到 2013-05-02 15:47:29
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传