谜题：方形拼图

Question

最近几天，我暂时放下了硕士的学习，专注于一个看起来简单的谜题：

---

这是一个10乘10的方格，总共有100个可以走的地方。目标是从一个角落开始，按照一些简单的“走法规则”走遍所有地方，最后到达100（如果你是程序员，从0开始的话就是99 :)）。

走的规则是：
1. 在垂直和水平方向上跳两格
2. 在对角线上跳一格
3. 每个方格只能走一次

为了更好地理解，这里有一个有效的走法示例（到第8步为止）：
示例走法 http://img525.imageshack.us/img525/280/squarepuzzle.png

---

我出于无聊，手动尝试这个谜题。多年来，我时不时地尝试用手解这个谜题，但从来没有超过96。听起来简单？你可以试试看 :)

为了破解这个问题，我用Python写了一个短小的程序（大约100行代码）。我在这个语言上还是个新手，想看看我能做到什么。
这个程序简单地使用了穷举法，也就是暴力深度优先搜索。

我的问题从这里开始：不幸的是，这个程序无法解决问题，因为状态空间太大，搜索永远无法结束，也找不到解决方案。它可以轻松到达98（并打印出来），但仍然不是完整的解决方案。
程序还会打印出它到目前为止覆盖的搜索树的长度。在几分钟内，从第65个元素开始的走法列表就被覆盖到最后，只是单一路径。这些数字在时间上呈指数级减少。我运行了代码很长时间，始终无法突破50的障碍，现在我已经信服了。

看来这个简单的方法不够，除非我永远运行下去。那么，我该如何改进我的代码，使其更快、更高效，以便找到解决方案呢？

基本上，我希望看到一些关于如何：

1. 捕捉并利用与这个问题相关的领域知识

2. 应用编程技巧/窍门来克服穷举问题

   ..最终实现一个实质性的解决方案。

提前感谢大家。

---

修订
感谢Dave Webb将这个问题与其所属领域联系起来：

这与骑士巡逻问题非常相似，骑士在棋盘上移动而不重新访问同一个方格。基本上这是同一个问题，只是“走法规则”不同。

---

Answer 1

我决定研究一下这个问题，看看能不能把它拆分成5x5的小块，每个小块的结束位置离下一个小块的起始位置只有一步的距离。

我首先假设5x5的小块是可以解决的。结果证明是可以的，而且速度很快。

于是我运行了solve(0,5)并查看了结果。我在Excel里画了一个10x10的编号网格，并在里面放了一个5x5的编号网格来做对照。然后我就搜索结果中以#]（结束单元格）为标记的，看看哪些离下一个5x5的起始位置只有一步的距离。（比如，对于第一个小块，我搜索了“13]”。）

供参考：

10 x 10 grid                       5 x 5 grid 
 0  1  2  3  4 |  5  6  7  8  9     0  1  2  3  4
10 11 12 13 14 | 15 16 17 18 19     5  6  7  8  9
20 21 22 23 24 | 25 26 27 28 29    10 11 12 13 14
30 31 32 33 34 | 35 36 37 38 39    15 16 17 18 19
40 41 42 43 44 | 45 46 47 48 49    20 21 22 23 24
---------------+---------------
50 51 52 53 54 | 55 56 57 58 59
60 61 62 63 64 | 65 66 67 68 69
70 71 72 73 74 | 75 76 77 78 79
80 81 82 83 84 | 85 86 87 88 89
90 91 92 93 94 | 95 96 97 98 99

这是一个可能的解决方案：

第一个小块：[0, 15, 7, 19, 16, 1, 4, 12, 20, 23, 8, 5, 17, 2, 10, 22, 14, 11, 3, 18, 6, 9, 24, 21, 13]，它在10x10网格中形成了一个对角线跳跃，跳到了下一个5x5的第一个角落。

第二个小块：[0, 12, 24, 21, 6, 9, 17, 2, 14, 22, 7, 15, 18, 3, 11, 23, 20, 5, 8, 16, 19, 4, 1, 13, 10]，它的最后一个单元是25，在10x10网格中，这个位置离55有两步的距离。

第三个小块：[0, 12, 24, 21, 6, 9, 17, 5, 20, 23, 8, 16, 19, 4, 1, 13, 10, 2, 14, 11, 3, 18, 15, 7, 22]，它的最后一个单元是97，在10x10网格中，这个位置离94也有两步的距离。

第四个小块可以是任何有效的解决方案，因为结束点并不重要。不过，从5x5到10x10的映射会比较复杂，因为这个小块是从对角的另一边开始的。于是我没有翻译，而是运行了solve(24,5)，随机选择了一个：[24, 9, 6, 21, 13, 10, 2, 17, 5, 20, 23, 8, 16, 1, 4, 12, 0, 15, 18, 3, 11, 14, 22, 7, 19]

现在既然知道5x5的解决方案是有效的，并且结束点可以合法地移动到下一个5x5的角落，那么这一切都应该可以通过编程来实现。5x5的解决方案总共有552个，这意味着存储这些解决方案以便后续计算和重新映射是相对简单的。

