主题:刚才看了MOZ解答的"一个大九宫格小九宫的游戏"的感想!
强强
[专家分:4740] 发布于 2007-02-21 18:50:00
同题目,我心里的想法只有一个字加十个符号:"强!!!!!!!!!!"希望大家都看看,如果哪位高手从中看出MOZ的算法,别忘了给我讲讲.
回复列表 (共23个回复)
11 楼
moz [专家分:37620] 发布于 2007-02-22 17:11:00
我开始有点精神错乱了,头痛得很.
我先把当初的想法说一下,晚上回家再把源代码发给你看看,
希望能给你带来点什么启示也好.
1. a$(0)是原来的横向顺序,每九个字符就是一行
2. a$(1)是阵列的竖向顺序,每九个字符就是一列
3. a$(2)是阵列的小方块,每九个字符就是一个小九宫
4. l( )数组是记录空位的位置的, l(0)是空位的总数
这是第一段 for 循环的作用
第二段循环是用 b$( ) 来记录以上三个排列形式当中每个小组缺的数字
比如说第二行是85723,缺的是1469,所以结果是b$(0,2)="1469"
(拿到源代码后,你运行一下,就知道是怎么一回事了)
b$( ) 第一维数字跟 a$( ) 的维数相对应 0横向 1纵向 2小方格
b$( ) 第二维数字是对应的某个小组(行,列,方格)
b$( ) 字符串的内容是所缺的数字
l(0)是空位的总数,也就是说缺l(0)个数字,c$是最终答案,长度为l(0).
第三段是主要计算过程:
1. 九方阵81个位置 - 已有33个数字 = 还缺 48 个数字,
2. 循环从 c$ 的第 1 个位置 to 第 48 个位置
3. 某一个位置 j ,首先确定它在各个排列形态(横/竖/方)里的哪一小组(行/列/格)
也就是 i0 , i1 , i2
4. 先从这三个小组里面找一个相同的数字出来,(符合题目要求,三种方式不重复)
4.1 找到有相同的数字,从三个 b$( ) 中拿出来,填到目标 c$ 去,然后下一位
4.2 找不到有相同的数字了,返回到上一位.(相当于递归的概念)
4.2.1 确定位置后,从 c$ 中把数字拿出来, 还给三个 b$( ) 去,
再从三个小组里找比之前已经找到了的数字大的下一个相同数字出来.
( 继续 4.1 循环)
5. 找啊找,
找到了:下一位,
找不到:上一位.
6. 48个字符( c$ 的长度 )都找齐了,这就是答案了
最后一段是显示结果的东西.原来留空的地方黄色显示.
程序中的一个 instchr$( ) 函数的目的是想要加快搜查速度的,
现在看来那么短的字符串,没有用这个函数了,回去把它删掉.
调试程序里加了一个按键暂停,用来追踪变量状态的,按一下执行一圈.
第一行是 c$ 的内容,逐位添加
按下来是三个 b$( ) 小组,标志着每个分组缺的数字
最后是 a$(0) , 只是拿来看看有没有做错的地方的.
相信加上显示的调试会让你明白箇中的过程.
12 楼
强强 [专家分:4740] 发布于 2007-02-22 17:43:00
OH,MY GOD 。谢谢了,不过我得好好消化消化
13 楼
moz [专家分:37620] 发布于 2007-02-22 18:51:00
instchr$( ) 函数执行的是还数功能,所以还是不能去掉,
源代码如下,等你看完看明白以后再说说,看这是不是小学生的方法?
declare sub printa(p$)
declare function sames$(x1$,x2$,x3$,x4$)
declare function instchr%(y1$,y2$)
defint a-z
dim b$(2,9),a$(2),l(81)
a$(0)=" 8 5723 7 21 6 4 1 4 89 9 5 4 43 8 1 2 3 57 4 1764 8 8"
a$(1)=a$(0)
a$(2)=a$(0)
for i=1 to 81
i1=((i-1)mod 9)*9+(i-1)\9+1
i2=(((i-1)\27)*3+((i-1)mod 9)\3)*9+((i-1)\9 mod 3)*3+(i-1)mod 3+1
i0$=mid$(a$(0),i,1)
mid$(a$(1),i1,1)=i0$
mid$(a$(2),i2,1)=i0$
if i0$=chr$(32)then
l(0)=l(0)+1
l(l(0))=i
end if
next
for i=1 to 9
for j=1 to 9
for k=0 to 2
if instr(mid$(a$(k),i*9-8,9),chr$(48+j))=0 then b$(k,i)=b$(k,i)+chr$(48+j)
next k,j,i
c$=space$(l(0))
for j=1 to l(0)
cls
print c$
for i=1 to 9:print b$(0,i),b$(1,i),b$(2,i),"=":next
printa a$(0)
i=l(j)
i0=(i-1)\9+1
i1=(i-1)mod 9+1
i2=((i-1)\27)*3+((i-1)mod 9)\3+1
mid$(c$,j,1)=sames$(b$(0,i0),b$(1,i1),b$(2,i2),mid$(c$,j,1))
print i0;i1;i2;"==";mid$(c$,j,1),"Press any Key to continue....."
if mid$(c$,j,1)=chr$(32)then j=j-2
zz$=input$(1)
next
cls
k=0
for i=1 to 81
d$=mid$(a$(0),i,1)
if d$=chr$(32)then
k=k+1
color 14,0
print mid$(c$,k,1);chr$(32);
else
color 7,0
print d$;chr$(32);
end if
if i mod 9=0 then print
next
end
function instchr(y1$,y2$)
for i=1 to len(y1$)
if y2$<mid$(y1$,i,1)then exit for
next
y1$=left$(y1$,i-1)+y2$+mid$(y1$,i)
instchr=i
end function
sub printa(p$)
for i=1 to len(p$)
print mid$(p$,i,1);
if i mod 9=0 then print
next
end sub
function sames$(x1$,x2$,x3$,x4$)
sames$=chr$(32)
if x4$<>chr$(32)then
i=instchr(x3$,x4$)
i=instchr(x2$,x4$)
i=instchr(x1$,x4$)
end if
for j1=i+1 to len(x1$)
k$=mid$(x1$,j1,1)
j2=instr(x2$,k$)
j3=instr(x3$,k$)
if j2>0 and j3>0 then
x1$=left$(x1$,j1-1)+mid$(x1$,j1+1)
x2$=left$(x2$,j2-1)+mid$(x2$,j2+1)
x3$=left$(x3$,j3-1)+mid$(x3$,j3+1)
sames$=k$
exit for
end if
next
end function
14 楼
xgf0 [专家分:60] 发布于 2007-02-22 20:18:00
看你们的对话好好笑,写程序还能追女孩子!我说老师为什么天天都说学程序用处很大呢,原来如此呀!! 我一定好好学!!!为了女孩子,加油!!加油站 [em5][em5][em5]
15 楼
xgf0 [专家分:60] 发布于 2007-02-22 20:24:00
看你们的对话真好笑,写程序还能追女孩子,我说老师怎么天天都说学程序用处大呢,原来老师都是过来人了。我以后学习可有动力了!!!em5][em5][em5]
16 楼
强强 [专家分:4740] 发布于 2007-02-22 20:42:00
研究ING……
17 楼
rickone [专家分:15390] 发布于 2007-02-22 21:38:00
FW现在在哪混?
我现在更想做的是,用推理解数独,因为数独这个游戏是要求解是唯一的,初盘唯一决定终盘,所以从理论上每个位置上的数是可以唯一确定下来的。也就是说跟人工解是一样的,我主张不用测试法,完全靠推理,这个游戏才好玩。
现在这方面的技术外文资料多,叫Sudoku solving technique,中文的推荐sd9981.com这个网站,翻译了一些技术帖。
18 楼
强强 [专家分:4740] 发布于 2007-02-22 22:46:00
哎,太麻烦,头都大了,给我逼急了就只能使用暴力的了。我也不管什么运行效率了,哎,不知道死了多少脑细胞!
19 楼
moz [专家分:37620] 发布于 2007-02-23 02:39:00
去看了一下老ONE给的网站,觉得也没有什么.
你说到推理,于是我便想到每一个位置都加上限制去试试,
结果试不出来,因为每次都马上出结果了,没法比较.
你说的推理跟测试其实是同一个道理,
只不过你推理的过程中,很有可能只是凭感觉,
属于一种漫无目的的没有方向感的随意去挑一个来先试试看行不行的,
好运的给你撞上了,不好运的你还得去找第二个位置,
很有可能重复了你还不知道.
跟电脑里按顺序的测试(也就相当于遍历)是同样的差别,
电脑更准确,不会遗漏,不会重复.比人稳定多了.属于理性动物(相对于人的感性而言)
反而跟人家说的树的概念可能相关(不过我不懂,我看了很多资料,反正就是无法理解)
(是不是你说的?),先挑选出口少的(马位/分枝)先跳.会比较快得出结果.
不过我对这个问题研究了很久,我没有办法找得到条件来判断何为出口少,
(我怎么能知道哪个出口比较少呢?)
20 楼
rickone [专家分:15390] 发布于 2007-02-24 01:05:00
你可能没明白我的意思,解一个9*9的数独,不管是刚搜,还是剪枝,都是一下出结果,不可能慢到一秒钟那么长时间的,不像马遍历,数独的最基本的规则本身就是非常强的剪枝条件。
基于推理的,不是搜索的,数独的定义里有一条,最终结果是唯一的,就是说空格内的数都是唯一的,基于推理的程序是按照逻辑计算的,它要是往哪个格里填个数的话说明它已经确定了这个位置,就是说它不是在猜,不是在搜索。做这样的程序的目的是对数独进行难度测试,比如基于直观法的推理程序,如果仅使用这一方法就可以解一个数独,就可以认为相当简单,再加一些方法才能解的就难一些。
玩数独有两种乐趣,一是解数独,二是寻找解数独的方法。
我来回复