c*****z
发帖数: 182 | 1 就是那种九个格，一个空，开始八个数字是打乱得
要求排成按顺序得，这种puzzle英文叫什么？
有算法吗，能否给个链接看看，谢谢！
比如给你
2 1 3
4 * 7
5 6 8
排好之后是这样得
1 2 3
4 5 6
7 8 * |
k****f
发帖数: 3794 | 2 a* search
【在 c*****z 的大作中提到】
: 就是那种九个格，一个空，开始八个数字是打乱得
: 要求排成按顺序得，这种puzzle英文叫什么？
: 有算法吗，能否给个链接看看，谢谢！
: 比如给你
: 2 1 3
: 4 * 7
: 5 6 8
: 排好之后是这样得
: 1 2 3
: 4 5 6
|
p***o
发帖数: 1252 | 3 穷举呗，36万种情况，用BFS估计一秒钟都用不到。
【在 c*****z 的大作中提到】
: 就是那种九个格，一个空，开始八个数字是打乱得
: 要求排成按顺序得，这种puzzle英文叫什么？
: 有算法吗，能否给个链接看看，谢谢！
: 比如给你
: 2 1 3
: 4 * 7
: 5 6 8
: 排好之后是这样得
: 1 2 3
: 4 5 6
|
c*****z
发帖数: 182 | 4 知道这个问题得英文名吗，我好去嗖嗖
【在 k****f 的大作中提到】
: a* search
|
c*****z
发帖数: 182 | 5 为什么是穷举啊，难道在一定步数内肯定可以解出？
【在 p***o 的大作中提到】
: 穷举呗，36万种情况，用BFS估计一秒钟都用不到。
|
p***o
发帖数: 1252 | 6 It's a problem of reachability. Either you show it's reachable or
prove it's not. For the simple case of 9 boxes, there are only 9!
vertices in the graph so brute-force search will work. Otherwise
you need some heuristics like a* search.
【在 c*****z 的大作中提到】
: 为什么是穷举啊，难道在一定步数内肯定可以解出？
|
c*****z
发帖数: 182 | 7 cool, i haven't thought it in that way, can you give some more
details about how to detect reachability? or give a link, thanks!
【在 p***o 的大作中提到】
: It's a problem of reachability. Either you show it's reachable or
: prove it's not. For the simple case of 9 boxes, there are only 9!
: vertices in the graph so brute-force search will work. Otherwise
: you need some heuristics like a* search.
|
p***o
发帖数: 1252 | 8 http://en.wikipedia.org/wiki/Graph_search_algorithm
【在 c*****z 的大作中提到】
: cool, i haven't thought it in that way, can you give some more
: details about how to detect reachability? or give a link, thanks!
|
s*******d
发帖数: 59 | |