除非我做错了，否则这给出了一个可能的解决方案（上面定义的5x5解决方案分别是第一到第四个）：

def trans5(i, col5, row5):
    if i < 5: return 5 * col5 + 50 * row5 + i
    if i < 10: return 5 + 5 * col5 + 50 * row5 + i
    if i < 15: return 10 + 5 * col5 + 50 * row5 + i
    if i < 20: return 15 + 5 * col5 + 50 * row5 + i
    if i < 25: return 20 + 5 * col5 + 50 * row5 + i

>>> [trans5(i, 0, 0) for i in one] + [trans5(i, 1, 0) for i in two] + [trans5(i, 0, 1) for i in three] + [trans5(i, 1, 1) for i in four]
    [0, 30, 12, 34, 31, 1, 4, 22, 40, 43, 13, 10, 32, 2, 20, 42, 24, 21, 3, 33, 11, 14, 44, 41, 23, 5, 27, 49, 46, 16, 19, 37, 7, 29, 47, 17, 35, 38, 8, 26, 48, 45, 15, 18, 36, 39, 9, 6, 28, 25, 50, 72, 94, 91, 61, 64, 82, 60, 90, 93, 63, 81, 84, 54, 51, 73, 70, 52, 74, 71, 53, 83, 80, 62, 92, 99, 69, 66, 96, 78, 75, 57, 87, 65, 95, 98, 68, 86, 56, 59, 77, 55, 85, 88, 58, 76, 79, 97, 67, 89]

有人能帮我检查一下这个方法吗？我觉得这是一个有效的解决方案和拆分问题的方法。

Answer 2

这个问题和骑士巡游问题很像，骑士在棋盘上移动，但不能重复走到同一个格子。基本上是同样的问题，只是“移动规则”不同。

我记得解决骑士巡游问题时一个很重要的优化方法，就是在选择下一个移动时，先看目标格子上可以走的步数，选择可走步数少的格子。这样可以让搜索更集中在某个区域，尽量填满这个区域，而不是到处乱跑，留下那些永远无法到达的小孤岛格子。（这就是沃恩斯多夫算法。）

另外，尽量考虑对称性。例如，在最简单的情况下，你起始格子的x和y坐标只需要到5就可以，因为棋盘旋转后(10,10)和(1,1)是一样的。

Answer 3

最后，我写了一段修改过的Python代码，解决了这个问题。我运行了这段代码几个小时，已经找到了五十万个解法。
不过，要找到所有的解法，还是需要进行全面的搜索，也就是让程序一直运行，直到它找到所有的组合。不过，找到“一个”合法解法的时间可以缩短到“线性时间”。

首先，我学到了一些东西：

1. 感谢Dave Webb的回答和ammoQ的回答。这个问题确实是哈密尔顿路径问题的扩展，属于NP困难问题。最开始没有“简单”的解决方案。有一个著名的谜题叫做骑士巡游，其实就是同样的问题，只是棋盘的大小和移动规则不同。关于这个问题，有很多讨论和方法，已经设计了很多算法。

2. 感谢Joe的回答。这个问题可以从底向上解决，可以拆分成可解决的小问题。解决的小问题可以通过入口和出口的方式连接起来（一个出口可以连接到另一个入口），这样主问题就可以看作是由小问题组成的。这种方法是合理和实用的，但并不完整，不能保证一定能找到答案，如果答案存在的话。

经过全面的暴力搜索，我在代码中总结了一些关键点：

• Warnsdorff算法：这个算法是快速找到大量解法的关键。它的意思是，你应该选择下一个移动到“最不容易到达”的地方，并把你的“待去”列表按可达性升序排列。最不容易到达的地方是指后续可能移动的选择最少的地方。

  下面是伪代码（来自维基百科）：

---

一些定义：

• 如果位置P可以通过一次骑士的移动到达位置Q，并且Q还没有被访问过，那么位置Q是可以从位置P访问的。
• 位置P的可达性是指从P可以访问到的位置数量。

算法：

将P设置为棋盘上的一个随机初始位置，在P处标记移动编号为“1”。对于从2到棋盘上方格数量的每一个移动编号，设S为从输入位置可达的位置集合，将P设置为S中可达性最小的位置，在P处标记当前移动编号，返回标记后的棋盘——每个方格将标记为被访问时的移动编号。

---

• 检查孤岛：利用领域知识的一个好方法。 如果某个移动（除非是最后一个）会导致它的任何邻居变成孤岛，即不再能被其他位置访问，那么这个分支就不再继续研究。结合Warnsdorff算法，这样可以节省相当多的时间（大约25%）。

这是我用Python写的代码，解决了这个谜题（考虑到这个问题是NP困难的，结果还算可以）。这段代码很容易理解，因为我认为自己在Python方面还是初学者。注释也很简单明了，解释了实现的过程。解法可以通过一个简单的图形界面在基本的网格上显示（代码中有相关指导）。

# Solve square puzzle
import operator

