Chinaunix首页 | 论坛 | 博客

-

  • 博客访问: 4155439
  • 博文数量: 172
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1923
  • 用 户 组: 普通用户
  • 注册时间: 2018-12-20 14:57
文章分类
文章存档

2021年(19)

2020年(81)

2019年(68)

2018年(4)

我的朋友

分类: 敏捷开发

2019-04-23 10:33:29

数独是一种老少皆宜的数学游戏,大家用零散的时间就可以玩上几局数独,有助于人们缓解压力,培养观察力和耐力,锻炼大脑。

数独游戏的规则也很简单,只需一支铅笔就能游戏,如:

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

9*9的格子中,已经填入了一些数,你所要做的就是把其余的格子中全部填入1~9的数,使得每一横行,每一竖行,以及粗线所包围的9个九宫格中,1~9这些数字全部只出现一次。

其实,如果用集算器的话,任何一局数独谜题都能随手解决。

首先,把数独问题记录入一个文本文件sudoku01.txt

 

007000008

840000600

000895300

010400003

000000070

900500024

204006000

080730010

130904700

 

为了排列整齐,其中空白的格子用0代替。解决问题的代码如下:

  A B C D
1 =file("sudoku01.txt") =A1.import@si() =B1.(~.split@p()) =C1.conj()
2 [] >func(A3,D1,1) =A2(1) =create(A,B,C,D,E,F,G,H,I).record(C2)
3 func   =ceil(B3/9) =(B3-1)%9+1
4   if A3(B3)!=0 if B3==81 >A2=A2|[A3.to()]
5     else >func(A3,A3,B3+1)
6     return  
7   =A3.to(C3*9-8,C3*9) =A3.step(9,D3)  
8   =ceil(C3/3)*3 =ceil(D3/3)*3 =(k=B8*9+C8-9,A3.m(k-20:k-18,k-11:k-9,k-2:k))
9   =to(9)\B7\C7\D8    
10   for B9 >A3(B3)=B10  
11     if B3==81 >A2=A2|[A3.to()]
12     else >func(A3,A3,B3+1)
13   >A3(B3)=0    

下面,详细分析一下这段代码。

B1中将文本文件逐行读入,构成一个序列:

C1中将每一行中各个格子的值拆开,使得每一行都构成一个序列:

D1中将各个格子的值顺次连接为一个序列,以便于计算:

再来看A3中的子程序,执行时,将已填入部分数据的数独格值序列作为参数复制在A3中,将当前正在填写的格子序号复制在B3中。C3D3根据格子序号计算出格子所在的行和列。

在第46行中,判断当前的格子中是否已经被填入了数,如果已经执行到了最后一个格子(第81个),说明谜题已经解开,将答案记录在A2的序列中;如果未执行到最后,则递归调用A3中的子程序,继续填写下一个格子。

在第7~13行,则是当前格子中为0时的处理,此时需要尝试填入数值。在A7中列出同一行的数构成的序列,B7中列出同一列的数构成的序列,D8中列出所在九宫格的数构成的序列。由于当前格子不能和同一行、同一列或者同一九宫格中已有的数相同,所以在B9中通过序列运算集合求差,计算出当前格子可能填入的所有数。

10~12行,在当前格中尝试填入每一个允许的数,如果填到了最后一个格子,说明问题解决,把答案记录在A2中;否则递归调用A3中的子程序,继续填写下一个格子。

如果B9中的所有结果都已经尝试过,则在第13行中把当前格中的数恢复为0,继续修改前面格子中的数。

 

在主程序的B2中,调用A3中的子程序,从第一个格子开始,尝试填数。执行后,即可在A2中看到执行结果:

对于普通的数独问题,A2中只会有1个解,如果数独题目存在问题,也可能出现无解或者多个解的情况。为了便于查看,在D2中,将得到的第1个解填入序表,得到的解答如下:

 

阅读(2719) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~