黑松山资源网 Design By www.paidiu.com
偶然发现linux系统附带的一个数独游戏,打开玩了几把。无奈是个数独菜鸟,以前没玩过,根本就走不出几步就一团浆糊了。
于是就打算借助计算机的强大运算力来暴力解数独,还是很有乐趣的。
下面就记录一下我写解数独程序的一些思路和心得。
一.数独游戏的基本解决方法
编程笼统的来说,就是个方法论。不论什么程序,都必须将问题的解决过程分解成计算机可以实现的若干个简单方法。俗话说,大道至简。对于只能明白0和1的计算机来说,就更需要细分步骤,一步一步的解决问题了。
首先来思考一下解数独的基本概念。
数独横九竖九共八十一个格子,同时又分为9个九宫格。规则很简单——需要每一个格中的数字,都保证与其所在横排和竖排以及九宫格内无相同数字。
所以我们的大概思路就是,从第一个空格开始试着填数,从 1 开始填,如果 1 不满足横排竖排九宫格无重复的话,就再填入 2 ,以此类推,直到填入一个暂时满足规则的数,中断此格,移动到下一个空格重复这个过程。
如果到达某个空格发现已经无数可选了,说明前面某一格填错了,那就返回上一格,从上一格的中断处继续往 9 尝试,直到这样回朔到填错的那一格。
这样的话,我们就可以整理出重要的步骤了:
将空格用 0 表示,同时将数独表示成嵌套的列表,这样每格的行数和列数就正好是列表中每个对应数的索引。
程序如下:
#coding=utf-8 import datetime class solution(object): def __init__(self,board): self.b = board self.t = 0 def check(self,x,y,value):#检查每行每列及每宫是否有相同项 for row_item in self.b[x]: if row_item == value: return False for row_all in self.b: if row_all[y] == value: return False row,col=x/3*3,y/3*3 row3col3=self.b[row][col:col+3]+self.b[row+1][col:col+3]+self.b[row+2][col:col+3] for row3col3_item in row3col3: if row3col3_item == value: return False return True def get_next(self,x,y):#得到下一个未填项 for next_soulu in range(y+1,9): if self.b[x][next_soulu] == 0: return x,next_soulu for row_n in range(x+1,9): for col_n in range(0,9): if self.b[row_n][col_n] == 0: return row_n,col_n return -1,-1 #若无下一个未填项,返回-1 def try_it(self,x,y):#主循环 if self.b[x][y] == 0: for i in range(1,10):#从1到9尝试 self.t+=1 if self.check(x,y,i):#符合 行列宫均无条件 的 self.b[x][y]=i #将符合条件的填入0格 next_x,next_y=self.get_next(x,y)#得到下一个0格 if next_x == -1: #如果无下一个0格 return True #返回True else: #如果有下一个0格,递归判断下一个0格直到填满数独 end=self.try_it(next_x,next_y) if not end: #在递归过程中存在不符合条件的,即 使try_it函数返回None的项 self.b[x][y] = 0 #回朔到上一层继续 else: return True def start(self): begin = datetime.datetime.now() if self.b[0][0] == 0: self.try_it(0,0) else: x,y=self.get_next(0,0) self.try_it(x,y) for i in self.b: print i end = datetime.datetime.now() print '\ncost time:', end - begin print 'times:',self.t return s=solution([[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,8,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]]) 73 s.start()
值得注意的是使用的递归判断能够很巧妙的在走错分支时回朔到上一层。具体实现是通过 for 循环来从 1 到 9 不断填入数字同时达到记录中断点的作用。通过下一层的返回值来确定是否回朔。
程序输出如下:
[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] cost time: 0:00:00.060687 times: 45360
可以看到程序虽然运算次数比较多,但是速度还是很快的。
黑松山资源网 Design By www.paidiu.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
黑松山资源网 Design By www.paidiu.com
暂无评论...
更新日志
2024年10月09日
2024年10月09日
- 【原神】V5.0攻略 | 林尼攻略一图流
- 李翊君.1993-相思的烈酒【上华】【WAV+CUE】
- 古巨基.1998-LEO.KU(国)【千禧年代】【WAV+CUE】
- 郭子.2001-原来你什么都不想要创作集丫滚石】【WAV+CUE】
- 《使命召唤:黑色行动6》新预告公布!10月25日发售
- Atlus《暗喻幻想》媒体评分汇总:高分好评如潮!
- 2024金摇杆奖提名揭晓 《黑神话》角逐最佳视觉设计!
- 群星《新说唱2024 第3期 (上)》[320K/MP3][32.76MB]
- 群星《新说唱2024 第3期 (上)》[FLAC/分轨][95.38MB]
- 群星《新说唱2024 第3期 (下)》[320K/MP3][31.36MB]
- 幻兽帕鲁手游什么时候正式上线 最新消息一览
- 西普大陆BOSS位置盘点 解锁天启纪元玩法
- 西普大陆精灵进阶培养攻略 精灵养成指南
- dnf手游法控法系职业哪个强 dnf手游法控法系职业强度排行
- 魔兽世界血藤护目镜图纸在哪买 wlk血藤护目镜图纸购买位置介绍