求助：基于2024/25欧冠瑞士制的36队赛事配对回溯算法实现

原代码核心问题 #

你的代码无法生成有效全量配对的原因在于：

• 顺序随机选择对手，未处理双向配对重复问题（比如会同时生成[A1,B1]和[B1,A1]，占用无效场次）
• 无回溯机制，随机选择可能提前耗尽后续球队的合法对手，导致出现undefined配对
• 未处理“当前选择导致死局”的场景，无法回退更换其他选项

回溯法核心思路 #

回溯法通过尝试-验证-回退的逻辑解决这类约束性配对问题：

1. 维护全局状态：跟踪每支球队的已交手对手、各档位已交手次数、剩余需赛场次
2. 优先处理未完成比赛的球队，为其遍历所有符合规则的潜在对手
3. 尝试配对后更新状态，递归继续处理剩余配对
4. 如果递归无法完成全部配对，则撤销当前配对（回溯），尝试下一个对手
5. 直到生成全部144场有效比赛

完整实现代码 #

const pots = [
    ["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9"],
    ["B1", "B2", "B3", "B4", "B5", "B6", "B7", "B8","B9"],
    ["C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8","C9"],
    ["D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8","D9"],
];

const REQUIRED_MATCHES_PER_POT = 2;
const TOTAL_MATCHES = 144;

// 初始化每支球队的状态
function initTeamState() {
    const state = {};
    pots.forEach((pot, potIndex) => {
        pot.forEach(team => {
            state[team] = {
                pot: potIndex,
                remainingMatches: 8, // 4档位×2场
                potCounts: [0, 0, 0, 0], // 各档位已交手次数统计
                opponents: new Set() // 已交手过的对手集合
            };
        });
    });
    return state;
}

// 回溯核心函数
function backtrack(matches, teamState) {
    // 终止条件：已生成全部有效比赛
    if (matches.length === TOTAL_MATCHES) {
        return [...matches];
    }

    // 找到第一个还有剩余比赛的球队
    const currentTeam = Object.keys(teamState).find(team => teamState[team].remainingMatches > 0);
    if (!currentTeam) return null;

    const currentState = teamState[currentTeam];

    // 遍历所有可能的合法对手
    for (const opponent of Object.keys(teamState)) {
        const oppState = teamState[opponent];

        // 过滤不符合规则的对手
        if (currentTeam === opponent) continue;
        if (currentState.opponents.has(opponent)) continue;
        if (oppState.remainingMatches === 0) continue;
        if (currentState.potCounts[oppState.pot] >= REQUIRED_MATCHES_PER_POT) continue;
        if (oppState.potCounts[currentState.pot] >= REQUIRED_MATCHES_PER_POT) continue;

        // 尝试配对：更新双方状态
        currentState.opponents.add(opponent);
        oppState.opponents.add(currentTeam);
        currentState.potCounts[oppState.pot]++;
        oppState.potCounts[currentState.pot]++;
        currentState.remainingMatches--;
        oppState.remainingMatches--;
        matches.push([currentTeam, opponent]);

        // 递归处理剩余配对
        const result = backtrack(matches, teamState);
        if (result) {
            return result; // 找到有效解，直接返回
        }

        // 回溯：撤销当前配对的状态更新
        matches.pop();
        currentState.remainingMatches++;
        oppState.remainingMatches++;
        currentState.potCounts[oppState.pot]--;
        oppState.potCounts[currentState.pot]--;
        currentState.opponents.delete(opponent);
        oppState.opponents.delete(currentTeam);
    }

    // 当前球队无合法对手可选，返回null触发回溯
    return null;
}

// 生成配对入口函数
function generateMatches() {
    const teamState = initTeamState();
    return backtrack([], teamState);
}

// 运行并验证结果
const matches = generateMatches();
console.log(`生成比赛总数：${matches.length}`);

// 验证每支球队的比赛是否符合规则
Object.keys(initTeamState()).forEach(team => {
    const teamMatches = matches.filter(m => m.includes(team));
    const potCounts = [0,0,0,0];
    teamMatches.forEach(m => {
        const opp = m[0] === team ? m[1] : m[0];
        const oppPot = pots.findIndex(pot => pot.includes(opp));
        potCounts[oppPot]++;
    });
    console.log(`${team}：共${teamMatches.length}场 | 各档位交手次数：${potCounts}`);
});

代码关键点说明 #

• initTeamState：初始化球队状态，明确每支球队的剩余比赛数、各档位交手限制和已交手对手
• backtrack：通过递归尝试所有合法配对，遇到死局则回退到上一步更换对手
• 约束检查：严格保证每支球队不会重复交手、同档位交手次数不超过2次、双方都有剩余比赛场次

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