智星论坛(IQSTAR BBS)
 
打印

数独算法

添加一版本,会做简单的试探:

ty6W5cNo.zip (19.47 KB)

[此贴子已经被作者于2006-3-7 16:31:11编辑过]


附件

lR7p7HrA.zip (18.55 KB)

2006-3-7 16:16, 下载次数: 22

数独算法

vxz0JBjL.zip (18.55 KB)

2006-3-7 16:17, 下载次数: 15

数独算法

fKFQCVOc.zip (19.47 KB)

2006-3-7 16:23, 下载次数: 15

0.54364331210052407755147385529445

TOP

请问对于每一个数独都能用不.
小楼昨夜听雨声, 竹兰幽幽入梦来。

TOP

引用:
以下是引用[I]楼 兰[/I]在2006-3-7 16:26:21的发言:[BR]请问对于每一个数独都能用不.
发现昨天的程序里面有个Bug,修正过来了.
对于一般的题目都应该可以求解,但是不能保证一定可以解出来.
主要问题在于这里力求用推理的方法,不然通过穷举的方法总是可以解出来的.
rSONv74W.zip (19.47 KB)
0.54364331210052407755147385529445

TOP

最后一个版本,带上c源代码了,(不过源代码可读性很差[em04] )
增加了允许的试探的次数,并且将输出弄得更加可读一些:
[attach]4505[/attach]

[此贴子已经被作者于2006-3-8 13:03:50编辑过]


附件

hEtGgO8E.zip (22.5 KB)

2006-3-8 09:27, 下载次数: 23

数独算法

XwSWXtmn.zip (22.54 KB)

2006-3-8 09:51, 下载次数: 21

0.54364331210052407755147385529445

TOP

引用:
以下是引用[I]LIKEME[/I]在2006-3-6 8:43:57的发言:[BR]我一直认为,数独是不需要试探的(很多资料上也这样说)。
这个题目到这个地方的时,推理顺序是这样的:
1、右下格子的第一列2个空位只能是5或者6;
2、最下一行4个空位中只有第4列的空位可以填1;
3、第3行第5列填1;
4、第1行第7列(你标注的位置)填1。
后面略。
独立方程的话,类似上面推理的第一步应该是可以增加限制条件的。:)
如果不试探,下面的情况接下去该如何分析呢?
0.54364331210052407755147385529445

TOP

写了个程序,可以产生很多的数独游戏,都保证有且只有一个结果的。
可以有三种运行方式:
i)
shudu.exe
这个将随机产生一个数独游戏
ii)
shudu.exe s
其中s是任意一个数字,那么将产生一个固定的数独游戏。这个游戏由数字s唯一确定
iii)
shudu.exe s t
其中s,t是两个不同的整数,那么将产生一个固定的数独游戏。这个游戏由数字s,t唯一确定

比如
shudu.exe 2 3
将产生:
5|  |6|  |  |  |4|3|  |
  |  |  |5|  |  |  |  |  |
9|  |  |  |8|7|  |1|  |
  |  |2|  |  |  |  |  |  |
  |  |  |3|  |  |9|  |  |
  |  |8|  |  |  |  |  |1|
  |1|  |  |5|2|  |8|  |
6|  |  |  |  |9|  |  |7|
8|  |9|  |  |  |5|  |  |

hh1uAj7A.zip (19.48 KB)

[此贴子已经被作者于2006-3-12 8:58:03编辑过]


附件

4JLlYFsv.zip (19.48 KB)

2006-3-12 08:49, 下载次数: 11

数独算法

0.54364331210052407755147385529445

TOP

关于这个问题,可以提出下面两个基本问题?
Q1、对于9乘9的空白的表一共有多少种填法,(我们假定答案为n9)?
Q2、对于9乘9的情况,如果答案有唯一解,至少先要确定几个数?
对于Q1,可能的答案是:n9=6,670,903,752,021,072,936,960=9! * 72^2 * 2^7 * 27,704,267,971
上面这个结果在去年五月(或者是之前)就被报道,(请原谅我没有考证出处和作者),
其中最后一个因子是素数。求解的方法是先依据对称性,得到因子,(我猜测是:9! * 72^2),
然后蛮力(可能有某些优化手段)搜索,(猜测大约为单pc十小时的工作量)。
于是,我想大家可以讨论一些“简单”问题:
Q3、依据对称性,可以断定的,n9的因子是什么?(我想至少是9! * 72^2,朋友们能不能把它变大呢?)
Q4、对于其它(比如所16乘16的)的讨论。
Q5、对于已经有几个数的情况呢?
对于Q2,应该还是open的。富有经验的人可以做出18或19的情况,现在的纪录应该是17。
对于为什么应该没有证明,对于怎么做好像也没有定论。

TOP

http://www.sudoku.com/forums/viewtopic.php?t=44&postdays=0&postorder=asc&start=0&sid=2d3e9a9cf336f08ad78d36dea85b9141
不过我不认为这个结果是准确的
0.54364331210052407755147385529445

TOP

引用:
以下是引用[I]duz[/I]在2006-3-8 12:20:56的发言:
) 如果不试探,下面的情况接下去该如何分析呢?
第6行第2列、第6行第7列、第8行第2列、第8行第7列形成了“对称格子”,因此第6行第1列只能填6。

[此贴子已经被作者于2006-3-14 10:22:39编辑过]

于千万人之中,遇见你所遇见的人;于千万年之中,时间的无涯荒野里,没有早一步,也没有晚一步,刚巧赶上了

TOP

引用:
以下是引用[I]duz[/I]在2006-3-14 10:11:01的发言:[BR]http://www.sudoku.com/forums/viewtopic.php?t=44&postdays=0&postorder=asc&start=0&sid=2d3e9a9cf336f08ad78d36dea85b9141
不过我不认为这个结果是准确的
为什么呢?

TOP

当前时区 GMT+8, 现在时间是 2008-12-5 23:02

Processed in 0.065066 second(s), 9 queries, Gzip enabled.


Skin By Wing