生成一个table个满足条件的（比赛队伍分配）
Generate a table that meet conditions (tournament team assignation)
我希望 activity 生成满足特定条件的 table，如：
- 共有16组
- 有8个活动
- 共有8轮，一轮中一个队只能做一个activity
- 每个小组都需要做每个activity
- 每个 activity 必须容纳 2 组，不能再多了
- 我们希望一个小组再也不会遇到同一个小组（这样人们就可以看到最大数量的其他人:-)）
我们尝试在 Excel 中手动生成此内容，但总有一些组会再次见面。
我们尝试手动“生成列表”，但我们总是结束我们的团队相互交叉，例如本示例中的团队 7 和团队 9 交叉 3 次：
table generated so far
我虽然也许可以使用三维数组，但对我来说这似乎有点矫枉过正，而且肯定有一些已知的方法来处理这些情况。
一个（可能还有很多其他的）解决方案：
round\xtvt
1
2
3
4
5
6
7
8
1
AL
BK
CJ
DI
EP
FO
GN
HM
2
PK
AJ
BI
CH
DO
EN
FM
GL
3
OJ
PI
AH
BG
CN
DM
EL
FK
4
NI
OH
PG
AF
BM
CL
DK
EJ
5
BE
DG
LO
JM
FI
HK
CP
AN
6
CD
EF
MN
KL
GH
AB
IJ
OP
7
GM
LN
DF
EO
AK
JP
BH
CI
8
FH
CM
EK
NP
JL
GI
AO
BD
使用的算法：[Draw + Brute + Sudoku]
第 0 步 - 设置：
公式：
M3 : =IF(COUNTIFS($B:$I,$L3,$B:$I,M)=0,"",COUNTIFS($B:$I,$L3,$B:$I,M))
V3 : =IF(B3="","",COUNTIF($B:$I,B3))
AE3 : =COUNTIF($B3:$I3,AE)
并拖动到 table 的末尾。
第 1-4 步 - 使用（以前的答案版本）配对链接：
并将其映射到“填写团队对”table 第 1 行。我们将看到“xtvt 号码#”、“xtvt 重复观看”table 计数将自动完成.我们只需要确保没有重复配对的团队（都已完成配对和 xtvt）。
我所说的“映射”是指：在“填写团队配对”中输入团队配对table，然后观察“xtvt 重复观看”中的“填写”table。一旦填满“1”，我们就完成了。
结果（目前）：
第 5 步 - 暴力破解（填满 2 行）
注意到“xtvt 重复观看”table 中的类似差距，我将 AN @ xtvt 8，第 5 轮。
然后我把BM@xtvt 1,round5。但不能工作：
因为 BM 以前发生过。所以我们放 BE。对其他人也重复同样的事情：寻找相似的缺口，配对。做同样的另一对，我们将填补第5轮配对..
注意“xtvt repeat watch”table是主要关注点。 round6 使用的模式是：
恕我直言，这有点蛮力，但不够严谨。完成这一步，我们将得到：
任意重复xtvt/team，我们可以在“xtvt repeat watch”中看到‘2’table。如果我们得到 2，则意味着该团队之前已经打过 xtvt。
我想现在，我们可以看到这个步骤有点像填色本，使用的思维步骤与数独非常相似。
寻找可能的
- 对（在“xtvt repeat watch”中table）
- feed（“填写团队配对”中的团队配对table）
- 测试（输入配对后，确保它不会触发“xtvt repeat watch”中的'2'table）
- 对下一对重复（在同一轮中）。
第 6 步 - 类似数独的整理
至于最后2轮，必须一起做。只需一次填满两个，然后对其进行排序，这样就没有团队在同一轮中重复（就像数独一样）。总结一下：
只是为了验证，使用“Pair repetition chk”table并确保没有重复的团队配对。
我认为在某些时候不可能弄清楚这一点。很高兴与大家分享找到的解决方案..
希望对您有所帮助。
所以，尽管@p.phidot 已经提供了一个解决方案，我还是继续写了一个程序来解决它。我这样做主要是因为我在 Whosebug 上多次看到这个问题的各种版本，但很少有人能得到满意的答案。
这里提出的问题是更一般的体育联赛调度问题的一个版本，其中 Howell and Mitchell movements of Duplicate Bridge tournaments try to address different variants of this problem. It is in fact an obscure type Combinatorial Search problem that has had some work on mathematics and computer science papers over the years(see: 1, 2, and 3 似乎采用了类似于@p.phidot[=67 的方法=])
虽然有很多变体，但基本问题是在矩形内成对地安排（“安排”）一些事物（“团队”）（“游戏”、“比赛”或“事件”）调度时间（“回合”）和唯一资源（Bridge 中的“周期”、“字段”或“板”，或上述问题中的“activity”）的数组。这必须在以下常见的最小限制内完成：
- 球队不能自己比赛。
- 球队在同一轮比赛中不能超过一次。
- 在同一轮中不能多次使用/（播放）时间段。
通常，以下两个最小约束也很常见（尽管一些模糊的变体问题可能会改变这些）：
- 球队不能在同一时期比赛超过一次。
- 球队不能与同一支球队比赛超过一次。
在这些几乎通用的规则之后，还有大量额外的约束产生了这个问题的所有许多变体。上面问的问题就是我所说的“2x”问题，它有以下附加限制：
- 不允许轮空（即每支球队必须每轮比赛）。
- #Periods = #Rounds（即“方形”时间表）。
- #Teams = 2 x #Rounds（即“2x”）。
从数字上讲，这强制执行了一个附加规则，该规则也可以被视为用于编程和逻辑推理目的的伪约束：
- 每一轮都必须使用所有周期（即，没有空周期）。
虽然已知一般问题的某些变体对于某些尺寸是可解的，而其他变体是不可解的，但在大多数情况下，除了明显的数值冲突（例如太多 teams/not 足够的周期）每个变体差异很大，以至于通常不清楚哪些问题可以解决，哪些不能解决。这个例外就是我所说的“奇数规则”，因为如果参数（#Rounds，#Periods，#Teams）的 any 是奇数，那么它通常可以通过以下方式解决只需每轮轮换不同数量的团队和周期。然而，这并不适用于所有偶数，因为通过简单的轮换，球队的对手或周期将在中途重复。这意味着当所有参数都是偶数时，没有简单的旋转组合可以使用，如果它可以解决它变得更像数独游戏。
因此，我编写了这个程序来解决上述问题的版本，使用了 Branch and Bound 组合搜索技术的有限形式。好消息是它可以解决 OP 提出的具体问题（8 轮，8 节，16 队），这是它给出的答案：
period\round
0
1
2
3
4
5
6
7
0
0,1
3,5
2,4
6,8
7,12
10,14
9,13
11,15
1
3,4
0,2
1,5
7,9
6,14
8,15
11,12
10,13
2
2,5
1,4
0,3
12,15
8,13
7,11
6,10
9,14
3
6,7
8,10
9,11
0,4
1,15
3,13
2,14
5,12
4
8,9
6,11
7,10
13,14
0,5
1,12
4,15
2,3
5
10,11
12,14
13,15
1,2
3,9
0,6
5,8
4,7
6
12,13
9,15
8,14
3,10
2,11
4,5
0,7
1,6
7
14,15
7,13
6,12
5,11
4,10
2,9
1,3
0,8
（显然，我从零开始对所有内容进行编号）
现在是坏消息：实际上，它最多只能工作 9 轮。对于 10 轮及以上，它基本上永远 运行s（我让它 运行 几个小时没有完成）。因此，如果有人想将它用于更大的问题，则需要应用更多的优化（更新：11 轮大约一天完成。12 轮，我估计大约需要一年）。但请记住，奇数总是很容易手动解决，无论多大。
所以这是主要的求解器 class（所有代码都在 c# 中）：
class SLSx2Solver
{
public int NumTeams { get; internal set; }
public int NumRounds { get; internal set; }
public int NumPeriods { get; internal set; }
public Schedule State;
public SLSx2Solver(int teams, int rounds, int periods)
{
NumRounds = rounds;
NumPeriods = rounds;
NumTeams = 2 * rounds;
}
public Schedule SolveIt()
{
State = new Schedule(NumTeams, NumRounds, NumPeriods);
// To remove as many solution symmetries as possible before doing
// the BnB search, fully specify the first team's schedule arbitrarily
for (int round = 0; round < NumRounds; round++)
{
State.AddPairing(0, round + 1, round, round);
}
// test all possible assignments for each round, in order
bool solutionWasFound = SolveRemainingRounds(State, 0);
return State;
}
// Try all possible assignments for this round and any remaining rounds.
// Returns true if it was able to find a solution.
internal bool SolveRemainingRounds(Schedule state, int round)
{
// check if all rounds have been finished
if (round >= state.NumRounds)
{
return state.IsSolved;
}
if (state.RoundHasUnassignedTeams(round))
{
if (AssignRemainingPeriods(state, round, 0))
{
return true; // current assignments worked, so cascade it back
}
return false; // current path found no solutions
}
else
{
if(state.RoundIsComplete(round))
{
return SolveRemainingRounds(state, round + 1);
}
return false; // current path found no solutions
}
}
// Test all possible assignments for this period, then all remaining
// periods in the round. Returns true if a solution was found.
internal bool AssignRemainingPeriods(Schedule state, int round, int period) //, List<int> teams = null, int teamIdx = 0)
{
// Is the Round done?
if (state.RoundIsComplete(round))
{
// move to the next round
return SolveRemainingRounds(state, round + 1);
}
// there has to be unassinged teams
List<int> teams = state.RoundUnassignedTeams(round);
if (teams == null || teams.Count == 0)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned teams!");
}
// find the first unassigned Period, starting from (period)
do
{
if (state.RoundPeriod(round, period) == null) break;
period++;
} while (period < state.NumPeriods);
if (period >= state.NumPeriods)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned periods!");
}
// try all combinations of the unassigned teams, in order
for (int teamIdx = 0; teamIdx < teams.Count - 1; teamIdx++)
{
int team1 = teams[teamIdx];
// before we try all team2 combinations, make sure team1
// hasn't already used this period
if (!state.TeamUsedPeriod(team1, period))
{
// try all higher unassigned teams
for (int idx2 = teamIdx + 1; idx2 < teams.Count; idx2++)
{
int team2 = teams[idx2];
if (state.AddPairing(team1, team2, round, period))
{
// assign the next team pair
bool found = AssignRemainingPeriods(state, round, period + 1);
if (found)
{
return true;
}
else
{
// undo the period-assignment
state.UndoPairing(team1, team2, round, period);
}
}
}
}
}
// no complete assignments found on this branch
return false;
}
}
此代码在 Schedule 对象上实现品牌绑定样式递归，该对象以 4 维（轮次 x 周期 x Team1 vs Team2）稀疏数组“空心制表立方体”类型保存和跟踪调度分配我发现对解决 8-queens problems 的类型很有用的结构（即，一个对象在每个维度中出现一次）。 class 的代码在这里：
class Schedule
{
// The public-readable attributes (immutable)
public int NumTeams { get; internal set; } // Max 32
public int NumRounds { get; internal set; } // Max 32
public int NumPeriods { get; internal set; }
public Schedule(int teams, int maxRounds, int periods)
{
NumTeams = teams;
NumRounds = maxRounds;
NumPeriods = periods;
// initialize the search-state
// (could make this a 4-dimensional array, but it would be HUGE)
roundXperiod = new Assignment[NumRounds, NumPeriods];
periodXteam = new Assignment[NumPeriods, NumTeams];
roundXteam = new Assignment[NumRounds, NumTeams];
teamXteam = new Assignment[NumTeams, NumTeams];
periodsAssignedCount = new int[NumRounds];
teamsAssignedCount = new int[NumRounds];
// init the moves-log stack
assignments = new Stack<Assignment>((NumTeams + 1 * NumRounds) / 2);
}
#region Internal Assignment-tracking structures
Assignment[,] roundXperiod;
Assignment[,] periodXteam;
Assignment[,] roundXteam;
Assignment[,] teamXteam; // [team1,team2] | team1 < team2
int[] periodsAssignedCount;
int[] teamsAssignedCount;
int roundsComplete;
#endregion
#region State-checking public interface
public bool RoundHasUnassignedTeams(int round)
{
return teamsAssignedCount[round] < NumTeams;
}
public bool RoundIsComplete(int round)
{
if (periodsAssignedCount[round] == NumPeriods
&& teamsAssignedCount[round] == NumTeams)
return true;
else
return false;
}
public bool IsSolved { get { return (roundsComplete == NumRounds); } }
public Assignment RoundPeriod(int round, int period)
{
return roundXperiod[round, period];
}
public bool TeamUsedPeriod(int team, int period)
{
return (periodXteam[period, team] != null);
}
#endregion
#region public List Generation
public List<int> RoundUnassignedTeams(int round)
{
List<int> lst = new List<int>();
for (int t = 0; t < NumTeams; t++)
{
if (roundXteam[round, t] == null)
lst.Add(t);
}
return lst;
}
public List<int> RoundUnassignedPeriods(int round)
{
List<int> lst = new List<int>();
for (int p = 0; p < NumPeriods; p++)
{
if (roundXperiod[round, p] == null)
lst.Add(p);
}
return lst;
}
#endregion
#region Schedule Assignment public interface
public bool AddPairing(int team1, int team2, int round, int period)
{
Assignment move = new Assignment(team1, team2, round, period);
return Push(move);
}
public void UndoPairing(int team1, int team2, int round, int period)
{
// do some validity checking
Assignment move = Peek();
if (move == null
|| move.Team1 != team1
|| move.Round != round
|| move.Team2 != team2
|| move.Period != period
)
throw new Exception("Schedule.UndoPairing: does not match last move!");
Pop();
return;
}
#endregion
#region Schedule-assignment internal implementation
Stack<Assignment> assignments;
// Adds an assignment to the search state, returns false if the
// assignmment was invalid. (All of the delta-logic is here)
bool Push(Assignment evnt)
{
/* Everything needs to be checked first */
// Has team1 already been assigned?
if (roundXteam[evnt.Round, evnt.Team1] != null) return false;
// Has team1 already used this period?
if (periodXteam[evnt.Period, evnt.Team1] != null) return false;
// Is the round-period unassigned?
if (roundXperiod[evnt.Round, evnt.Period] != null) return false;
// Has team2 already used this period?
if (periodXteam[evnt.Period, evnt.Team2] != null) return false;
// Is team2 unassinged for this round?
if (roundXteam[evnt.Round, evnt.Team2] != null) return false;
// Have these two teams already played each other?
if (teamXteam[evnt.Team1, evnt.Team2] != null) return false;
// Add the move to the stack
assignments.Push(evnt);
/* Make all changes to the data-structures */
roundXteam[evnt.Round, evnt.Team1] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team1] = evnt;
roundXperiod[evnt.Round, evnt.Period] = evnt;
periodsAssignedCount[evnt.Round]++;
roundXteam[evnt.Round, evnt.Team2] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team2] = evnt;
teamXteam[evnt.Team1, evnt.Team2] = evnt;
if (RoundIsComplete(evnt.Round)) roundsComplete++;
return true;
}
// UnDo whatever the last move (on top of the stack) was
// (this is where all of the state-UnDo logic needs to be)
void Pop()
{
Assignment evnt = assignments.Pop();
/* validate first */
if (roundXteam[evnt.Round, evnt.Team1] == null
|| roundXteam[evnt.Round, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team1] does not match!");
if (periodXteam[evnt.Period, evnt.Team1] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team1] does not match!");
// Is the round-period matching?
if (roundXperiod[evnt.Round, evnt.Period] == null
|| roundXperiod[evnt.Round, evnt.Period] != evnt)
throw new Exception("Schedule.Pop: periodAssignments does not match!");
if (periodXteam[evnt.Period, evnt.Team2] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team2] does not match!");
if (roundXteam[evnt.Round, evnt.Team2] == null
|| roundXteam[evnt.Round, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team2] does not match!");
if (teamXteam[evnt.Team1, evnt.Team2] == null
|| teamXteam[evnt.Team1, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: team1VsTeam2[Team1,Team2] does not match!");
// Implement UnDO
bool wasComplete = RoundIsComplete(evnt.Round);
roundXteam[evnt.Round, evnt.Team1] = null;
teamsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team1] = null;
roundXperiod[evnt.Round, evnt.Period] = null;
periodsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team2] = null;
roundXteam[evnt.Round, evnt.Team2] = null;
teamsAssignedCount[evnt.Round]--;
teamXteam[evnt.Team1, evnt.Team2] = null;
if (wasComplete
&& !RoundIsComplete(evnt.Round)) roundsComplete--;
return;
}
Assignment Peek()
{
return assignments.Peek();
}
#endregion
public override string ToString()
{
string str = "P \ R->";
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + r.ToString();
}
str += "\n";
for (int p = 0; p < NumPeriods; p++)
{
str += p.ToString();
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + ((roundXperiod[r, p]?.PairString)??"");
}
str += "\n";
}
return str;
}
}
最后，上面的两个 classes 都使用 Assignment 对象封装了在特定回合和时间段内相互比赛的两支球队：
public class Assignment
{
// Create a schedule pairing assignment
public Assignment(int team1, int team2, int round, int period)
{
if (team2 == -1 || period == -1)
throw new Exception("Cannot create a Pairing Assingment if team2 or period = -1");
// by convetion, Team1 must always be less than Team2
if (team1 < team2)
{
Team1 = team1;
Team2 = team2;
}
else
{
Team1 = team2;
Team2 = team1;
}
Round = round;
Period = period;
}
public int Team1 { get; internal set; }
public int Team2 { get; internal set; }
public int Round { get; internal set; }
public int Period { get; internal set; }
public string PairString
{
get
{
return Team1.ToString() + "," + Team2.ToString();
}
}
}
下面是我的表单中的一些代码，说明了如何使用求解器 class:
listBox1.Items.Clear();
listBox1.Items.Add(" ... running ...");
SLSx2Solver slv = new SLSx2Solver(rounds);
Schedule sol = slv.SolveIt();
if (!sol.IsSolved)
{
MessageBox.Show("No Solution Found.", "Solution Result:", MessageBoxButtons.OK, MessageBoxIcon.Information);
return;
}
// display the results
listBox1.Items.Clear();
string str = sol.ToString();
foreach(string s in str.Split('\n'))
{
listBox1.Items.Add(s);
}
NumTeams = teams;
我希望 activity 生成满足特定条件的 table，如：
- 共有16组
- 有8个活动
- 共有8轮，一轮中一个队只能做一个activity
- 每个小组都需要做每个activity
- 每个 activity 必须容纳 2 组，不能再多了
- 我们希望一个小组再也不会遇到同一个小组（这样人们就可以看到最大数量的其他人:-)）
我们尝试在 Excel 中手动生成此内容，但总有一些组会再次见面。
我们尝试手动“生成列表”，但我们总是结束我们的团队相互交叉，例如本示例中的团队 7 和团队 9 交叉 3 次： table generated so far
我虽然也许可以使用三维数组，但对我来说这似乎有点矫枉过正，而且肯定有一些已知的方法来处理这些情况。
一个（可能还有很多其他的）解决方案：
| round\xtvt | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | AL | BK | CJ | DI | EP | FO | GN | HM |
| 2 | PK | AJ | BI | CH | DO | EN | FM | GL |
| 3 | OJ | PI | AH | BG | CN | DM | EL | FK |
| 4 | NI | OH | PG | AF | BM | CL | DK | EJ |
| 5 | BE | DG | LO | JM | FI | HK | CP | AN |
| 6 | CD | EF | MN | KL | GH | AB | IJ | OP |
| 7 | GM | LN | DF | EO | AK | JP | BH | CI |
| 8 | FH | CM | EK | NP | JL | GI | AO | BD |
使用的算法：[Draw + Brute + Sudoku]
第 0 步 - 设置：
公式：
M3 : =IF(COUNTIFS($B:$I,$L3,$B:$I,M)=0,"",COUNTIFS($B:$I,$L3,$B:$I,M))
V3 : =IF(B3="","",COUNTIF($B:$I,B3))
AE3 : =COUNTIF($B3:$I3,AE)
并拖动到 table 的末尾。
第 1-4 步 - 使用（以前的答案版本）配对链接：
并将其映射到“填写团队对”table 第 1 行。我们将看到“xtvt 号码#”、“xtvt 重复观看”table 计数将自动完成.我们只需要确保没有重复配对的团队（都已完成配对和 xtvt）。
我所说的“映射”是指：在“填写团队配对”中输入团队配对table，然后观察“xtvt 重复观看”中的“填写”table。一旦填满“1”，我们就完成了。
结果（目前）：
第 5 步 - 暴力破解（填满 2 行）
注意到“xtvt 重复观看”table 中的类似差距，我将 AN @ xtvt 8，第 5 轮。
然后我把BM@xtvt 1,round5。但不能工作：
注意“xtvt repeat watch”table是主要关注点。 round6 使用的模式是：
恕我直言，这有点蛮力，但不够严谨。完成这一步，我们将得到：
任意重复xtvt/team，我们可以在“xtvt repeat watch”中看到‘2’table。如果我们得到 2，则意味着该团队之前已经打过 xtvt。
我想现在，我们可以看到这个步骤有点像填色本，使用的思维步骤与数独非常相似。
寻找可能的
- 对（在“xtvt repeat watch”中table）
- feed（“填写团队配对”中的团队配对table）
- 测试（输入配对后，确保它不会触发“xtvt repeat watch”中的'2'table）
- 对下一对重复（在同一轮中）。
第 6 步 - 类似数独的整理
至于最后2轮，必须一起做。只需一次填满两个，然后对其进行排序，这样就没有团队在同一轮中重复（就像数独一样）。总结一下：
只是为了验证，使用“Pair repetition chk”table并确保没有重复的团队配对。
我认为在某些时候不可能弄清楚这一点。很高兴与大家分享找到的解决方案..
希望对您有所帮助。
所以，尽管@p.phidot 已经提供了一个解决方案，我还是继续写了一个程序来解决它。我这样做主要是因为我在 Whosebug 上多次看到这个问题的各种版本，但很少有人能得到满意的答案。
这里提出的问题是更一般的体育联赛调度问题的一个版本，其中 Howell and Mitchell movements of Duplicate Bridge tournaments try to address different variants of this problem. It is in fact an obscure type Combinatorial Search problem that has had some work on mathematics and computer science papers over the years(see: 1, 2, and 3 似乎采用了类似于@p.phidot[=67 的方法=])
虽然有很多变体，但基本问题是在矩形内成对地安排（“安排”）一些事物（“团队”）（“游戏”、“比赛”或“事件”）调度时间（“回合”）和唯一资源（Bridge 中的“周期”、“字段”或“板”，或上述问题中的“activity”）的数组。这必须在以下常见的最小限制内完成：
- 球队不能自己比赛。
- 球队在同一轮比赛中不能超过一次。
- 在同一轮中不能多次使用/（播放）时间段。
通常，以下两个最小约束也很常见（尽管一些模糊的变体问题可能会改变这些）：
- 球队不能在同一时期比赛超过一次。
- 球队不能与同一支球队比赛超过一次。
在这些几乎通用的规则之后，还有大量额外的约束产生了这个问题的所有许多变体。上面问的问题就是我所说的“2x”问题，它有以下附加限制：
- 不允许轮空（即每支球队必须每轮比赛）。
- #Periods = #Rounds（即“方形”时间表）。
- #Teams = 2 x #Rounds（即“2x”）。
从数字上讲，这强制执行了一个附加规则，该规则也可以被视为用于编程和逻辑推理目的的伪约束：
- 每一轮都必须使用所有周期（即，没有空周期）。
虽然已知一般问题的某些变体对于某些尺寸是可解的，而其他变体是不可解的，但在大多数情况下，除了明显的数值冲突（例如太多 teams/not 足够的周期）每个变体差异很大，以至于通常不清楚哪些问题可以解决，哪些不能解决。这个例外就是我所说的“奇数规则”，因为如果参数（#Rounds，#Periods，#Teams）的 any 是奇数，那么它通常可以通过以下方式解决只需每轮轮换不同数量的团队和周期。然而，这并不适用于所有偶数，因为通过简单的轮换，球队的对手或周期将在中途重复。这意味着当所有参数都是偶数时，没有简单的旋转组合可以使用，如果它可以解决它变得更像数独游戏。
因此，我编写了这个程序来解决上述问题的版本，使用了 Branch and Bound 组合搜索技术的有限形式。好消息是它可以解决 OP 提出的具体问题（8 轮，8 节，16 队），这是它给出的答案：
| period\round | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0,1 | 3,5 | 2,4 | 6,8 | 7,12 | 10,14 | 9,13 | 11,15 |
| 1 | 3,4 | 0,2 | 1,5 | 7,9 | 6,14 | 8,15 | 11,12 | 10,13 |
| 2 | 2,5 | 1,4 | 0,3 | 12,15 | 8,13 | 7,11 | 6,10 | 9,14 |
| 3 | 6,7 | 8,10 | 9,11 | 0,4 | 1,15 | 3,13 | 2,14 | 5,12 |
| 4 | 8,9 | 6,11 | 7,10 | 13,14 | 0,5 | 1,12 | 4,15 | 2,3 |
| 5 | 10,11 | 12,14 | 13,15 | 1,2 | 3,9 | 0,6 | 5,8 | 4,7 |
| 6 | 12,13 | 9,15 | 8,14 | 3,10 | 2,11 | 4,5 | 0,7 | 1,6 |
| 7 | 14,15 | 7,13 | 6,12 | 5,11 | 4,10 | 2,9 | 1,3 | 0,8 |
（显然，我从零开始对所有内容进行编号）
现在是坏消息：实际上，它最多只能工作 9 轮。对于 10 轮及以上，它基本上永远 运行s（我让它 运行 几个小时没有完成）。因此，如果有人想将它用于更大的问题，则需要应用更多的优化（更新：11 轮大约一天完成。12 轮，我估计大约需要一年）。但请记住，奇数总是很容易手动解决，无论多大。
所以这是主要的求解器 class（所有代码都在 c# 中）：
class SLSx2Solver
{
public int NumTeams { get; internal set; }
public int NumRounds { get; internal set; }
public int NumPeriods { get; internal set; }
public Schedule State;
public SLSx2Solver(int teams, int rounds, int periods)
{
NumRounds = rounds;
NumPeriods = rounds;
NumTeams = 2 * rounds;
}
public Schedule SolveIt()
{
State = new Schedule(NumTeams, NumRounds, NumPeriods);
// To remove as many solution symmetries as possible before doing
// the BnB search, fully specify the first team's schedule arbitrarily
for (int round = 0; round < NumRounds; round++)
{
State.AddPairing(0, round + 1, round, round);
}
// test all possible assignments for each round, in order
bool solutionWasFound = SolveRemainingRounds(State, 0);
return State;
}
// Try all possible assignments for this round and any remaining rounds.
// Returns true if it was able to find a solution.
internal bool SolveRemainingRounds(Schedule state, int round)
{
// check if all rounds have been finished
if (round >= state.NumRounds)
{
return state.IsSolved;
}
if (state.RoundHasUnassignedTeams(round))
{
if (AssignRemainingPeriods(state, round, 0))
{
return true; // current assignments worked, so cascade it back
}
return false; // current path found no solutions
}
else
{
if(state.RoundIsComplete(round))
{
return SolveRemainingRounds(state, round + 1);
}
return false; // current path found no solutions
}
}
// Test all possible assignments for this period, then all remaining
// periods in the round. Returns true if a solution was found.
internal bool AssignRemainingPeriods(Schedule state, int round, int period) //, List<int> teams = null, int teamIdx = 0)
{
// Is the Round done?
if (state.RoundIsComplete(round))
{
// move to the next round
return SolveRemainingRounds(state, round + 1);
}
// there has to be unassinged teams
List<int> teams = state.RoundUnassignedTeams(round);
if (teams == null || teams.Count == 0)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned teams!");
}
// find the first unassigned Period, starting from (period)
do
{
if (state.RoundPeriod(round, period) == null) break;
period++;
} while (period < state.NumPeriods);
if (period >= state.NumPeriods)
{
throw new Exception("AssignRemainingPeriods(" + round.ToString() + "): no unassigned periods!");
}
// try all combinations of the unassigned teams, in order
for (int teamIdx = 0; teamIdx < teams.Count - 1; teamIdx++)
{
int team1 = teams[teamIdx];
// before we try all team2 combinations, make sure team1
// hasn't already used this period
if (!state.TeamUsedPeriod(team1, period))
{
// try all higher unassigned teams
for (int idx2 = teamIdx + 1; idx2 < teams.Count; idx2++)
{
int team2 = teams[idx2];
if (state.AddPairing(team1, team2, round, period))
{
// assign the next team pair
bool found = AssignRemainingPeriods(state, round, period + 1);
if (found)
{
return true;
}
else
{
// undo the period-assignment
state.UndoPairing(team1, team2, round, period);
}
}
}
}
}
// no complete assignments found on this branch
return false;
}
}
此代码在 Schedule 对象上实现品牌绑定样式递归，该对象以 4 维（轮次 x 周期 x Team1 vs Team2）稀疏数组“空心制表立方体”类型保存和跟踪调度分配我发现对解决 8-queens problems 的类型很有用的结构（即，一个对象在每个维度中出现一次）。 class 的代码在这里：
class Schedule
{
// The public-readable attributes (immutable)
public int NumTeams { get; internal set; } // Max 32
public int NumRounds { get; internal set; } // Max 32
public int NumPeriods { get; internal set; }
public Schedule(int teams, int maxRounds, int periods)
{
NumTeams = teams;
NumRounds = maxRounds;
NumPeriods = periods;
// initialize the search-state
// (could make this a 4-dimensional array, but it would be HUGE)
roundXperiod = new Assignment[NumRounds, NumPeriods];
periodXteam = new Assignment[NumPeriods, NumTeams];
roundXteam = new Assignment[NumRounds, NumTeams];
teamXteam = new Assignment[NumTeams, NumTeams];
periodsAssignedCount = new int[NumRounds];
teamsAssignedCount = new int[NumRounds];
// init the moves-log stack
assignments = new Stack<Assignment>((NumTeams + 1 * NumRounds) / 2);
}
#region Internal Assignment-tracking structures
Assignment[,] roundXperiod;
Assignment[,] periodXteam;
Assignment[,] roundXteam;
Assignment[,] teamXteam; // [team1,team2] | team1 < team2
int[] periodsAssignedCount;
int[] teamsAssignedCount;
int roundsComplete;
#endregion
#region State-checking public interface
public bool RoundHasUnassignedTeams(int round)
{
return teamsAssignedCount[round] < NumTeams;
}
public bool RoundIsComplete(int round)
{
if (periodsAssignedCount[round] == NumPeriods
&& teamsAssignedCount[round] == NumTeams)
return true;
else
return false;
}
public bool IsSolved { get { return (roundsComplete == NumRounds); } }
public Assignment RoundPeriod(int round, int period)
{
return roundXperiod[round, period];
}
public bool TeamUsedPeriod(int team, int period)
{
return (periodXteam[period, team] != null);
}
#endregion
#region public List Generation
public List<int> RoundUnassignedTeams(int round)
{
List<int> lst = new List<int>();
for (int t = 0; t < NumTeams; t++)
{
if (roundXteam[round, t] == null)
lst.Add(t);
}
return lst;
}
public List<int> RoundUnassignedPeriods(int round)
{
List<int> lst = new List<int>();
for (int p = 0; p < NumPeriods; p++)
{
if (roundXperiod[round, p] == null)
lst.Add(p);
}
return lst;
}
#endregion
#region Schedule Assignment public interface
public bool AddPairing(int team1, int team2, int round, int period)
{
Assignment move = new Assignment(team1, team2, round, period);
return Push(move);
}
public void UndoPairing(int team1, int team2, int round, int period)
{
// do some validity checking
Assignment move = Peek();
if (move == null
|| move.Team1 != team1
|| move.Round != round
|| move.Team2 != team2
|| move.Period != period
)
throw new Exception("Schedule.UndoPairing: does not match last move!");
Pop();
return;
}
#endregion
#region Schedule-assignment internal implementation
Stack<Assignment> assignments;
// Adds an assignment to the search state, returns false if the
// assignmment was invalid. (All of the delta-logic is here)
bool Push(Assignment evnt)
{
/* Everything needs to be checked first */
// Has team1 already been assigned?
if (roundXteam[evnt.Round, evnt.Team1] != null) return false;
// Has team1 already used this period?
if (periodXteam[evnt.Period, evnt.Team1] != null) return false;
// Is the round-period unassigned?
if (roundXperiod[evnt.Round, evnt.Period] != null) return false;
// Has team2 already used this period?
if (periodXteam[evnt.Period, evnt.Team2] != null) return false;
// Is team2 unassinged for this round?
if (roundXteam[evnt.Round, evnt.Team2] != null) return false;
// Have these two teams already played each other?
if (teamXteam[evnt.Team1, evnt.Team2] != null) return false;
// Add the move to the stack
assignments.Push(evnt);
/* Make all changes to the data-structures */
roundXteam[evnt.Round, evnt.Team1] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team1] = evnt;
roundXperiod[evnt.Round, evnt.Period] = evnt;
periodsAssignedCount[evnt.Round]++;
roundXteam[evnt.Round, evnt.Team2] = evnt;
teamsAssignedCount[evnt.Round]++;
periodXteam[evnt.Period, evnt.Team2] = evnt;
teamXteam[evnt.Team1, evnt.Team2] = evnt;
if (RoundIsComplete(evnt.Round)) roundsComplete++;
return true;
}
// UnDo whatever the last move (on top of the stack) was
// (this is where all of the state-UnDo logic needs to be)
void Pop()
{
Assignment evnt = assignments.Pop();
/* validate first */
if (roundXteam[evnt.Round, evnt.Team1] == null
|| roundXteam[evnt.Round, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team1] does not match!");
if (periodXteam[evnt.Period, evnt.Team1] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team1] does not match!");
// Is the round-period matching?
if (roundXperiod[evnt.Round, evnt.Period] == null
|| roundXperiod[evnt.Round, evnt.Period] != evnt)
throw new Exception("Schedule.Pop: periodAssignments does not match!");
if (periodXteam[evnt.Period, evnt.Team2] == null
|| periodXteam[evnt.Period, evnt.Team1] != evnt)
throw new Exception("Schedule.Pop: periodTeams[Period,Team2] does not match!");
if (roundXteam[evnt.Round, evnt.Team2] == null
|| roundXteam[evnt.Round, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: teamAssignment[Team2] does not match!");
if (teamXteam[evnt.Team1, evnt.Team2] == null
|| teamXteam[evnt.Team1, evnt.Team2] != evnt)
throw new Exception("Schedule.Pop: team1VsTeam2[Team1,Team2] does not match!");
// Implement UnDO
bool wasComplete = RoundIsComplete(evnt.Round);
roundXteam[evnt.Round, evnt.Team1] = null;
teamsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team1] = null;
roundXperiod[evnt.Round, evnt.Period] = null;
periodsAssignedCount[evnt.Round]--;
periodXteam[evnt.Period, evnt.Team2] = null;
roundXteam[evnt.Round, evnt.Team2] = null;
teamsAssignedCount[evnt.Round]--;
teamXteam[evnt.Team1, evnt.Team2] = null;
if (wasComplete
&& !RoundIsComplete(evnt.Round)) roundsComplete--;
return;
}
Assignment Peek()
{
return assignments.Peek();
}
#endregion
public override string ToString()
{
string str = "P \ R->";
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + r.ToString();
}
str += "\n";
for (int p = 0; p < NumPeriods; p++)
{
str += p.ToString();
for (int r = 0; r < NumRounds; r++)
{
str += "\t" + ((roundXperiod[r, p]?.PairString)??"");
}
str += "\n";
}
return str;
}
}
最后，上面的两个 classes 都使用 Assignment 对象封装了在特定回合和时间段内相互比赛的两支球队：
public class Assignment
{
// Create a schedule pairing assignment
public Assignment(int team1, int team2, int round, int period)
{
if (team2 == -1 || period == -1)
throw new Exception("Cannot create a Pairing Assingment if team2 or period = -1");
// by convetion, Team1 must always be less than Team2
if (team1 < team2)
{
Team1 = team1;
Team2 = team2;
}
else
{
Team1 = team2;
Team2 = team1;
}
Round = round;
Period = period;
}
public int Team1 { get; internal set; }
public int Team2 { get; internal set; }
public int Round { get; internal set; }
public int Period { get; internal set; }
public string PairString
{
get
{
return Team1.ToString() + "," + Team2.ToString();
}
}
}
下面是我的表单中的一些代码，说明了如何使用求解器 class:
listBox1.Items.Clear();
listBox1.Items.Add(" ... running ...");
SLSx2Solver slv = new SLSx2Solver(rounds);
Schedule sol = slv.SolveIt();
if (!sol.IsSolved)
{
MessageBox.Show("No Solution Found.", "Solution Result:", MessageBoxButtons.OK, MessageBoxIcon.Information);
return;
}
// display the results
listBox1.Items.Clear();
string str = sol.ToString();
foreach(string s in str.Split('\n'))
{
listBox1.Items.Add(s);
}
NumTeams = teams;