T = the team under consideration (T = 1, 2, 3 or 4)
Game scores:
3
1 3 7 5
3 4 0 8
2 4 2 2
Game scores are stored in 2 4x4 arrays:
score1[1:4][1:4]: score2[1:4][1:4]:
0 -1 7 -1 0 -1 5 -1
0 0 -1 2 0 0 -1 2
0 0 0 0 0 0 0 8
0 0 0 0 0 0 0 0
^ ^
| |
Score of team 1 in game Score of team 2 in game
(-1 mean: game has not been played)
|
It's easy to determine the winner if we had a full schedule:
int winner( int score1[5][5], int score2[5][5] )
{
int totPoints[5] = {0,0,0,0,0}; // totPoints[i] = total pts of team i
for ( int i = 1; i <= 4; i++ )
for ( int j = i+1; j <= 4; j++ )
{
if ( score1[i][j] > score2[i][j] )
totPoints[i] += 3; // Team 1 won
else if ( score1[i][j] < score2[i][j] )
totPoints[j] += 3; // Team 2 won
else
{ // Tie game
totPoints[i] += 1;
totPoints[j] += 1;
}
}
winner = team with highest total points
If multiway tie --> return 0 (no winner)
}
|
Problem: we need to fill in a full schedule --- Solution: back tracking
|
void Search( stepNum, currState, stepsToSol[] )
{
if ( stepNum >= MAXSTEPS allowed )
return; // Dead end, try next branch
if ( currState is a solution )
{ print( currState ); // Print solution
print( stepsToSol[ ] ); // Print steps to achieve solution
if ( you only need 1 solution )
exit(0);
else
return; // Continue to find other solutions...
}
// Make one step and search further
for ( every possible SINGLE step S in the current state )
{ currState = applyStep(S, currState)
add S to stepsToSol[]
Search( stepNum+1, (new) currState, stepsToSol[] );
// Walk back the previous step when Search returns
currState = removeStep(S, currState)
remove S from stepsToSol[];
} // Loop back --> try next step S
}
|
// score1: scores from team 1, score2: scores from team 2
// T = team requested in J5 (find # wins by this team)
void simPlay( int score1[5][5], int score2[5][5], int T )
{
if ( stepNum >= MAXSTEPS allowed )
return; // Dead end, try next branch
if ( currState is a solution )
{ print( currState ); // Print solution
print( stepsToSol[ ] ); // Print steps to achieve solution
if ( you only need 1 solution )
exit(0);
else
return; // Continue to find other solutions...
}
// Make one step and search further
for ( every possible SINGLE step S in the current state )
{ currState = applyStep(S, currState)
add S to stepsToSol[]
Search( stepNum+1, (new) currState, stepsToSol[] );
// Walk back the previous step when Search returns
currState = removeStep(S, currState)
remove S from stepsToSol[];
} // Loop back --> try next step S
}
|
void simPlay( int score1[5][5], int score2[5][5], int T )
{
|
int nCases = 0;
void simPlay( int score1[5][5], int score2[5][5], int T )
{
if ( score1[][] and score2[][] have a full schedule )
{
if ( winner(score1, score2) == T )
nCases++; // One more case where team T wins
return; // Find all winning score boards
}
// Make one step and search further
for ( every possible SINGLE step S in the current state )
{ currState = applyStep(S, currState)
add S to stepsToSol[]
Search( stepNum+1, (new) currState, stepsToSol[] );
// Walk back the previous step when Search returns
currState = removeStep(S, currState)
remove S from stepsToSol[];
} // Loop back --> try next step S
|
int nCases = 0;
void simPlay( int score1[5][5], int score2[5][5], int T )
{
if ( score1[][] and score2[][] have a full schedule )
{
if ( winner(score1, score2) == T )
nCases++; // One more case where team T wins
return; // Find all winning score boards
}
// Fill in 1 unplayed game and recurse
for ( int i = 1; i <= 4; i++ )
{
for ( int j = i+1; j <= 4; j++ )
if ( score1[i][j] == -1 || score2[i][j] == -1 )
{
for ( every outcome of game between team i and j )
{
enter games score for game (i,j)
simPlay(score1, score2, T); // Recursion will fill in all games
erase score of game (i, j);
}
}
}
|
DEMO: CCC/2013/Progs/j5.cc