go编程解数独

没玩过数独……

不好意思，写错了，应该是下面的
007000001
900000628
602000590
000081005
070503000
090060070
000005000
200040086
040030000

还是贴代码吧，真看不懂

呵呵，我已经找到问题所在了，解决了，等我把代码整理下就贴出来！

贴代码了，呵呵，水平有限，比较乱，但有个问题，我这个程序只能读出一组答案，怎么才能读出成立的所有答案啊！

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("")
}

已读取数独题：

8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

结束 成功解答，共计算了 10041 次！ 8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

未修改源码

能说下你期望的结果吗？

800000000000000000000000000000000000000000000000000000000000000000000000000000000

假如数独题如上，那肯定不止一种结果，我期望的是能得出所有成立的结果！

我用C语言写的解得挺快的(go正在学习中)。我接的结果是这样，需要的话我可以把代码贴出来:

             RESULT SUDOKU

*****************************************************

+-----------------+-----------------+-----------------+

| --- --- --- | --- --- --- | --- --- --- |

| | 5 | 8 | 7 | | | 9 | 2 | 6 | | | 4 | 3 | 1 | |

| --- --- --- | --- --- --- | --- --- --- |

| | 9 | 1 | 4 | | | 3 | 5 | 7 | | | 6 | 2 | 8 | |

| --- --- --- | --- --- --- | --- --- --- |

| | 6 | 3 | 2 | | | 8 | 1 | 4 | | | 5 | 9 | 7 | |

| --- --- --- | --- --- --- | --- --- --- |

+-----------------+-----------------+-----------------+

| --- --- --- | --- --- --- | --- --- --- |

| | 3 | 2 | 6 | | | 7 | 8 | 1 | | | 9 | 4 | 5 | |

| --- --- --- | --- --- --- | --- --- --- |

| | 4 | 7 | 8 | | | 5 | 9 | 3 | | | 1 | 6 | 2 | |

| --- --- --- | --- --- --- | --- --- --- |

| | 1 | 9 | 5 | | | 4 | 6 | 2 | | | 8 | 7 | 3 | |

| --- --- --- | --- --- --- | --- --- --- |

+-----------------+-----------------+-----------------+

| --- --- --- | --- --- --- | --- --- --- |

| | 8 | 6 | 9 | | | 2 | 7 | 5 | | | 3 | 1 | 4 | |

| --- --- --- | --- --- --- | --- --- --- |

| | 2 | 5 | 3 | | | 1 | 4 | 9 | | | 7 | 8 | 6 | |

| --- --- --- | --- --- --- | --- --- --- |

| | 7 | 4 | 1 | | | 6 | 3 | 8 | | | 2 | 5 | 9 | |

| --- --- --- | --- --- --- | --- --- --- |

+-----------------+-----------------+-----------------+

             GAME OVER

（本来在输出的格式还挺整齐的，粘到这里好像变形了）

我的意思是怎么输出所有正确的结果！ 比如800000000000000000000000000000000000000000000000000000000000000000000000000000000 这个求解，最终结果肯定不只一种，怎么输出所有可能的结果。

需要一个思路

你有没有写过八后同盘的‘树结构查找’算法，和那个差不多

1. 定义一个点的结构体 type point struct{ x int; y int };

   2.定义一个 长度为81的‘point’数组 记录填写的顺序;

   将这个数组表示依次填写81个方格内容的顺序，对比如：800000....可以是[0,0][0,1],[0,2]...[8,8]，  080000000...0可以是[0,1],[0,0],[0,2][0,3]...[8,8]
   

   3.定义一个二维数组 area[int][int] 该数组记录“按照以上填写顺序每个格里可以填写的数值”

    这个数组里的值是随着求解的过程变化的 比如 如果 方格sudo[i][j]里 1,3,4,5,9 和几个数据都被占据 那么area[i][j] 的
   

   值就应该是val = (1<<1) | (1<<3) | (1<<4) | (1<<5) | (1<<9) , 当填写到sudo[i][j]时 判断X(x>0&&x<10) 是否可以填写

   可用表达式 (X | val != val) 来判断,如果为真表示可以填写

   4.开始探索式求解 定义滚动变量 current := 0; 定义求解深度变量用来 表示已填写的个数 depth := initDepth; (初始化时的个数);

