w*******g 发帖数: 9932 | 1 http://en.wikipedia.org/wiki/Sudoku
我一年级的儿子有这么个作业, 每星期都有。 昨天我想帮帮他, 结果自己也做不出
来。 几小时, 烦了就只好用 Prolog 写了个程序硬算出了。 知道这东西是 NP-hard
的的, 可是小学一年级的作业不应该怎么难吧。 |
G*******n 发帖数: 2041 | 2 一年级的能有多难,贴出来让我老婆最多十分钟给你搞定,我差一点,二十分钟。
有suduko的app,你可以下载下来做做
各种限制条件交替使用,不能确定的写下可能的值,一个一个试。 |
w*******g 发帖数: 9932 | 3 我没有那个耐心挨个试。greedy method doesn't work. Backtrack takes a long
time.
真没有技巧吗
【在 G*******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一年级的能有多难,贴出来让我老婆最多十分钟给你搞定,我差一点,二十分钟。 : 有suduko的app,你可以下载下来做做 : 各种限制条件交替使用,不能确定的写下可能的值,一个一个试。
|
l*****8 发帖数: 16949 | 4 就是各种限制条件。你总结的越多就越容易解。
我的基本做法是先做可以直接看出来的。等到这部分做完就在没解出来的空格里写上所
有可能的值。比如如果各种条件排除了123789,你就写上456.然后就能有很多新的限制
条件被发现。比如如果你发现一行里有两个45, 那么这行里其它的4,5都可以排除掉。
如果一行里有3个456,那么这行里其他的456也可以被排除掉。还有许多利用关联条件
发现更复杂的关系。反正你能发现的条件越多,做得就越快。这种你随便下个app玩玩
就能琢磨出来了。 |
d****g 发帖数: 7460 | 5 高级BSO啊
hard
【在 w*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://en.wikipedia.org/wiki/Sudoku : 我一年级的儿子有这么个作业, 每星期都有。 昨天我想帮帮他, 结果自己也做不出 : 来。 几小时, 烦了就只好用 Prolog 写了个程序硬算出了。 知道这东西是 NP-hard : 的的, 可是小学一年级的作业不应该怎么难吧。
|
w*******g 发帖数: 9932 | 6 make sense, Thank you
【在 l*****8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是各种限制条件。你总结的越多就越容易解。 : 我的基本做法是先做可以直接看出来的。等到这部分做完就在没解出来的空格里写上所 : 有可能的值。比如如果各种条件排除了123789,你就写上456.然后就能有很多新的限制 : 条件被发现。比如如果你发现一行里有两个45, 那么这行里其它的4,5都可以排除掉。 : 如果一行里有3个456,那么这行里其他的456也可以被排除掉。还有许多利用关联条件 : 发现更复杂的关系。反正你能发现的条件越多,做得就越快。这种你随便下个app玩玩 : 就能琢磨出来了。
|
G********r 发帖数: 3161 | 7 你们一年级有你Wiki贴的那个难么?我觉得一年级不应该有那么难。其实就是排除法,
一般从数字最多的那个行或是列开始,比如说你Wiki里的那个,数字最多的那个是一列
数字:79X6X2X18,X表示空白,这列数字差345,然后你看6和2之间的那个空格的那一行
,已经有3和4了,那么就只能放5了。以此类推。 |
w*******g 发帖数: 9932 | 8 I will post it when I have the chance but it is that difficult. Greedy
method didn't work
the solution I found using program is quite different from what my initial
attempt by hand.
【在 G********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你们一年级有你Wiki贴的那个难么?我觉得一年级不应该有那么难。其实就是排除法, : 一般从数字最多的那个行或是列开始,比如说你Wiki里的那个,数字最多的那个是一列 : 数字:79X6X2X18,X表示空白,这列数字差345,然后你看6和2之间的那个空格的那一行 : ,已经有3和4了,那么就只能放5了。以此类推。
|
w*******g 发帖数: 9932 | 9 * * * | * 4 * | * 5 *
6 1 * | 7 * * | * * *
* 3 2 | 6 * * | * * *
---------------------
9 5 * | * * * | * 6 7
* * * | 1 * 7 | * * *
7 6 * | * * * | * 3 1
---------------------
* * * | * * 3 | 6 9 *
* * * | * * 1 | * 7 3
* 8 * | * 2 * | * * * |
S****p 发帖数: 3928 | 10 这还真不难。一年级可以做,不过要有点耐心。
879342156
614785329
532619748
951238467
423167985
768594231
145873692
296451873
387926514
完全不需要二选一。窍门其实很简单,就是根据的基本规则。横竖和方框里每个数字只
能出现一次。 |
|
|
w*******g 发帖数: 9932 | 11 cool, good to know it's easy to do
【在 S****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这还真不难。一年级可以做,不过要有点耐心。 : 879342156 : 614785329 : 532619748 : 951238467 : 423167985 : 768594231 : 145873692 : 296451873 : 387926514
|
S****p 发帖数: 3928 | 12 例如
9-- --- ---
--- --- ---
--- --- ---
--9 --- ---
--- --- ---
--- --- ---
--- -9- ---
--- --- --9
-?- --- ---
这个问号就是9
这是一种思路 |
S****p 发帖数: 3928 | 13 其他的一些思路
例如一行只缺2 或 4, 就对应看这两个位置的列和方块。如果有4,那么这个对应位置
就是2. 大概就这意思。
复杂一点的就要做记号了。 |
l*****8 发帖数: 16949 | 14 我也试了一下,确实不难。还没到我说的需要填几个可能的值的那一步。 |
M******k 发帖数: 27573 | 15 还有一些比较怪异的pattern,什么XY,剑鱼等等,不过一般的应该用不到吧. |
p**s 发帖数: 2707 | 16 高手啊,我只知道什么三链四链之类的
【在 M******k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还有一些比较怪异的pattern,什么XY,剑鱼等等,不过一般的应该用不到吧.
|
M******k 发帖数: 27573 | 17 知道名字没用啊,解的时候看不出来也是白给。
【在 p**s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 高手啊,我只知道什么三链四链之类的
|
b****b 发帖数: 656 | 18 这个不可能是np hard问题吧? 我教小朋友编程就写了个soduku solver. 就是把一个个
手工判断方法反复用上去。到最后有些没法完全决定的, 就随便放些数, 然后接着穷举。
hard
【在 w*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://en.wikipedia.org/wiki/Sudoku : 我一年级的儿子有这么个作业, 每星期都有。 昨天我想帮帮他, 结果自己也做不出 : 来。 几小时, 烦了就只好用 Prolog 写了个程序硬算出了。 知道这东西是 NP-hard : 的的, 可是小学一年级的作业不应该怎么难吧。
|
w*****3 发帖数: 2301 | |
x***1 发帖数: 999 | 20 介绍一种方法:
排除法,找出所有可能的1和9,比如:
找出所有1,第一个3x3有1,不用找,横着数第二个3x3里,第二行不能为1 ,第一列不
能为1,第三列不能为1,那么只有第3行第2列为1。第三个3x3里,第2行和3行以及3列
不能为1,只有第1行第一列为1。
得到如下阵列,大概需要2分钟,
* * * | * 4 * | 1 5 *
6 1 * | 7 * * | * * *
* 3 2 | 6 1 * | * * *
---------------------
9 5 1 | * * * | * 6 7
* * * | 1 * 7 | * * *
7 6 * | * * * | * 3 1
---------------------
1 * * | * * 3 | 6 9 *
* * * | * * 1 | * 7 3
* 8 * | * 2 * | * 1 *
以此类推,找2-9,需要15分钟,得到结果。
【在 w*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : * * * | * 4 * | * 5 * : 6 1 * | 7 * * | * * * : * 3 2 | 6 * * | * * * : --------------------- : 9 5 * | * * * | * 6 7 : * * * | 1 * 7 | * * * : 7 6 * | * * * | * 3 1 : --------------------- : * * * | * * 3 | 6 9 * : * * * | * * 1 | * 7 3
|
|
|
w*******g 发帖数: 9932 | 21 what you described is actually a NP method
in fact, my prolog soduku solver does exactly the same thing as well except
it can find all the solutions with backtracking.
the generalization of Soduku is NP-complete according to a Japanese paper (
see the wiki link)
举。
【在 b****b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个不可能是np hard问题吧? 我教小朋友编程就写了个soduku solver. 就是把一个个 : 手工判断方法反复用上去。到最后有些没法完全决定的, 就随便放些数, 然后接着穷举。 : : hard
|
w*******g 发帖数: 9932 | 22 thanks. This looks like a good heuristics.
【在 x***1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 介绍一种方法: : 排除法,找出所有可能的1和9,比如: : 找出所有1,第一个3x3有1,不用找,横着数第二个3x3里,第二行不能为1 ,第一列不 : 能为1,第三列不能为1,那么只有第3行第2列为1。第三个3x3里,第2行和3行以及3列 : 不能为1,只有第1行第一列为1。 : 得到如下阵列,大概需要2分钟, : * * * | * 4 * | 1 5 * : 6 1 * | 7 * * | * * * : * 3 2 | 6 1 * | * * * : ---------------------
|
s*****j 发帖数: 6435 | 23 你要叫小孩编程的话, 这是一个非常好的例子.
except
【在 w*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : what you described is actually a NP method : in fact, my prolog soduku solver does exactly the same thing as well except : it can find all the solutions with backtracking. : the generalization of Soduku is NP-complete according to a Japanese paper ( : see the wiki link) : : 举。
|
s*****c 发帖数: 753 | 24 Sudoku Solver algorithm
http://www.sudokuwiki.org/sudoku.htm
Click the right list to show explanations of each strategies. I believe
most people can understand the simple strategy 1-6.
Try the examples they provide or you can input your soduku. Click take step
button to see the solution step by step.
hard
【在 w*******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://en.wikipedia.org/wiki/Sudoku : 我一年级的儿子有这么个作业, 每星期都有。 昨天我想帮帮他, 结果自己也做不出 : 来。 几小时, 烦了就只好用 Prolog 写了个程序硬算出了。 知道这东西是 NP-hard : 的的, 可是小学一年级的作业不应该怎么难吧。
|