This is one of my nicest-ever experiences with programming. My cousin asked me about the 3-7-10 problem, do you know it? Most probably yes... I'll remind you. You have 3 unmetered containers with capacities 3 liters, 7 liters and 10 liters. Use them to have 5 liters in the 7-liters one and 5 liters in the 10-liters one. You're only allowed to either fill a container or evacuate it – no fractions of any container can be acquired. You have only 10 liters in the 10-liters container, the other two are vacant. No extra water is allowed.
I solved it quickly, but – as you know – just by trial and error. Then I thought about it a little bit... this is a typical backtracking problem. You proceed with one of the solutions, till it either proves correct or you find your last step irrelevant. Instead of quitting the whole solution, you just throw away your last step and choose another one.
Let's learn together ;-). Once you do a step, what can cause it to be “irrelevant”? The answer is very simple: You've reached this configuration before. A configuration is my term to describe the current state, meaning: [Container_3 contains 2 liters, Container_7 contains 4 liters, Container_10 contains 4 liters]. This is a valid configuration, since the sum of the contents is correctly 10 liters.
Note that if you do a step that reaches a configuration you've seen before, you're not advised to do it again – otherwise you'll keep looping forever, reaching the same configuration over and over again.
There's another obvious configuration that makes you stop: The winning configuration. If the next configuration is what you're seeking (0-5-5), just print the solution vector out.
What's the solution vector? I simply keep the configurations with me as I go. Whenever I advance, I add the last configuration hoping that I'll reach the correct one. Whenever I reach a dead end, I just throw that configuration away (from the solution vector) and pick another. Whenever I reach the winning configuration, I print all what I have.
An important notice: Whenever I reach the winning configuration, I print out the solution then discard the last step (though it was correct)! Why? Because I'm seeking all possible solutions, not just one. So I just go on normally – as if nothing has happened – discarding the last trial and proceeding with the next one… may be the next one will lead me to another solution.
The final thing to know is: Given a configuration we're currently in, what are the allowed steps? This is trivial... why are you asking me!? :-P
The allowed moves are – as you know: Pour Container_3 into Container_7, Container_3 into Container_10, Container_7 into Container_3, Container_7 into Container_10, Container_10 into Container_3, or Container_10 into Container_7. Thus, at each iteration, I try these six in order. That's all...
A final notice: Take care of overflowing while pouring. I mean, when you pour Container_7 that currently contains 4 liters (for example) into Container_3 that currently contains 1 liter, take care to leave Container_7 with 2 liters and Container_3 full. This is the meaning of using min() and max() in my solution.
I've said this was one of my nicest-ever experiences because I coded this problem, pressed Ctrl+F5, and found all the 20 solutions on the screen. No debugging, no tracing, nothing. It just worked from the first trial. Only then that I realized I've finally understood backtracking, since this was my first program to write using backtracking.
That said, my solution is not at all generic. You're encouraged to make it more generic, or – more importantly – to expand it. This idea can work for any given containers and any target configuration. I preferred to let this exercise to you. I even didn't try to optimize the code so as not to obscure it.
I'm sharing the solution with you. I've commented it as much as I can, and I'm willing to discuss with you in case it's not that clear.
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ofstream fout("solutions.txt");
static int counter = 1;
struct configuration {
int contents_3, contents_7, contents_10;
configuration(int contents_3, int contents_7, int contents_10) {
this->contents_3 = contents_3;
this->contents_7 = contents_7;
this->contents_10 = contents_10;
}
bool const operator==(const configuration& other) const {
return (this->contents_3 == other.contents_3 && this->contents_7 == other.contents_7 && this->contents_10 == other.contents_10);
}
};
vector<configuration> solution;
void solve(configuration current) {
// Firstly... have we reached the required configuration?
if (current.contents_3 == 0 && current.contents_7 == 5 && current.contents_10 == 5) {
solution.push_back(current); // Add it in preparation for printing the complete solution.
// Printing the solution.
{
fout << "Solution " << counter++ << ":" << endl;
for (vector<configuration>::const_iterator cit = solution.begin(); cit != solution.end(); cit++)
fout << cit->contents_3 << " " << cit->contents_7 << " " << cit->contents_10 << endl;
fout << endl;
}
solution.pop_back(); // Backtrack to search for other solutions.
} else { // Not yet, let's continue...
if (find(solution.begin(), solution.end(), current) != solution.end()) // Have we encountered this configuration before?
return; // If yes, return instantly. A configuration can never repeat, because if this happens then we are stuck in an infinite loop.
solution.push_back(current); // Let's assume this is a correct guess...
//================================//
// Trying the six allowable moves //
//================================//
// Pouring into contents_3...
{
solve(configuration( // ...contents_7.
min(3, current.contents_3 + current.contents_7),
max(0, current.contents_7 - (3 - current.contents_3)),
current.contents_10));
solve(configuration( // ...contents_10.
min(3, current.contents_3 + current.contents_10),
current.contents_7,
max(0, current.contents_10 - (3 - current.contents_3))));
}
// Pouring into contents_7...
{
solve(configuration( // ...contents_3.
max(0, current.contents_3 - (7 - current.contents_7)),
min(7, current.contents_7 + current.contents_3),
current.contents_10));
solve(configuration( // ...contents_10.
current.contents_3,
min(7, current.contents_7 + current.contents_10),
max(0, current.contents_10 - (7 - current.contents_7))));
}
// Pouring into contents_10...
{
solve(configuration( // ...contents_3.
max(0, current.contents_3 - (10 - current.contents_10)),
current.contents_7,
min(10, current.contents_10 + current.contents_3)));
solve(configuration( // ...contents_7.
current.contents_3,
max(0, current.contents_7 - (10 - current.contents_10)),
min(10, current.contents_10 + current.contents_7)));
}
solution.pop_back(); // Backtrack. Either this was a good guess and the solution was already output, or it was bad and thus useless. In both cases, remove it from our vector.
}
}
int main() {
solve(configuration(0, 0, 10));
fout.close();
return 0;
}