整理一下目前我取得的资讯，虽然说实在还蛮有限的。 首先我认为这个问题应该早就有相关的研究， 所以打算先找相关的文献，但无奈找不到正确的关键字，所以没进展。 ps. 『求关键字！』 後来，想说先从类似的问题开始找起， 发现 Round-robin tournament (循环赛) 其实蛮像的， 一样是 n 个队伍两两交手，且交手过得队伍不得再次交手。 但差别在於，Round-robin torunament 的每一场都是相同的竞赛， 并没有像是大地游戏有不同关卡的区分。 单纯只是要排 Round-robin tournament 的话基本上都有解， 但要把每一场对战对应到大地游戏的关卡时， 就会发现一支队伍参与同一个关卡不只一次的状况。 在大地游戏中，相较於同一个关卡玩两次， 遇到相同对手两次其实不是什麽太大不了的事， 所以我想从这个方向下手其实不太适合。 ---- 接着想说写程式来跑跑看，看能看能不能得出什麽规律。 若状况是 "n 关 m 小队" 的话， 假设每个小队每回合都必须参与，且玩遍所有关卡， 并且任意两个小队不会重复交手的情况下，不难发现： 1. 小队数 m 必为偶数 (否则每回合都有小队无法配对) 2. n*2 >= m (否则场地不足所有小队参赛) 3. n < m (否则关卡比其他小队数目还多) 於是就设计了一个跟原 po 概念一致的 DFS， 然後跑出了以下结果： *03/03 上午 update 1* --- 下方表格有误，因为 7 关 8 小队已确认有解。 目前猜测应该是我不应该事先决定好休关的位置。 本来以为休关的位置无所谓， 因为可以用交换 row 或 column 任意变换， 但实际上却不是如此。 今晚会 update 重跑的结果。 --- *03/03 22:50 update 2* --- 晚上依照前面的说法，拿掉事先决定好休关位置不会有问题的假设。 code 实在很难改，我改了一个多小时才完成... 改完之後试着跑了一下 "6 关 8 队"，程式居然跟我说有解... 我想这应该是程式有 bug 吧，但仔细验证了一遍，这组解居然是合法的! 实在太让人震惊了!!! XD | | A | B | C | D | E | F | |---------|-----|-----|-----|-----|-----|-----| | Round 1 | x | x | 0,1 | 2,3 | 4,5 | 6,7 | | Round 2 | x | x | 2,4 | 0,6 | 1,7 | 3,5 | | Round 3 | 0,2 | 1,3 | 5,6 | 4,7 | x | x | | Round 4 | 1,4 | 0,5 | 3,7 | x | 2,6 | x | | Round 5 | 3,6 | 2,7 | x | 1,5 | x | 0,4 | | Round 6 | 5,7 | 4,6 | x | x | 0,3 | 1,2 | 原来关键是，有两关要在相同的两个回合休关!! 顺便更新一下表格，但七关以上的我的程式跑不完.. | n\m | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | |-----|---|---|---|---|----|----|----|----| | 1 | o | | | | | | | | | 2 | | x | | | | | | | | 3 | | x | o | | | | | | | 4 | | | o | o | | | | | | 5 | | | x | x | o | | | | | 6 | | | | o | o | o | | | ps. 跟原先表格的差异只有 n=6, m=8 不同 --- 留空的部份表示没有满足前提， 而 o, x 当然就是表示有解、无解。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.34.7.189 当然有，DFS 跑的内容基本上就是在填 qaz00123 文末的表格。 ※ 编辑: tkcn 来自: 114.34.7.189 (03/02 20:06) 内容 update，目前的表格是错误的。 ※ 编辑: tkcn 来自: 114.34.7.189 (03/03 10:31) ※ 编辑: tkcn 来自: 114.34.7.189 (03/03 23:01) 内容再次 update，六关八队是有解的!! ※ 编辑: tkcn 来自: 114.34.7.189 (03/03 23:02)