Data representation

 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)

Determining the winner from a full schedule

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

Theory on Backtracking    What is Backtracking

  • Backtracking is an algorithmic technique for solving problems recursively by:

      • Building a solution incrementally --- one piece/step at a time.

      • The algorithm must walk back the previous step during the solution building process

        (Hence the name: backtracking)

  • Backtracking is a form of brute force search algorithm

  • However:

      • Backtracking will not explore "solution" that violates the solution criteria

        (So backtracking is more efficient than pure brute force sreach)

Backtracking algorithm    in pseudo code
 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 
 }

Backtracking algorithm    rename function to simPlay()
 // 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 
 }

Backtracking algorithm    there is no limit on # steps


 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 
 }

Backtracking algorithm    currState is a solution when the score board is filled
 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 

Backtracking algorithm for J5

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