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 的大作中提到】
: 一年级的能有多难，贴出来让我老婆最多十分钟给你搞定，我差一点，二十分钟。
: 有suduko的app，你可以下载下来做做
: 各种限制条件交替使用，不能确定的写下可能的值，一个一个试。
|
l*****8
发帖数: 16949 | 4 就是各种限制条件。你总结的越多就越容易解。
我的基本做法是先做可以直接看出来的。等到这部分做完就在没解出来的空格里写上所
有可能的值。比如如果各种条件排除了123789,你就写上456.然后就能有很多新的限制
条件被发现。比如如果你发现一行里有两个45, 那么这行里其它的4，5都可以排除掉。
如果一行里有3个456，那么这行里其他的456也可以被排除掉。还有许多利用关联条件
发现更复杂的关系。反正你能发现的条件越多，做得就越快。这种你随便下个app玩玩
就能琢磨出来了。 |
d****g
发帖数: 7460 | 5 高级BSO啊
hard
【在 w*******g 的大作中提到】
: http://en.wikipedia.org/wiki/Sudoku
: 我一年级的儿子有这么个作业， 每星期都有。 昨天我想帮帮他， 结果自己也做不出
: 来。 几小时， 烦了就只好用 Prolog 写了个程序硬算出了。 知道这东西是 NP-hard
: 的的， 可是小学一年级的作业不应该怎么难吧。
|
w*******g
发帖数: 9932 | 6 make sense, Thank you
【在 l*****8 的大作中提到】
: 就是各种限制条件。你总结的越多就越容易解。
: 我的基本做法是先做可以直接看出来的。等到这部分做完就在没解出来的空格里写上所
: 有可能的值。比如如果各种条件排除了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 的大作中提到】
: 你们一年级有你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 的大作中提到】
: 这还真不难。一年级可以做，不过要有点耐心。
: 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，什么ＸＹ，剑鱼等等，不过一般的应该用不到吧． |
p**s
发帖数: 2707 | 16 高手啊，我只知道什么三链四链之类的
【在 M******k 的大作中提到】
: 还有一些比较怪异的pattern，什么ＸＹ，剑鱼等等，不过一般的应该用不到吧．
|
M******k
发帖数: 27573 | 17 知道名字没用啊，解的时候看不出来也是白给。
【在 p**s 的大作中提到】
: 高手啊，我只知道什么三链四链之类的
|
b****b
发帖数: 656 | 18 这个不可能是np hard问题吧? 我教小朋友编程就写了个soduku solver. 就是把一个个
手工判断方法反复用上去。到最后有些没法完全决定的, 就随便放些数, 然后接着穷举。
hard
【在 w*******g 的大作中提到】
: 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 的大作中提到】
: * * * | * 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 的大作中提到】
: 这个不可能是np hard问题吧? 我教小朋友编程就写了个soduku solver. 就是把一个个
: 手工判断方法反复用上去。到最后有些没法完全决定的, 就随便放些数, 然后接着穷举。
:
: hard
|
w*******g
发帖数: 9932 | 22 thanks. This looks like a good heuristics.
【在 x***1 的大作中提到】
: 介绍一种方法：
: 排除法，找出所有可能的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 的大作中提到】
: 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 的大作中提到】
: http://en.wikipedia.org/wiki/Sudoku
: 我一年级的儿子有这么个作业， 每星期都有。 昨天我想帮帮他， 结果自己也做不出
: 来。 几小时， 烦了就只好用 Prolog 写了个程序硬算出了。 知道这东西是 NP-hard
: 的的， 可是小学一年级的作业不应该怎么难吧。
|
