时间戳

首页 > 解决方案 > 查找多米诺骨牌顺序的有效方法

python - 查找多米诺骨牌顺序的有效方法

问题描述

我有一个以这种方式工作的小型多米诺骨牌游戏：给了我一个N*N4 块，我需要对它们进行排序，以便每两个相邻的块具有相同的编号。瓷砖可以旋转。例如，这是我的 2*2 板：

a,b,c,d = [1,2,3,4], [7,9,6,2], [6,8,8,5], [3,5,0,0]

它们可以通过以下方式可视化：

print(print_2_tiles(a,b,'a','b'))
print(print_2_tiles(d,c,'d','c'))

##############
#**1**##**7**#
#4*A*2##2*B*9#
#**3**##**6**#
##############
##############
#**3**##**6**#
#0*D*5##5*C*8#
#**0**##**8**#
##############

可以看出，“赢得”这个棋盘的唯一方法是我订购瓷砖的方式，因为<a,b>仅通过 2 连接，<a,d>仅通过 3 连接，依此类推……<a,c>,<b,d>根本没有连接。任何瓷砖的旋转或移动都不会获得“胜利”。

我写了函数：

  1. 查找任何给定的 2 个图块之间的连接
  2. 计算出连接给定的 2 个图块需要多少次旋转
  3. 检查所有可能性并找到正确的顺序

然而，这只是一个带有 16*12*8 选项的简单案例，我可以排除许多选项，因为有独特的连接器（即连接的“2”<a,c>在其他瓷砖中不存在）。如果我得到一个更大的板（更大的字母表也可能使事情复杂化......），比如说，5 * 5，选项的数量将是 100 * 96 * 92......并且蛮力不会削减它。

我怎样才能有效地找到正确的顺序（保证板子有一个正确的顺序）？

这是我的努力：

import numpy as np
from itertools import combinations, product


# returns list of [<connector element>, <indices of element in a>, <indices of element in b>]
def find_connections(a,b):
    intersected_elem = np.array(list(set(a).intersection(b)))

    possible_connections = []

    for val in intersected_elem:
        x = list(np.where(np.array(a) == val)[0])
        y = list(np.where(np.array(b) == val)[0])
        possible_connections.append([val,x,y])

    return possible_connections

def str_tile(t, name):
    template = '''#######
#**{}**#
#{}*{}*{}#
#**{}**#
#######'''

    up,right,down,left = t

    return template.format(up,left,name.upper(),right,down)

def print_2_tiles(a,b, name_a, name_b):

    res = ''

    for line in zip(str_tile(a,name_a).splitlines(), str_tile(b,name_b).splitlines()):
        res += ''.join(line)
        res += '\n'

    return res[:-1]


def find_final_connections(tiles_ls):
    tiles_combinations = list(combinations(tiles_ls, 2))

    a_idx,b_idx = 0,1
    final_connections = []

    for comb in tiles_combinations:
        connections = find_connections(comb[0], comb[1])

        print('({},{})'.format(a_idx,b_idx), connections, end='\t')

        if len(connections):
            print('this meants {},{} are connected via {} in directions {},{}'.format(a_idx,b_idx, connections[0][0], connections[0][1][0], connections[0][2][0]))
            final_connections.append((a_idx,b_idx))
        else:
            print()

        # is there a neater way, using enumerate on itertools.combinations?
        b_idx += 1
        if b_idx == len(tiles_ls):
            a_idx += 1
            b_idx = a_idx + 1   


    print(final_connections)


a,b,c,d = [1,2,3,4], [7,9,6,2], [6,8,8,5], [3,5,0,0]
tiles_ls = [a,b,c,d]
find_final_connections(tiles_ls) # returns a 4-elem list -> success

print('#'*30)

a,b,c,d = [1,2,3,4], [7,9,6,2], [6,8,8,5], [0,5,0,0]
tiles_ls = [a,b,c,d]
find_final_connections(tiles_ls) # returns a 3-elem list -> fail

标签： pythonalgorithm

解决方案

就这么确定暴力破解不行吗？

我会尝试一个系统的解决方案，你依次选择每一个多米诺骨牌并将其放在左上角，尝试所有四个旋转。然后选择另一个多米诺骨牌并将其放在第二个位置，尝试所有四个旋转并检查是否与第一个匹配。

依此类推，在任何阶段，您从剩余的多米诺骨牌中挑选一个，尝试四次旋转并检查与已知邻居的兼容性。

这最好写成递归过程。

推荐阅读