for{

      switch{

             case 向前:
                          if 当前填写深度 大于81 /*表示找到一个解*/ ，{
                                      记录结果,循环转入 ‘case 向后’；
                           } else {
                                           1,计算下一个填写方格的'可填写值'即 area[x][y] , 2.深度加1 ，3.进入'case 向下'
                          }
             case 向后:
                          if 当前深度小于初始深度 {
                                    求解完成
                          } else {
                                    1, 深度减1,  2.返回到填写前一格的状态，3.转入'case 向下'
                          }
             case 向下:
                         1.滚动变量 current++;
                         if current > 9 {
                                  current = 0
                                  转入'case 向后'
                          } else  {
                                    if  current 可填写入当前  {  
                                             填写并转入'case 向前'
                                    } else {
                                              继续循环'case 向下'
                                    }
                          }

       }

   if depth < initDepth {
         结束
    }

}

   /////////////////////////////////////////////////////////////

可能我描述的不够准确，有空我把 C语言的程序改成golang的粘出来，如果你想要 C语言 的我可以发给你

你有没有写过八后同盘的‘树结构查找’算法，和那个差不多

1. 定义一个点的结构体 type point struct{ x int; y int };

   2.定义一个 长度为81的‘point’数组 记录填写的顺序;

   将这个数组表示依次填写81个方格内容的顺序，对比如：800000....可以是[0,0][0,1],[0,2]...[8,8]，  080000000...0可以是[0,1],[0,0],[0,2][0,3]...[8,8]
   

   3.定义一个二维数组 area[int][int] 该数组记录“按照以上填写顺序每个格里可以填写的数值”

    这个数组里的值是随着求解的过程变化的 比如 如果 方格sudo[i][j]里 1,3,4,5,9 和几个数据都被占据 那么area[i][j] 的
   

   值就应该是val = (1<<1) | (1<<3) | (1<<4) | (1<<5) | (1<<9) , 当填写到sudo[i][j]时 判断X(x>0&&x<10) 是否可以填写

   可用表达式 (X | val != val) 来判断,如果为真表示可以填写

   4.开始探索式求解 定义滚动变量 current := 0; 定义求解深度变量用来 表示已填写的个数 depth := initDepth; (初始化时的个数);

for{

      switch{

             case 向前:
                          if 当前填写深度 大于81 /*表示找到一个解*/ ，{
                                      记录结果,循环转入 ‘case 向后’；
                           } else {
                                           1,计算下一个填写方格的'可填写值'即 area[x][y] , 2.深度加1 ，3.进入'case 向下'
                          }
             case 向后:
                          if 当前深度小于初始深度 {
                                    求解完成
                          } else {
                                    1, 深度减1,  2.返回到填写前一格的状态，3.转入'case 向下'
                          }
             case 向下:
                         1.滚动变量 current++;
                         if current > 9 {
                                  current = 0
                                  转入'case 向后'
                          } else  {
                                    if  current 可填写入当前  {  
                                             填写并转入'case 向前'
                                    } else {
                                              继续循环'case 向下'
                                    }
                          }

       }

   if depth < initDepth {
         结束
    }

}

   /////////////////////////////////////////////////////////////

可能我描述的不够准确，有空我把 C语言的程序改成golang的粘出来，如果你想要 C语言 的我可以发给你

另外 ，你的代码怎么贴的那么漂亮

<p>//你看看是不是要这样的效果，可以求所有的解</p>

<p>package main</p>

<p>import "fmt"</p>

<p>const (</p> N = 9 <p>)</p>

<p>type point struct{</p>

<pre><code>x int

y int </code></pre>

<p>}</p>

<p>type line [N]int</p>

<p>type area [N]line</p>

