整理一下目前我取得的資訊，雖然說實在還蠻有限的。 首先我認為這個問題應該早就有相關的研究， 所以打算先找相關的文獻，但無奈找不到正確的關鍵字，所以沒進展。 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)