class Node:
# Here is how the squares are defined
    def __init__(self, ID, base):
        self.posx = ID % base
        self.posy = ID / base
        self.base = base
    def isValidNode(self, posx, posy):
        return (0<=posx<self.base and 0<=posy<self.base)

    def getNeighbors(self):
        neighbors = []
        if self.isValidNode(self.posx + 3, self.posy): neighbors.append(self.posx + 3 + self.posy*self.base)
        if self.isValidNode(self.posx + 2, self.posy + 2): neighbors.append(self.posx + 2 + (self.posy+2)*self.base)
        if self.isValidNode(self.posx, self.posy + 3): neighbors.append(self.posx + (self.posy+3)*self.base)
        if self.isValidNode(self.posx - 2, self.posy + 2): neighbors.append(self.posx - 2 + (self.posy+2)*self.base)
        if self.isValidNode(self.posx - 3, self.posy): neighbors.append(self.posx - 3 + self.posy*self.base)
        if self.isValidNode(self.posx - 2, self.posy - 2): neighbors.append(self.posx - 2 + (self.posy-2)*self.base)
        if self.isValidNode(self.posx, self.posy - 3): neighbors.append(self.posx + (self.posy-3)*self.base)
        if self.isValidNode(self.posx + 2, self.posy - 2): neighbors.append(self.posx + 2 + (self.posy-2)*self.base)
        return neighbors


# the nodes go like this:
# 0 => bottom left
# (base-1) => bottom right
# base*(base-1) => top left
# base**2 -1 => top right
def solve(start_nodeID, base):
    all_nodes = []
    #Traverse list is the list to keep track of which moves are made (the id numbers of nodes in a list)
    traverse_list = [start_nodeID]
    for i in range(0, base**2): all_nodes.append(Node(i, base))
    togo = dict()
    #Togo is a dictionary with (nodeID:[list of neighbors]) tuples
    togo[start_nodeID] = all_nodes[start_nodeID].getNeighbors()
    solution_count = 0


    while(True):
        # The search is exhausted
        if not traverse_list:
            print "Somehow, the search tree is exhausted and you have reached the divine salvation."
            print "Number of solutions:" + str(solution_count)
            break

        # Get the next node to hop
        try:
            current_node_ID = togo[traverse_list[-1]].pop(0)
        except IndexError:
            del togo[traverse_list.pop()]
            continue

        # end condition check
        traverse_list.append(current_node_ID)
        if(len(traverse_list) == base**2):
            #OMG, a solution is found
            #print traverse_list
            solution_count += 1
            #Print solution count at a steady rate
            if(solution_count%100 == 0): 
                print solution_count
                # The solution list can be returned (to visualize the solution in a simple GUI)
                #return traverse_list


        # get valid neighbors
        valid_neighbor_IDs = []
        candidate_neighbor_IDs = all_nodes[current_node_ID].getNeighbors()
        valid_neighbor_IDs = filter(lambda id: not id in traverse_list, candidate_neighbor_IDs)

        # if no valid neighbors, take a step back
        if not valid_neighbor_IDs:
            traverse_list.pop()
            continue

        # if there exists a neighbor which is accessible only through the current node (island)
        # and it is not the last one to go, the situation is not promising; so just eliminate that
        stuck_check = True
        if len(traverse_list) != base**2-1 and any(not filter(lambda id: not id in traverse_list, all_nodes[n].getNeighbors()) for n in valid_neighbor_IDs): stuck_check = False

        # if stuck
        if not stuck_check:
            traverse_list.pop()
            continue

        # sort the neighbors according to accessibility (the least accessible first)
        neighbors_ncount = []
        for neighbor in valid_neighbor_IDs:
            candidate_nn = all_nodes[neighbor].getNeighbors()
            valid_nn = [id for id in candidate_nn if not id in traverse_list]
            neighbors_ncount.append(len(valid_nn))
        n_dic = dict(zip(valid_neighbor_IDs, neighbors_ncount))
        sorted_ndic = sorted(n_dic.items(), key=operator.itemgetter(1))

        sorted_valid_neighbor_IDs = []
        for (node, ncount) in sorted_ndic: sorted_valid_neighbor_IDs.append(node)



        # if current node does have valid neighbors, add them to the front of togo list
        # in a sorted way
        togo[current_node_ID] = sorted_valid_neighbor_IDs


# To display a solution simply
def drawGUI(size, solution):
    # GUI Code (If you can call it a GUI, though)
    import Tkinter
    root = Tkinter.Tk()
    canvas = Tkinter.Canvas(root, width=size*20, height=size*20)
    #canvas.create_rectangle(0, 0, size*20, size*20)
    canvas.pack()

    for x in range(0, size*20, 20):
        canvas.create_line(x, 0, x, size*20)
        canvas.create_line(0, x, size*20, x)

    cnt = 1
    for el in solution:
        canvas.create_text((el % size)*20 + 4,(el / size)*20 + 4,text=str(cnt), anchor=Tkinter.NW)
        cnt += 1
    root.mainloop()


print('Start of run')

# it is the moment
solve(0, 10)

#Optional, to draw a returned solution
#drawGUI(10, solve(0, 10))

raw_input('End of Run...')

感谢所有分享知识和想法的人。