Python编写的数独求解程序

jerryxjr1220 · 发表于 2016-9-30 06:42:44

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 jerryxjr1220 于 2017-2-7 10:09 编辑

程序构思是穷举所有可能性，然后选择选项最少的进行依次尝试，以提高成功率。
基本上一个简单的数独在0.5s以内，中等难度的1s以内，困难的2s内完成。
不过，本程序对无解的数独求解可能会出错，因为我没考虑无解的情况，这个可以有待优化。
原始数独：
[0,0,8,0,0,0,2,0,0],
[0,3,0,8,0,2,0,6,0],
[7,0,0,0,9,0,0,0,5],
[0,5,0,0,0,0,0,1,0],
[0,0,4,0,0,0,6,0,0],
[0,2,0,0,0,0,0,7,0],
[4,0,0,0,8,0,0,0,6],
[0,7,0,1,0,3,0,9,0],
[0,0,1,0,0,0,8,0,0]

输出：
[6, 1, 8, 7, 3, 5, 2, 4, 9]
[5, 3, 9, 8, 4, 2, 7, 6, 1]
[7, 4, 2, 6, 9, 1, 3, 8, 5]
[3, 5, 7, 4, 2, 6, 9, 1, 8]
[1, 8, 4, 5, 7, 9, 6, 2, 3]
[9, 2, 6, 3, 1, 8, 5, 7, 4]
[4, 9, 3, 2, 8, 7, 1, 5, 6]
[8, 7, 5, 1, 6, 3, 4, 9, 2]
[2, 6, 1, 9, 5, 4, 8, 3, 7]

游客，如果您要查看本帖隐藏内容请回复

pinro · 发表于 2016-9-30 08:30:16

数独爱好者进来学习一下

pinro · 发表于 2016-9-30 09:27:03

看不大懂啊
请问一下
原理是不是把空位所有可能的值都列出来
然后只剩一种可能的空位就填上去

jerryxjr1220 · 发表于 2016-9-30 12:08:14

原理是把空位的所有可能值列出来，然后依次去用可能值尝试，正确就尝试下一个空位，错误就尝试下一个可能值。直到所有可能值都尝试完就结束，但是我没有考虑无解的情况～

天外飞mao · 发表于 2016-9-30 14:14:35

厉害了我的哥

jerryxjr1220 · 发表于 2016-9-30 20:57:51

考虑了一下，可能多解的情况也没考虑到~

lb971216008 · 发表于 2016-10-2 11:02:59

我也喜欢数独

dh89 · 发表于 2016-11-16 15:14:13

学习下

会抓贼的老托比 · 发表于 2016-11-16 16:14:37

数独小时候玩过

薇薇 · 发表于 2016-11-16 22:19:30

bhsx · 发表于 2016-11-17 08:56:44

大头鱼 · 发表于 2016-12-18 22:09:41

有事

zhihaoyu · 发表于 2016-12-24 15:47:39

学习学习

yuan2016 · 发表于 2016-12-26 12:25:18

gopythoner · 发表于 2017-4-14 21:51:53

厉害了

lsy19810210 · 发表于 2017-4-15 09:13:17

学习

小锟 · 发表于 2017-4-15 09:17:20

本帖最后由小锟于 2017-4-15 09:18 编辑

import itertools as t

a = range(1,10)
s = 0
    
def search(shuduliebiao):
    global a
    b = []
    for each in shuduliebiao :
        if each in a:
            seat = shuduliebiao.index(each)
            b.append(seat)
    return b

shuduliebiao = [0,0,8,0,0,0,2,0,0]
b = search(shuduliebiao)

length = len(b)

aims = t.permutations(a,9)
for aim in aims:
    aim = list(aim)
    for every in b:
        if aim[every] == shuduliebiao[every]:
            s+=1
            
        if s == length:
            print aim
    s = 0

错误的情况有什么情况，感觉九个格子的数独应该没什么什么错误的

抱歉，看了你的答案，我感觉自己理解错了
不好意思，膜拜大神

源稚空 · 发表于 2017-4-17 09:43:27

xpb · 发表于 2017-4-17 17:36:39

这个程序好！！！！！！！

过期的牛奶 · 发表于 2017-4-18 19:11:57

厉害呀，来学习一下！

账号		自动登录	找回密码
密码			立即注册

[作品展示] Python编写的数独求解程序

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐: