In this puzzle you have a list of n pitchers, with known capacities, c1, c2, ... cn, of holding water in gallons. You have a faucet that can be used as often and as much as the player needs. The goal is to measure exactly g gallons of water, using nothing other than these pitchers. Suppose the current amounts of water that these pitchers hold is w1, w2, ... wn,. These numbers are assumed to be 0 initially. The puzzle is solved as soon as wi = g for any i. A player can perform the following operations:

 Fill pitcher i (from the faucet). The precondition of this operation is: ci > wi ≥ 0. The effect is: wi = ci.

 Empty pitcher i. The precondition of this operation is: ci ≥ wi > 0. The effect is: wi = 0.

 Pour pitcher i to pitcher j. The precondition of this operation is: (ci ≥ wi > 0) and (cj > wj ≥ 0). In words, pitcher i must have some water to pour, and pitcher j must have some unused capacity to receive it. The (partial) effect is: (wi = 0) or (wj = cj) or both. In words, the pour operation must continue until pitcher i becomes empty (and its content is added to pitcher j's content), or pitcher j becomes full (and pitcher i retains the remainder), whichever occurs first. They may occur simultaneously.

A Sample Run

Select the puzzle to solve:

1. Pitchers

2. Eight puzzle

Your selection: 1

Enter the number of pitchers: 3

Enter the capacities of the 3 pitchers (gallons): 2, 5, 10

Enter the goal (gallons): 1

Current configuration: [0, 0, 0]

Please select your next move from the following choices:

1. Fill pitcher 1

2. Fill pitcher 2

3. Fill pitcher 3

Your selection: 2

Current configuration: [0, 5, 0]

Please select your next move from the following choices:

1. Fill pitcher 1

2. Fill pitcher 3

3. Empty pitcher 2

4. Pour pitcher 2 to 1

5. Pour pitcher 2 to 3

Your selection: 4

Current configuration: [2, 3, 0]

Please select your next move from the following choices:

1. Fill pitcher 2

2. Fill pitcher 3

3. Empty pitcher 1

4. Empty pitcher 2

5. Pour pitcher 1 to 2

6. Pour pitcher 1 to 3

7. Pour pitcher 2 to 3

Your selection: 3 Current configuration: [0, 3, 0]

Please select your next move from the following choices:

1. Fill pitcher 1

2. Fill pitcher 2

3. Fill pitcher 3

4. Empty pitcher 2

5. Pour pitcher 2 to 1

6. Pour pitcher 2 to 3

Your selection: 5 Current configuration: [2, 1, 0]

Great! You have reached the goal in 4 moves. Bye.

See explaination

Explanation:

#include <iostream>

#include <vector>

using namespace std;

// function to print configuration for each pitcher

void printConfig(vector<int> w, int n)

{

cout << "Current configuration: [" << w[0];

for(int i=1; i<n; i++)

{

cout << ", " << w[i];

}

cout << "]" << endl;

}

void getOptions(vector<int> c, vector<int> w, int n, vector<pair<int, pair<int, int>>> &options)

{

// options count

int count = 0;

// fill

for(int i=0; i<n; i++)

{

if(c[i] > w[i] && w[i] >= 0)

{

count ++;

cout << count << ". Fill pitcher " << (i+1) << endl;

// add options to list

options.push_back(make_pair(1, make_pair(i, 0)));

}

}

// empty

for(int i=0; i<n; i++)

{

if(c[i] >= w[i] && w[i] > 0)

{

count++;

cout << count << ". Empty pitcher " << (i+1) << endl;

// add options to list

options.push_back(make_pair(2, make_pair(i, 0)));

}

}

// Pour pitcher i to pitcher j

for(int i=0; i<n; i++)

{

if(c[i] >= w[i] && w[i] > 0)

{

for(int j=0; j<n; j++)

{

if(i!=j && c[j] > w[j] && w[j] >= 0)

{

count++;

cout << count << ". Pour pitcher " << (i+1) << " to " << (j+1) << endl;

// add options to list

options.push_back(make_pair(3, make_pair(i, j)));

}

}

}

}

}

void execute(vector<int> c, vector<int> &w, pair<int, pair<int, int>> option)

{

int i = option.second.first;

// for fill

if(option.first == 1)

{

w[i] = c[i];

}

// empty

else if(option.first == 2)

{

w[i] = 0;

}

// pour

else

{

int j = option.second.second;

if(w[i] >= c[j])

{

w[i] = w[i] - c[j];

w[j] = c[j];

}

else

{

w[j] = w[i];

w[i] = 0;

}

}

}

int main()

{

// required variables

int choice, n, temp, g, flag, moves = 0;

// vectors are dynamic sized arrays

vector<int> c, w;

vector<pair<int, pair<int, int>>> options;

// select puzzle

cout << "Select the puzzle to solve:\n";

cout << "1. Pitchers\n";

cout << "2. Eight puzzle\n";

cout << "Your selection: ";

cin >> choice;

if(choice == 1)

{

// input values required

cout << "Enter the number of pitchers: ";

cin >> n;

// array for pitchers

cout << "Enter the capacities of the " << n << " pitchers (gallons): ";

for(int i=0; i<n; i++)

{

cin >> temp;

c.push_back(temp);

w.push_back(0);

}

cout << "Enter the goal (gallons): ";

cin >> g;

// start game

while(true)

{

// print configuration

printConfig(w, n);

// check for goal state

flag = 0;

for(int i=0; i<n; i++)

{

if(w[i] == g)

{

flag = 1;

break;

}

}

if(flag)

{

cout << "Great! You have reached the goal in " << moves << " moves. Bye." << endl;

break;

}

// get and print options

//empty previous options

options.clear();

getOptions(c, w, n, options);

// ask for user's selection

cout << "Your selection: ";

cin >> choice;

// update moves

moves++;

// perform according to the selection

execute(c, w, options[choice-1]);

}

}

return 0;

}