如何用C#递归实现多米诺骨牌链组合生成？

问题说明 #

输入规则：

• 首行输入骨牌数量n
• 后续n行输入多米诺骨牌（格式如1 2）
• 末行输入每条链的骨牌数x

输出要求：

• 输出所有符合规则的骨牌链：链中前一骨牌的第二个数字等于后一骨牌的第一个数字，且骨牌不重复使用
• 无符合条件的链时输出N/A
• 仅允许引用System命名空间

解决思路 #

递归核心逻辑：

1. 递归基例：当当前链的长度等于目标长度x时，输出该链并返回
2. 递归过程：
   • 遍历所有未使用的骨牌
   • 如果当前链为空，直接选择该骨牌加入链，标记为已使用，递归调用
   • 如果当前链不为空，判断骨牌的第一个数字是否等于链最后一个骨牌的第二个数字，符合条件则加入链，标记为已使用，递归调用
3. 回溯：递归返回后，取消骨牌的已使用标记，从当前链中移除该骨牌，尝试其他可能的骨牌选择

完整代码 #

using System;
using System.Collections.Generic;

class DominoChainGenerator
{
    static List<Tuple<int, int>> dominoes = new List<Tuple<int, int>>();
    static bool[] used;
    static int targetLength;
    static bool hasValidChain = false;

    static void Main()
    {
        // 读取输入
        int n = int.Parse(Console.ReadLine());
        for (int i = 0; i < n; i++)
        {
            string[] parts = Console.ReadLine().Split();
            int a = int.Parse(parts[0]);
            int b = int.Parse(parts[1]);
            dominoes.Add(Tuple.Create(a, b));
        }
        targetLength = int.Parse(Console.ReadLine());

        used = new bool[n];
        List<Tuple<int, int>> currentChain = new List<Tuple<int, int>>();

        // 尝试所有可能的起始骨牌
        for (int i = 0; i < n; i++)
        {
            if (!used[i])
            {
                used[i] = true;
                currentChain.Add(dominoes[i]);
                GenerateChains(currentChain, dominoes[i].Item2);
                currentChain.RemoveAt(currentChain.Count - 1);
                used[i] = false;
            }
        }

        // 无有效链时输出N/A
        if (!hasValidChain)
        {
            Console.WriteLine("N/A");
        }
    }

    static void GenerateChains(List<Tuple<int, int>> currentChain, int lastNumber)
    {
        // 递归终止条件：链长度达标
        if (currentChain.Count == targetLength)
        {
            PrintChain(currentChain);
            hasValidChain = true;
            return;
        }

        // 遍历所有未使用的骨牌
        for (int i = 0; i < dominoes.Count; i++)
        {
            if (!used[i])
            {
                var domino = dominoes[i];
                // 匹配链的末尾数字
                if (domino.Item1 == lastNumber)
                {
                    used[i] = true;
                    currentChain.Add(domino);
                    // 递归生成后续链段
                    GenerateChains(currentChain, domino.Item2);
                    // 回溯：恢复状态
                    currentChain.RemoveAt(currentChain.Count - 1);
                    used[i] = false;
                }
            }
        }
    }

    static void PrintChain(List<Tuple<int, int>> chain)
    {
        for (int i = 0; i < chain.Count; i++)
        {
            if (i > 0)
            {
                Console.Write(" -> ");
            }
            Console.Write($"{chain[i].Item1} {chain[i].Item2}");
        }
        Console.WriteLine();
    }
}

关键部分解释 #

1. 输入处理：将骨牌存储为Tuple<int, int>列表，初始化时直接创建空列表，从根源避免空指针异常
2. 递归基例：明确以currentChain.Count == targetLength作为终止条件，修正了之前的基例错误
3. 回溯机制：递归返回后恢复骨牌的未使用状态，确保所有可能的骨牌组合都被遍历，解决了结果不全的问题
4. 起始骨牌遍历：主函数中遍历所有骨牌作为链的起点，不会遗漏任何可能的有效链
5. 状态标记：用布尔数组used记录骨牌是否被使用，操作高效且逻辑清晰

内容的提问来源于stack exchange，提问作者Bro