我想写一个简短的程序来寻找一个理想的多米诺骨牌链，想法？

Question

如果你不熟悉多米诺骨牌：你有两个数字的游戏。你必须这样安排，第一首曲子的结尾就是第二首曲子的开头。因此，如果我们有3个多米诺骨牌，其值为[3-1][3-4][1-4]，您可以将其排列为[1-3]、[3-4]、[4-1]或[4-1]、[1-3]、[3-4]，因为您可以切换开始的一侧（转动桌面）

现在谈谈我的代码问题：

我得到了一个关于domino值的数据：

^{tb1}$

dominos = {'D1': [1, 2,3,4,3,2,6], 'D2': [5,4,6,1,4,3,5]}

现在，如果我随机选择一个片段，需要找到一条“路线”到达特定的domino（所选的片段不能旋转），从1开始，再次以1结束，同时使用尽可能少的domino片段

例如：选择的片段是[3-4]，代码需要打印出路由，看起来像这样（或在数组中）：

1: #1 [1-5]
2: !#7 [5-6] 
3: !#3 [6-3] 
4: **[3-4]** 
5: #4 [4-1]

到目前为止，我已经尝试用许多for循环来实现这一点，但都没有成功

import pandas as pd


dominos = {'D1': [1, 2,3,4,3,2,6], 'D2': [5,4,6,1,4,3,5]}
data = pd.DataFrame(dominos) 


ranD = data.loc[4,]

def findpath(data, ranD):
    trargetD1 = ranD.D1 
    #fid possible start
    for x in range(len(data)):
        if data.loc[x,'D1'] == 1:
            start = start + data.loc[x,]
            if start.loc[x, 'D2'] == ranD.D1:
                PerfectStart = start.loc[x, 'D2']
            elif start.loc[x, 'D2'] != ranD.D1:
                PerfectStart = start.loc[1,] 
        else:
            print("no start found")
    # when a start was found, that doesn't match ranD at pos. D2 find possible steps        
    for x in range(len(data)):
        if PerfectStart.D2 == ranD.D2 :
            
            step1 = step1 + data.loc[x,'D1']
            if step1.loc[x, 'D2'] == ranD.D1:
                PerfectStep = step1.loc[x, 'D2']
            elif start.loc[x, 'D2'] != ranD.D1:
                PerfectStep = step1.loc[1,]
  
etc.

如果有人对如何处理这个问题有想法，请让我知道

非常感谢您的反馈

Answer 1

你想把它看作是一个图形问题

您有6个节点（1..6），骨牌是节点之间的边

您正在寻找一条从1到1的路径，该路径通过一条特定的边（a、b），并且具有最少的边数，并且不会通过同一条边两次

因此，天真的方法是寻找从1到a和从1到b的路径，希望或强制它们不共享边

但是，有些设置无法运行，因为您选择的第一条路径会阻塞第二条路径。有一个解决方案是maximum flow

为此，您需要将一个源链接到容量为2的节点1。a和b连接到容量为1的水槽。每隔一条边的容量为1。如果求解最大流，则它的容量为2，可以提取路径，或者容量为0或1，在这种情况下，没有解决方案

因为您只有6个节点，所以不必担心有一个非常有效的解决方案，因为几乎所有的节点都会运行得很快

如果您熟悉max flow，您可能可以稍微简化实现。如果没有，请不要担心，实施最简单的解决方案

Answer 2

我认为从概念上讲，最简单的方法是将这个问题转化为最小成本流问题。设置一个图，其中每个数字都有一个节点，每个domino都是一条边，连接与上面数字对应的节点，每个方向的容量为1，成本为1。删除与您试图在链中使用的domino对应的边，并为其每个编号分配1个需求单位。为节点1分配2个供应单元。找到最小成本流（使用例如NetworkX），并使用DFS将多米诺骨牌集转换为链