L5: Exhaustive Search and Generation I

In this lab we consider some of the problems from Jutge.org, section EDA \rightarrow Exhaustive search and generation.

Backtracking

Backtracking is a technique for solving problems by exploring all possible solutions. This is done extending partial solutions to the given problem to larger ones, trying all the possible alternatives, until we reach a full solution. If the current partial solution cannot be extended to reach a total solution, via the current possible extension, we need to backtrack and try to extend it trying the other possibilities. In the backtracking approach it is common to have a parameter (say k) which is used to keep track of the progress done so far.

A possible (very high level) template could be the following:

void backtracking(int k, ...other parameters...){
    if (k == base_case){// base case of the recursion
        /* 
        This is this case we arrived to a full solution
        
        Do here whatever you are supposed to do with a full solution, e.g. write it to cout.
        */
    }
    else{// inductive case
        /*
        Assume you already have a partial solution, for instance a vector whose entries up to k-1 represent a partial solution.
        
        We want to extend the partial solution to a partial solution up to k, in all the possible allowed ways. That is:
        
        Do a for loop on all the possible ways to extend the partial solution to a partial solution one element larger. 
        (Sometimes this loop is only on 2 elements, e.g. true or false and it is not done explicitly with a for)

        Inside the loop, check whether the way you are trying to extend is allowed
        (this really depends on the problem at hand) 
        if it is allowed:
            - Extend the partial solution.
            - Update the auxiliary structures         
            backtracking(k+1, ...other parameters updated...);
            - Undo the update on the auxiliary structures 
              to allow trying other branches of execution (backtracking)
        */
    }
}

In the main the backtracking function is then called with backtracking(0, ...), where the 0 signals that we have done no progress yet towards a full solution. The partial solution is still empty.

Common error(s)

  • Trying to do more than one check in the if condition of the base case. This will likely result in some unwanted execution, for instance entering in the else for k > base case and perhaps going out the range of a vector.

  • Assuming that the base case is k=0. This is not. The base case of the recursion is when we have a full solution. k=0 is signaling the opposite, the partial solution is empty, we have not made yet any progress towards a full solution.

  • In the inductive case (the else), trying to update k with ++k or updating other quantities in the same way instead of calling backtracking(k+1, ...).

  • In the inductive case (the else), not assuming you already have a partial solution up to k-1, and therefore trying to compute it again, typically with some for loop.

  • If the backtracking is used to enumerate all possible solutions to a problem, a common theme is to mark as used some objects before calling backtracking(k+1, ...) to disallow using them in the future. A common error is forgetting to undo the marking as used of the objects after the call to backtracking(k+1, ...). This will result in exploring only one possible branch (one way of extending partial solutions). This might lead or not to a full solution.

Jutge exercises

In this lab we consider the following Jutge exercises.

Once you have chosen a problem to solve, download the .zip archive of the problem and unzip it. In the obtained folder there are:

  • a file .pdf with the official problem statement
  • one or more text files with examples of input sample.inp
  • the corresponding correct outputs sample.cor

After creating a C++ source file to solve the problem, compile it with g++ -std=c++11.

Common error(s)

Not using the flag -std=c++11.

Possible useful flags are -Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG

Test the executable file obtained on the given example(s), for instance with ./a.out < sample.inp > output. Also, test your code against simple/trivial inputs, e.g. a graph with no-edges.

Common error(s)

Writing the input by hand.
Not checking the exact formatting of the output.

To see whether the output is the same as sample.cor a way is to use diff output sample.cor

Once the code compiles and on the given samples it gives the correct output submit it to the Jutge for automatic evaluation.

Common error(s)

Sending to the Jutge code that was not even compiled locally.
Not checking if the output was correct on the given inputs.

You are “stuck” on a problem if you spent around 1 hour trying to solve it but still the Jutge is rejecting your solution.

Possible approaches to getting “un-stuck” are:

  • do not think about that problem for some time and come back to your code with fresh eyes

  • look again at the theory

  • try to explain your code to another student

  • ask for hints, e.g. by email. Be specific on the type of help you need. Include in the email the code of your approach.


From this block of exercises, in class we solve together the ones marked with 🔶. They are the same as the one listed below.1

Remember that for any doubt on the exercises you can ask me by email too until 6 days before the lab exam.

Footnotes

  1. Recall that ❗ marks possibly harder problems.↩︎