---

The Complete Guide to Solving the Two Bucket Problem in C++

The Two Bucket problem is a classic computational puzzle that serves as a perfect introduction to state-space search algorithms. This guide explains how to solve it efficiently using C++ by modeling states and transitions, leveraging Breadth-First Search (BFS) to find the optimal solution with the minimum number of moves.

---

The Dilemma: A Puzzle of Measurement and Survival

Imagine you're stranded with just two unmarked buckets. One holds exactly 3 liters, the other 5. You have an infinite source of water, but to operate a rescue device, you need to measure out precisely 4 liters. How do you do it? Pouring, emptying, and transferring water are your only options. This isn't just a riddle; it's the core of a fundamental computer science problem.

This scenario perfectly illustrates the "Two Bucket" problem. It challenges you to find the shortest sequence of actions to reach a target quantity. Many developers initially approach this with random trial and error, quickly getting lost in a sea of possible states. The real challenge lies in finding a systematic, guaranteed method to find the most efficient solution.

In this deep-dive guide, we will dissect this problem from the ground up. We will transform this seemingly complex puzzle into a structured graph problem and implement a robust C++ solution using Breadth-First Search (BFS). You will learn not just the code, but the theory behind why this approach is optimal, turning a confusing brain-teaser into a clear algorithmic process.

---

What is the Two Bucket Problem?

The Two Bucket problem is a type of water jug puzzle. The setup is simple, but the solution requires careful logical steps. You are given three key inputs:

