抛砖引玉，讨论一下Jigsaw题？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

抛砖引玉，讨论一下Jigsaw题？

抛砖引玉，讨论一下Jigsaw题？# JobHunting - 待字闺中

j*l2010-04-19 07:04

1 楼

总觉得和Boggle题，跳马(骑士周游)题，迷宫题，图论，DFS, 回溯有千丝万缕的联系。不知
道和动态规划有没有关系。
题目:
嘉定每块碎片最多和另外四块碎片接合。你用到的数据结构是什么？假定你已经有了一个方法，可以告诉你两块碎片是否可以接合。你该如何解决这个puzzle, 使得你调用该方法的次数是最少的？

b*w2010-04-19 07:04

2 楼

先说一个比较笨的 backtracking + prune的办法吧,不能保证最少比较。
假设有n块 jagsaw,number 0 to n-1, 建一个nx4的表 lookuptable，
lookuptable[i][0]-[3]，就是可以和i jigsaw 连接的另外四块。然后每两块 jigsaw
i,j 互比，调用提供函数，如果i,j可以连接，就把对方的index添到自己的
lookuptable entry里面去。worst case (n-1)!其实不用，如果i,j其中有一个的
lookuptable entry已经满了就不需要比了。
然后假设最后的board是 (n-1)*(n-1）的，整个backtracking的程序框架是
1。首先判断当前board放满没有，如果满了，说明我们已经找到了一个解。
2。如果没有，先选择一个空的位置。
(x,y)=possible_move();
现在先随机选，实际可以优化。
然后产生可以放在这个位置的所有jigsaw candidates,这里需要一个
buffer，i.e.Use