智游城

标题: 数学题 [打印本页]

作者: 老陈 时间: 2013-9-9 18:14
标题: 数学题
Sudoku挺好玩儿的。
9x9=81个格填满，很漂亮。
谁知道填满后的图形总共有多少种？

作者: 老陈 时间: 2013-9-11 13:05
昨天在赌场打牌，玩手机想出这个题目。原以为几个数乘一乘就能得到结果，实际不是这样，因为变化太多，最后结果应该是一个天文数字，这个数字现在我也没算出来，肯定超过2^64，因为我用计算机编程序计算，累加结果的无符号长整型的变量溢出，20分钟的运行得到这个结果。再想其它办法吧，真是自找麻烦。

作者: maomaobiao 时间: 2013-9-11 13:13

老陈发表于 2013-9-11 15:05
昨天在赌场打牌，玩手机想出这个题目。原以为几个数乘一乘就能得到结果，实际不是这样，因为变化太多，最后 ...

Sudoku is very very complicate, as well as addictive.

Be very careful to fool around with.

Given any one valid Sudoku puzzle that has one only solution, there is a program to solve it. This was achieved by Japanese (if I remember correctly).

However, there is no solution to "build" a random valid Sudoku puzzle so far. It is even more complicated than the solution itself.

作者: 老陈 时间: 2013-9-12 01:54
本帖最后由老陈于 2013-9-11 15:40 编辑

计算溢出的问题解决了，当变量的值大于10^18时，在这个变量里减去10^18，另一个变量加1，用两个变量表示累加结果，不过这样处理会降低效率。

再说计算思路：
为了叙述方便，我们把81个单元格的名字写成Crc形式，其中C是单元格的意思，r代表单元格所在的行，c代表单元格所在的列。

取一张空白表，C11有9种数字可填，C12有8种数字可填，
C13:7
C14:6
...
C19:1

C21:6
C22:5
C23:4
C31:3
C32:2
C33:1
C41:6

C24麻烦
当C14,C15,C16与C21,C22,C23都不同时C24有3种选择，有一个相同时有4种选择，有两个相同时有5种选择，有3个相同时有6种选择。用类似的办法找其它单元格的可填数字数，相乘再累加就得到基本图形集合的元素数：5,472,730,538。

每个图形第1到第3行可以互换，第4到第6，第7到第9也一样，列也一样，行列互换，旋转和翻转也可以。这样可以从基本图形中派生才更多图形。这些图形有重复，把它们去掉，得到结果如下：
6,670,903,752,021,072,936,960

结果有待于验证，我非常自信的是数量级肯定没问题。

作者: maomaobiao 时间: 2013-9-12 08:56

老陈发表于 2013-9-12 03:54
计算溢出的问题解决了，当变量的值大于10^18时，在这个变量里减去10^18，另一个变量加1，用两个变量表示累 ...

order of magnitude is right if I remember correctly.

The actual result seemed a little bit smaller than yours here, not so sure. Wiki....

作者: maomaobiao 时间: 2013-9-12 08:58

老陈发表于 2013-9-12 03:54
计算溢出的问题解决了，当变量的值大于10^18时，在这个变量里减去10^18，另一个变量加1，用两个变量表示累 ...

Have you consider the duplicates when you "flip" the large square?

for example, 1 2 2 4 are equivalent for a 2x2 square.
3 4 1 3

作者: 老陈 时间: 2013-9-12 09:26

maomaobiao 发表于 2013-9-11 18:58
Have you consider the duplicates when you "flip" the large square?

for example, 1 2 ...

你的例子我认为后一个是前一个派生出来的。
在我的结果中把它们数成2个。
如果不考虑派生，前面那个10位数应该是准确答案。
后面那个22位数的答案是把所有派生出来的都计算在内了，是否把完全相同的一个结果多次计算，我拿不很准，但我写的程序计算4x4的结果准确，用来计算9x9的应该问题不大。

欢迎光临智游城 (http://zhiyoucheng.co/)