State-Space Search for the 4-Gallon / 3-Gallon Water Jug Problem (Reach Exactly 2 Gallons)

We model the classic Water Jug problem as a State Space Search task. Here, the capacities are 4 gallons and 3 gallons, with the goal: reach a state where the 4-gallon jug contains exactly 2 gallons.

Let a State be an ordered pair:

• $(x, y)$ where
  • $x$ = water in the 4-gallon jug ($0 \le x \le 4$)
  • $y$ = water in the 3-gallon jug ($0 \le y \le 3$)

We consider legal actions as Production Rules that generate successor states. The transition dynamics are based on filling, emptying, and pouring without measuring markings.

Key state-goal:

• Goal test: $x = 2$ (i.e., $(2, y)$ for any $y$ satisfying $0 \le y \le 3$)

Note: The above path is one valid solution sequence; the detailed production-rule application is given below.

Problem formulation in State Space Search

We define a Search Problem as:

• State space: $S = \{(x,y)\mid x\in\{0,1,2,3,4\},\ y\in\{0,1,2,3\}\}$
• Start state: $s_0 = (0,0)$
• Goal set: $G = \{(2,y)\mid y\in\{0,1,2,3\}\}$
• Actions: fill a jug, empty a jug, or pour from one jug to the other until either the source is empty or the destination is full
• Transition function: defined by the production rules below

Action set (conceptually):

1. Fill 4-gallon jug
2. Fill 3-gallon jug
3. Empty 4-gallon jug
4. Empty 3-gallon jug
5. Pour 4 → 3
6. Pour 3 → 4

Because capacities are small, this is a finite graph search. Algorithms like BFS/DFS/A* are applicable; here we mainly need the representation and at least one solution path.

Production Rules written explicitly (formal “if state then successor”)

We write each rule as a Production Rule of the form:

Rule name:
If $(x,y)$ satisfies the condition, then generate successor $(x',y')$ as specified.

Let $\Delta_{4\to3}=\min(x,3-y)$ and $\Delta_{3\to4}=\min(y,4-x)$.

1. Fill-4

   • Condition: (always)
   • $(x,y)\rightarrow(4,y)$

2. Fill-3

   • Condition: (always)
   • $(x,y)\rightarrow(x,3)$

3. Empty-4

   • Condition: (always)
   • $(x,y)\rightarrow(0,y)$

4. Empty-3

   • Condition: (always)
   • $(x,y)\rightarrow(x,0)$

5. Pour-4-to-3

   • Condition: $x>0$ and $y<3$
   • $(x,y)\rightarrow(x-\Delta_{4\to3},\ y+\Delta_{4\to3})$

6. Pour-3-to-4

   • Condition: $y>0$ and $x<4$
   • $(x,y)\rightarrow(x+\Delta_{3\to4},\ y-\Delta_{3\to4})$

Example solution (one correct action sequence)

We show a concrete path from the start $(0,0)$ to a goal state where the 4-gallon jug holds exactly 2 gallons.

Solution sequence (states + actions)

Target: reach $(2,y)$ for some $y$

1. Start: $(0,0)$
2. Fill-3: $(0,0)\rightarrow(0,3)$
3. Pour-3-to-4: pour from the 3-gallon into the 4-gallon
   $(0,3)\rightarrow(3,0)$
4. Fill-3: $(3,0)\rightarrow(3,3)$
5. Pour-3-to-4: $(3,3)\rightarrow(4,2)$
   (Because $4-x=1$, so only 1 gallon fits in the 4-gallon; 3−1=2 remains in 3-gallon.)
6. Pour-4-to-3: $(4,2)\rightarrow(2,2)$
   (Because $3-y=1$, so 1 gallon is needed to fill the 3-gallon; $4-1=3$? Let’s compute carefully:)
   • Here $x=4$, $y=2$
   • $\Delta_{4\to3}=\min(4,3-2)=\min(4,1)=1$
   • New state: $(x-\Delta,\ y+\Delta)=(4-1,\ 2+1)=(3,3)$

That reveals a correction: the state after pouring 4 → 3 from $(4,2)$ should be $(3,3)$, not $(2,2)$. We therefore adjust the solution to a correct one.

Corrected solution path (fully consistent arithmetic)

We use a known-valid sequence:

1. $(0,0)$
2. Fill-4: $(0,0)\rightarrow(4,0)$
3. Pour-4-to-3: $(4,0)\rightarrow(1,3)$
   • $\Delta_{4\to3}=\min(4,3-0)=3$ → $(4-3,\ 0+3)=(1,3)$
4. Empty-3: $(1,3)\rightarrow(1,0)$
5. Pour-4-to-3: (not possible because $y<3$ but $x=1>0$ yes pour)
   $(1,0)\rightarrow(0,1)$
   • $\Delta_{4\to3}=\min(1,3-0)=1$ → $(1-1,\ 0+1)=(0,1)$
6. Fill-4: $(0,1)\rightarrow(4,1)$
7. Pour-4-to-3: $(4,1)\rightarrow(2,3)$
   • $\Delta_{4\to3}=\min(4,3-1)=\min(4,2)=2$
   • $(4-2,\ 1+2)=(2,3)$

Now the 4-gallon jug contains exactly 2 gallons in state $(2,3)$, which satisfies the goal $x=2$.

The production-rule math above explicitly shows why each successor state is correct.

Visual check: state graph snippet

Below is a small portion of the graph around the solution path.