通过递归和回溯找到所有可能的多米诺骨牌链

本文介绍了通过递归和回溯找到所有可能的多米诺骨牌链的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在研究一个挑战，我需要找到线性多米诺骨牌瓷砖的所有可能性。我了解递归的原理，但不了解如何将其转换为代码。如果有人可以用简单的步骤来解释问题（解决方案），然后我可以遵循并尝试对其进行编码。

I'm working on a challange where I need to find all possibilities for linear chains of dominoes tiles. I understand the principle of recursion but not how to translate it to code. If someone could maybe explain the problem (solution) in simple steps, which I could then follow and try to code them.

示例：

Example:

标题： [3/4] [5/6] [1/4] [1/6]

可能的链： [3/4]-[4/1]-[1/6]-[6/5]

可以翻转瓷砖。 （切换数字）

It's allowed to flip the tiles. (switching the numbers)

推荐答案

该过程非常简单：您从多米诺骨牌D的集合开始，而空链C

The process is very simple: you start with a collection of dominoes D, and an empty chain C.

for each domino in the collection: see if it can be added to the chain (either the chain is empty, or the first number is the same as the second number of the last domino in the chain. if it can, append the domino to the chain, then print this new chain as it is a solution, then call recursively with D - {domino} and C + {domino} repeat with the flipped domino

Java代码：

public class Domino { public final int a; public final int b; public Domino(int a, int b) { this.a = a; this.b = b; } public Domino flipped() { return new Domino(b, a); } @Override public String toString() { return "[" + a + "/" + b + "]"; } }

算法：

private static void listChains(List<Domino> chain, List<Domino> list) { for (int i = 0; i < list.size(); ++i) { Domino dom = list.get(i); if (canAppend(dom, chain)) { chain.add(dom); System.out.println(chain); Domino saved = list.remove(i); listChains(chain, list); list.add(i, saved); chain.remove(chain.size()-1); } dom = dom.flipped(); if (canAppend(dom, chain)) { chain.add(dom); System.out.println(chain); Domino saved = list.remove(i); listChains(chain, list); list.add(i, saved); chain.remove(chain.size()-1); } } } private static boolean canAppend(Domino dom, List<Domino> to) { return to.isEmpty() || to.get(to.size()-1).b == dom.a; }

您的示例：

public static void main(String... args) { List<Domino> list = new ArrayList<>(); // [3/4] [5/6] [1/4] [1/6] list.add(new Domino(3, 4)); list.add(new Domino(5, 6)); list.add(new Domino(1, 4)); list.add(new Domino(1, 6)); List<Domino> chain = new ArrayList<>(); listChains(chain, list); }