<p>func (s *area) show(){</p>

<pre><code>fmt.Println("---------------")

for i:=0;i&lt;N;i++ { for j:=0;j&lt;N;j++ { fmt.Print(s[i][j]) } fmt.Print("\n") } </code></pre>

<p>}</p>

<p>func main(){</p>

<pre><code>fmt.Println("")

var ( i int j int start int step int total int current point ) var sudoku area = area{ / {0,0,7,0,0,0,0,0,1}, {9,0,0,0,0,0,6,2,8}, {6,0,2,0,0,0,5,9,0}, {0,0,0,0,8,1,0,0,5}, {0,7,0,5,0,3,0,0,0}, {0,9,0,0,6,0,0,7,0}, {0,0,0,0,0,5,0,0,0}, {2,0,0,0,4,0,0,8,6}, {0,4,0,0,3,0,0,0,0}, /// {0,0,0,0,0,0,0,0,1}, {9,0,0,0,0,0,6,2,8}, {6,0,2,0,0,0,5,9,0}, {0,0,0,0,8,1,0,0,5}, {0,7,0,5,0,3,0,0,0}, {0,9,0,0,6,0,0,7,0}, {0,0,0,0,0,5,0,0,0}, {2,0,0,0,4,0,0,8,6}, {0,4,0,0,3,0,0,0,0}, } var limit area = area{} var route [NN]point = [NN]point{}

sdk := sudoku[:] i = 0 j = 0 route[0].x, route[0].y = i, j

var cover func([]line,point) int = func(sudo []line,p point) int {

var (
    x   int
    y   int
    i   int
    j   int
    result  int
)
result = 0

for i,j = p.x,0; j<N; j++ {
    if p.y != j {
        result = result|(1<<uint(sudo[i][j]))
    }
}
for i,j = 0,p.y; i<N; i++ {
    if p.x != i {
        result = result|(1<<uint(sudo[i][j]))
    }
}
x,y = (p.x/3)*3,(p.y/3)*3
for i=0;i<3;i++ {
    for j=0;j<3;j++ {
        if p.x != i && p.y != j {
            result = result|(1<<uint(sudo[x+i][y+j]))
        }
    }
}

return result

}

// 确定填写路线 step,start = 0,0 for i=0; i&lt;N; i++ { for j=0; j&lt;N; j++{ if sudoku[i][j] &gt; 0 { route[step].x,route[step].y = i,j step++ } } } start = step for i=0; i&lt;N; i++ { for j=0; j&lt;N; j++{ if !(sudoku[i][j] &gt; 0) { route[step].x,route[step].y = i,j step++ } } }

//for _,a := range route { //fmt.Print(a) //}

// 初始化求解参数 current = route[start] limit[current.x][current.y] = cover(sdk,current) flag := '+' temp := sudoku[current.x][current.y] depth := start total = 0 for{ //fmt.Printf("%c,%d",flag,depth) switch flag {

    case '>':
        if depth >= N*N {
            sudoku.show()
            depth--
            flag = '<'
            total++
        }else{
            temp = 0
            current = route[depth]
            limit[current.x][current.y] = cover(sdk,current)
            flag = '+'
        }
        break
    case '<':
        if depth < start {
            break
        } else {
            current = route[depth]
            flag = '+'
            temp = sudoku[current.x][current.y]
        }
    default:
        temp++
        if temp > N {
            flag = '<'
            sudoku[current.x][current.y] = 0
            depth--
        }else if (1<<uint(temp)|limit[current.x][current.y]) != limit[current.x][current.y] {
            flag = '>'
            sudoku[current.x][current.y] = temp
            depth++
        }

}

if depth < start { // 查找完毕
    break
}

}

fmt.Println("------------------OVER--------------------") fmt.Println("total:",total) </code></pre>

<p>}</p>

代码沾上去全乱了 ， 你是怎么弄上去的

代码沾上去全乱了 ， 你是怎么弄上去的 （建议将上面乱的删掉）

gist.github.com

15楼整解代码我放在这里了

非常感谢！我好好研究先！