谜语:方形拼图

Question

最近几天,我已经从主人的研究中勉强自己,并一直专注于这个(看似简单的)难题:

---

这个10*10网格构成了100个可用场所的正方形.目标是从一个角落开始并遍历所有地方,相对于一些简单的"遍历规则"并达到数字100(如果你是一个程序员,则从99开始,而不是从0开始:)

遍历的规则是:
1.沿着垂直和水平轴跳两个空格
2.沿对角线一个空格跳
3.您只能访问每个方块一次

为了更好地可视化,这是一个有效的示例遍历(直到第8步):
示例Traverse http://img525.imageshack.us/img525/280/squarepuzzle.png

---

从手动的角度来说,我一直在努力解决这个难题.多年来,我一直试图手工解决它,但我从来没有超过96.听起来容易吗？试试自己,亲眼看看:)

因此,为了解决这个问题,我在Python中开发了一个简短的(大约100行代码)程序.我是这种语言的初学者,我想看看我能做些什么.
该程序只是应用详尽的尝试和错误解决技术.换句话说:蛮力深度首先搜索.

我的问题来自于此:遗憾的是,该程序无法解决问题,因为状态空间太大,以至于搜索永远不会找到解决方案.它可以毫不费力地达到98号(并打印出来),但仍然不是一个完整的解决方案.
该程序还打印出它到目前为止所涵盖的搜索树的长度.在几分钟内,例如,第65个元素的遍历列表将被覆盖到最后,只有一条路径.该数字以指数增加的时间段减少.我已经运行了很长一段时间的代码,并且无法超越50个障碍,现在我确信.

似乎这种简单的方法是不够的,除非我永远运行它.那么,如何才能更快,更高效地改进代码,以便提供解决方案呢？

基本上,我期待看到有关如何:

1. 捕获并利用特定于此问题的领域知识

2. 应用编程技巧/技巧来克服疲惫

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

提前致谢.

---

修订
感谢Dave Webb将问题与域名相关联:

这非常类似于Knight's Tour问题,该问题涉及将骑士绕棋盘移动而不重新访问同一个方块.基本上它是相同的问题,但具有不同的"导线规则".

---

Answer 1

这非常类似于Knight's Tour问题,该问题涉及将骑士绕棋盘移动而不重新访问同一个方块.基本上它是相同的问题,但具有不同的"导线规则".

我记得通过递归方式处理骑士之旅的关键优化是按照目标广场上可用移动次数的增加顺序进行下一步动作.这鼓励搜索尝试在一个区域中密集移动并填充它而不是全方位缩放并留下永远无法访问的小岛广场.(这是Warnsdorff的算法.)

还要确保尽可能考虑对称性.例如,在最简单的层面上,起始方块的x和y只需要达到5,因为(10,10)与板旋转时的(1,1)相同.

Answer 2

我决定看一下这个问题,看看我是否可以把它分解成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,5,5,17,2,10,22,14,11,3,18,6,9,24, 21,13]将对角跳跃放到5(10x10)下一个5 x 5的第一个角落.

第二广场:[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]将其与10x10中的25的最后一个方格放在一起,这是从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]在10x10中使用97的最后一个方格,这是从94开始的两次跳跃.

第四方可以是任何有效的解决方案,因为终点无所谓.然而,解决方案从5x5到10x10的映射更难,因为正方形从相反的角落开始.而不是翻译,运行解决(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解决方案,分别为1到4):

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 3

最后,我提出了修改后的Python代码来克服这个问题.我已经将代码调试了几个小时,它已经在几个小时内找到了50万个解决方案.
全套解决方案仍然需要进行彻底的详尽搜索,即让程序运行直到完成所有组合.但是,达到"一个"合法的解决方案可以减少到"线性时间".

首先,我学到的东西:

1. 感谢Dave Webb的回答和ammoQ的回答.问题确实是哈密顿路径问题的扩展,因为它是NP-Hard.开始时没有"简单"的解决方案.Knight's Tour有一个着名的谜语,它与不同尺寸的板/网格和不同的遍历规则完全相同.有许多事情已经说明和完成以阐述问题,并且已经设计了方法和算法.

2. 感谢Joe的回答.这个问题可以用自下而上的方式来解决,可以解决为可解决的子问题.解决的子问题可以在入口 - 出口点概念中连接(一个出口点可以连接到另一个入口点),这样主要问题就可以解决为较小规模问题的构成.不过,这种方法合理而实用,但并不完整.如果存在,则无法保证找到答案.

在详尽的暴力搜索中,以下是我在代码上开发的关键点:

• Warnsdorff的算法:该算法是快速获得方便数量的解决方案的关键点.它只是声明,您应该选择下一步到"最不可访问"的位置,并按升序或可访问性填充"去"列表.最不可访问的地方是指具有最少数量的可能跟随移动的地方.

  下面是伪代码(来自维基百科):

一些定义:

• 如果P可以通过单个骑士的移动移动到Q,则可以从位置P访问位置Q,并且尚未访问Q.
• 位置P的可访问性是可从P访问的位置的数量.

算法:

将P设置为电路板上的随机初始位置标记P处的电路板,每个移动编号的移动编号为"1",从2到电路板上的方格数,让S为可从输入位置访问的位置集将P设置为S中的位置,最小可达性标记P处的板,当前移动编号返回标记的板 - 每个方块将标记有访问它的移动编号.

• 检查岛屿:这里对领域知识的一个很好的利用被证明是方便的.如果移动(除非是最后一个移动)将导致其任何邻居成为孤岛,即任何其他邻居都无法访问,那么该分支将不再被调查.结合Warnsdorff算法节省了大量时间(非常大约25%).

这是我在Python中的代码,它解决了谜题(考虑到问题是NP-Hard,可接受的程度).代码很容易理解,因为我认为自己处于Python的初级阶段.这些评论在解释实施时非常简单.解决方案可以通过基本GUI(代码中的指南)显示在简单的网格上.

# 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...')

感谢所有人分享他们的知识和想法.

Answer 4

这只是http://en.wikipedia.org/wiki/Hamiltonian_path问题的一个例子.德国维基百科声称它是NP难的.