• The capacity of the first bucket (let's call it bucket_one_capacity).
• The capacity of the second bucket (bucket_two_capacity).
• A target goal volume of water to be measured (goal).
• Which bucket to start with full (start_bucket).

Your objective is to find the minimum number of moves required to have the goal volume in either of the two buckets. To achieve this, you can only perform a limited set of actions:

1. Fill a bucket: Completely fill either bucket one or bucket two from the water source.
2. Empty a bucket: Completely empty the contents of either bucket.
3. Pour from one to another: Pour water from one bucket into the other until the source bucket is empty or the destination bucket is full, whichever happens first.

Each of these actions counts as a single "move." The solution we seek is the total number of moves, the final amount of water in the goal bucket, and the amount of water in the other bucket.

---

Why This Problem is a Gateway to Advanced Algorithms

At first glance, this seems like a simple logic puzzle. However, its structure makes it an ideal case study for understanding state-space search, a core concept in Artificial Intelligence and algorithm design. Let's break down why it's so important.

A state represents a snapshot of the system at a specific moment. In our case, a state is defined by the amount of water in each bucket. For example, (3, 2) could be a state where bucket one (capacity 3) has 3 liters and bucket two (capacity 5) has 2 liters.

The actions (filling, emptying, pouring) are transitions that move us from one state to another. The collection of all possible states and the transitions between them forms a conceptual graph. The initial state is the starting configuration (e.g., one bucket full, the other empty), and the goal state is any state where one of the buckets contains the target volume.

Our task is to find the shortest path from the initial state to a goal state in this graph. This is where graph traversal algorithms come into play. The most suitable algorithm for finding the shortest path in an unweighted graph (where each move has the same cost) is Breadth-First Search (BFS).

BFS systematically explores the graph level by level, guaranteeing that the first time we reach a goal state, it will be via the minimum number of moves. This makes it a perfect fit for the Two Bucket problem.

---

How to Model and Solve the Problem with C++

Solving this problem programmatically requires translating the abstract concepts of states and transitions into concrete data structures and logic. We'll use a queue for our BFS algorithm and a set to keep track of states we've already visited to avoid infinite loops.

Step 1: Defining the State

First, we need a way to represent a state. A state consists of the water levels in both buckets and the number of moves taken to reach this state. A C++ struct is perfect for this, as it's readable and groups related data together.

// Represents a state: (liters in bucket1, liters in bucket2, number of moves)
struct State {
    int b1;
    int b2;
    int moves;

    // Operator for comparison, useful for std::set
    bool operator<(const State& other) const {
        if (b1 != other.b1) return b1 < other.b1;
        return b2 < other.b2;
    }
};

Step 2: The BFS Algorithm Logic

The BFS algorithm is the engine of our solution. It explores all possible states one "move" at a time, radiating outwards from the start state until a solution is found.

Here is the high-level logic flow:

    ● Start
    │
    ▼
  ┌───────────────────────────┐
  │ Initialize queue & visited set │
  │ Add start_state to queue  │
  └────────────┬──────────────┘
               │
               ▼
        ┌─── Is queue empty? ───┐
       ╱           │            ╲
      No           │            Yes
      │            ▼             │
      ▼      ┌───────────┐       ▼
┌─────────────┐ │ No solution │  ┌─────────┐
│ Dequeue S   │ └───────────┘  │   End   │
└──────┬──────┘                  └─────────┘
       │
       ▼
  ◆ Is S the goal?
   ╱           ╲
 Yes            No
  │              │
  ▼              ▼
┌───────────┐  ┌────────────────────────┐
│  Success! │  │ Generate next_states   │
│ Return moves│  │ For each new state `N`: │
└───────────┘  │  If N not visited:     │
               │    - Add to visited     │
               │    - Enqueue N          │
               └───────────────────┬────┘
                                   │
                                   └────────────回 (Loop back)

To implement this, we need:

• A std::queue<State> to hold the states we need to visit.
• A std::set<std::pair<int, int>> to store the bucket levels of states we have already processed. Using a set prevents us from re-visiting the same state and getting stuck in a loop (e.g., pouring from bucket 1 to 2, then immediately back to 1).

Step 3: Generating All Possible Next States

From any given state (b1, b2), we need to generate all possible states reachable in one move. This involves implementing the logic for our three core actions.

Let's visualize the transitions from a state. For example, if we have buckets of capacity 3 and 5, and our current state is (3, 0):

    Current State: (3, 0)
    Capacities: (3, 5)
          │
          ├─ Action: Empty Bucket 1 ──────────→ New State: (0, 0)
          │
          ├─ Action: Fill Bucket 2 ───────────→ New State: (3, 5)
          │
          └─ Action: Pour 1 into 2 ───────────→ New State: (0, 3)

The pouring logic is the most complex. When pouring from a source bucket to a destination bucket, the amount to pour is limited by two factors: the amount of water in the source bucket and the remaining space in the destination bucket. The amount transferred is the minimum of these two values.

For example, pouring from bucket 1 (containing b1 liters) to bucket 2 (capacity cap2, containing b2 liters):

int available_space_in_b2 = cap2 - b2;
int pour_amount = std::min(b1, available_space_in_b2);

// New state after pouring
int new_b1 = b1 - pour_amount;
int new_b2 = b2 + pour_amount;

Step 4: Putting It All Together in C++

Now, let's assemble the complete, well-commented C++ solution. This code is part of the exclusive curriculum from kodikra.com and demonstrates a clean, efficient implementation of the BFS algorithm for this problem.

#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <numeric> // For std::gcd

namespace two_bucket {

// A struct to hold the final result for clarity
struct BucketStats {
    int moves;
    std::string goal_bucket;
    int other_bucket_level;
};

// Represents a state in our search: (liters in bucket1, liters in bucket2)
using State = std::pair<int, int>;

// Function to solve the Two Bucket puzzle
BucketStats solve(int cap1, int cap2, int goal, const std::string& start_bucket) {
    // Edge Case: If the goal is not a multiple of the GCD of capacities, it's impossible.
    // This is based on Bézout's identity.
    if (goal % std::gcd(cap1, cap2) != 0) {
        // Technically, the problem constraints might not require this check,
        // but it's a mathematical truth of the puzzle. We'll proceed as if solvable.
    }

    // Queue for BFS: stores the current state and the number of moves to reach it
    std::queue<std::pair<State, int>> q;
    
    // Set to keep track of visited states to avoid cycles
    std::set<State> visited;

    // Determine the initial state based on which bucket starts full
    State initial_state;
    if (start_bucket == "one") {
        initial_state = {cap1, 0};
    } else {
        initial_state = {0, cap2};
    }

    // Start the BFS
    q.push({initial_state, 1}); // The first action is filling the start bucket
    visited.insert(initial_state);

    while (!q.empty()) {
        State current_state = q.front().first;
        int moves = q.front().second;
        q.pop();

        int b1 = current_state.first;
        int b2 = current_state.second;

        // --- Check for Goal State ---
        if (b1 == goal) {
            return {moves, "one", b2};
        }
        if (b2 == goal) {
            return {moves, "two", b1};
        }

        // --- Generate Next Possible States ---
        State next_states[6];

        // 1. Fill bucket one
        next_states[0] = {cap1, b2};
        // 2. Fill bucket two
        next_states[1] = {b1, cap2};
        // 3. Empty bucket one
        next_states[2] = {0, b2};
        // 4. Empty bucket two
        next_states[3] = {b1, 0};

        // 5. Pour bucket one into bucket two
        int pour1to2 = std::min(b1, cap2 - b2);
        next_states[4] = {b1 - pour1to2, b2 + pour1to2};

        // 6. Pour bucket two into bucket one
        int pour2to1 = std::min(b2, cap1 - b1);
        next_states[5] = {b1 + pour2to1, b2 - pour2to1};

        // --- Enqueue valid, unvisited states ---
        for (const auto& next_state : next_states) {
            if (visited.find(next_state) == visited.end()) {
                visited.insert(next_state);
                q.push({next_state, moves + 1});
            }
        }
    }
    
    // This part should ideally not be reached if a solution exists
    // and the GCD check passes.
    return {0, "", 0}; // Should represent an impossible scenario
}

} // namespace two_bucket

// Example usage
int main() {
    // Scenario: Buckets of 3L and 5L, goal is 4L, start with bucket one full.
    int bucket_one_cap = 3;
    int bucket_two_cap = 5;
    int goal_liters = 4;
    std::string start_bucket = "one";

    two_bucket::BucketStats result = two_bucket::solve(bucket_one_cap, bucket_two_cap, goal_liters, start_bucket);

    if (result.moves > 0) {
        std::cout << "Solution Found!" << std::endl;
        std::cout << "Total moves: " << result.moves << std::endl;
        std::cout << "Goal bucket: " << result.goal_bucket << std::endl;
        std::cout << "Other bucket level: " << result.other_bucket_level << "L" << std::endl;
    } else {
        std::cout << "No solution found." << std::endl;
    }

    return 0;
}

---

Detailed Code Walkthrough

1. Namespace and Structures

We wrap our code in a two_bucket namespace to avoid naming conflicts. The BucketStats struct provides a clean and readable way to return the multiple values required by the solution. The State is defined as a std::pair<int, int> for simplicity, representing the water levels (b1, b2).

2. Initial Setup and BFS Queue

Inside the solve function, we initialize our BFS queue, q, which stores pairs of {State, moves}. The visited set is crucial; it stores State objects that have already been processed, preventing the algorithm from entering infinite loops.

3. Starting the Search

We determine the initial state based on the start_bucket string. If it's "one", the state is (cap1, 0). Otherwise, it's (0, cap2). This first "fill" action counts as the first move, so we push the initial state onto the queue with moves = 1.

4. The Main Loop

The while (!q.empty()) loop is the heart of the BFS. In each iteration, it:

• Dequeues the state at the front of the queue. This is the current state we are exploring.
• Checks for the goal: It immediately checks if either b1 or b2 equals the goal. If so, a solution has been found! Because BFS explores level by level, we are guaranteed this is the shortest path. The function returns the results in a BucketStats object.
• Generates next states: An array next_states is populated with all 6 possible outcomes from the current state: fill 1, fill 2, empty 1, empty 2, pour 1-to-2, and pour 2-to-1.

5. State Validation and Enqueuing

A for loop iterates through the 6 potential next states. For each one, it checks if that state exists in the visited set. If visited.find(next_state) == visited.end(), it means we've never encountered this combination of bucket levels before. Therefore, we add it to visited and push it onto the queue with an incremented move count (moves + 1).

6. The Mathematical Constraint: GCD

A crucial piece of theory, based on Bézout's identity from number theory, states that a linear Diophantine equation ax + by = c has integer solutions for x and y if and only if c is a multiple of the greatest common divisor (GCD) of a and b. In our puzzle, this translates to: a solution to measure a goal volume is only possible if goal is a multiple of std::gcd(cap1, cap2). While the provided kodikra module may not require this check for its test cases, it's a fundamental property of the problem worth knowing.

---

Alternative Approaches and Considerations

While BFS is optimal for finding the shortest solution, it's not the only way to traverse the state-space graph. Understanding the alternatives helps solidify your algorithmic knowledge.

BFS vs. DFS: A Comparison

Depth-First Search (DFS) is another common graph traversal algorithm. Instead of exploring level by level, DFS goes as deep as possible down one path before backtracking. Here’s how they compare for the Two Bucket problem:

Aspect	Breadth-First Search (BFS)	Depth-First Search (DFS)
Optimality	Guaranteed to find the shortest path (minimum number of moves) because it explores all paths of length 1, then all paths of length 2, and so on.	Finds a solution, but provides no guarantee that it's the shortest. The first solution it finds depends on the path it happens to explore first.
Memory Usage	Can be memory-intensive. The queue can grow very large if the number of states at each level is high. Stores all nodes at the current depth.	Generally more memory-efficient. It only needs to store the nodes along the current path from the root to the current node.
Implementation	Typically implemented iteratively using a queue.	Can be implemented iteratively with a stack or more naturally with recursion.
Use Case	Ideal for shortest path problems on unweighted graphs, like our puzzle.	Better for problems where you just need to find if a path exists, or for traversing an entire tree/graph (e.g., topological sort).

Future-Proofing Your Skills: Advanced Optimizations

For very large state spaces, even BFS can become slow. More advanced techniques exist:

• Bidirectional Search: This involves running two BFS searches simultaneously—one forward from the start state and one backward from the goal state. The search stops when the two "frontiers" meet in the middle. This can significantly reduce the search space and time complexity.
• A* Search: If we could estimate the remaining "distance" to the goal (a heuristic), we could use an algorithm like A* to prioritize exploring states that seem closer to the solution. For this problem, designing a good heuristic is non-trivial but possible.

Understanding these concepts prepares you for more complex problems in pathfinding, AI planning, and robotics, which often build upon the same foundations of state-space search. To continue your journey, you can explore our C++ learning path, which covers these advanced topics.

---

Frequently Asked Questions (FAQ)

1. Why use Breadth-First Search (BFS) instead of Depth-First Search (DFS)?

BFS is used because the problem asks for the minimum number of moves. BFS explores the state graph level by level, guaranteeing that the first time it finds the goal state, it has done so via the shortest possible path. DFS, on the other hand, explores one path to its maximum depth before backtracking and would likely find a valid solution that is not the most efficient one.

2. What exactly is a "state" in the context of this problem?

A "state" is a unique snapshot of the system at any given moment. For the Two Bucket problem, a state is completely defined by the amount of water in each of the two buckets. For example, (3, 5) is a state where the first bucket has 3 liters and the second has 5 liters. Our algorithm moves from one state to another through defined actions (fill, empty, pour).

3. Is the Two Bucket problem always solvable?

No. A solution only exists if the target goal volume is a multiple of the greatest common divisor (GCD) of the two bucket capacities. For example, if you have buckets of capacity 6 and 9, the GCD is 3. You can only measure volumes that are multiples of 3 (3, 6, 9, 12, etc.). It would be impossible to measure exactly 4 liters.

4. How can I optimize this C++ solution for performance?

The primary bottleneck can be the visited set lookup. Using std::unordered_set instead of std::set can provide average O(1) lookup time instead of O(log N), but it requires you to provide a custom hash function for the std::pair or custom State struct. For the constraints of this particular kodikra module, std::set is perfectly sufficient and simpler to implement.

5. What happens if the goal is larger than the capacity of both buckets?

If the goal is larger than the capacity of the larger bucket, it's impossible to measure that amount in a single bucket. The algorithm as written would exhaust all possible states without finding a solution and the queue would become empty, correctly indicating no solution was found (though a simple upfront check like if (goal > std::max(cap1, cap2)) could handle this more efficiently).

6. What are some real-world applications of state-space search?

State-space search is a fundamental concept in Artificial Intelligence and robotics. It's used in route planning (like Google Maps finding the shortest route), solving puzzles and games (like chess or Sudoku), robotic motion planning (finding a path for a robot arm to move without collision), and even in formal verification of computer hardware and software.

7. Can this problem be solved without a queue, perhaps recursively?

Yes, a recursive solution is possible. However, a direct recursive implementation without memoization (tracking visited states) would naturally form a Depth-First Search (DFS). It would explore one sequence of moves to its end before trying another, and would not be guaranteed to find the shortest path first. To make a recursive solution find the shortest path, you would essentially be re-implementing a BFS, which is more naturally done with an iterative queue-based approach.

---

Conclusion: More Than Just a Puzzle

The Two Bucket problem, as explored in this kodikra.com module, is a powerful lesson disguised as a simple puzzle. It teaches us to deconstruct a problem into a graph of states and transitions, a technique applicable to a vast range of computational challenges. By implementing a Breadth-First Search, we not only find a solution but the most efficient one, reinforcing the importance of choosing the right algorithm for the job.

You've learned how to model the problem, implement a robust BFS in C++, handle state management with queues and sets, and understand the mathematical constraints that define the problem's boundaries. This foundational knowledge is a stepping stone to tackling more complex algorithms in AI, game development, and optimization.

To further develop your skills, master C++ with our complete guide and continue to challenge yourself with problems that require you to think in terms of states, graphs, and optimal paths.

Disclaimer: The C++ code in this article is written based on C++17 standards and should be compatible with newer versions like C++20 and C++23. The core algorithmic concepts are timeless.

---

Published by Kodikra — Your trusted Cpp learning resource.