1. Algorithmic Overview & Mathematical Formulation
The Wolf, Sheep, and Cabbage puzzle (historically known as the Fox, Goose, and Bag of Grain problem) represents one of the foundational constraint satisfaction problems ($CSP$) and discrete state-space search benchmarks in algorithmic graph theory. Attributed to the Latin collection Propositiones ad Acuendos Juvenes ("Problems to Sharpen the Young") compiled by the 8th-century scholar Alcuin of York, the scenario models an operational transport logistics dilemma governed by strict relational conflict invariants.
Formally, let the operational domain be governed by a binary state vector $\mathbf{s} \in \{0, 1\}^4$, defined as:
$$\mathbf{s} = (F, W, S, C)$$
where the binary coordinate values $0$ and $1$ map respectively to the Left Bank (Origin) and the Right Bank (Destination). The individual vector components represent:
- $F \in \{0, 1\}$: Spatial position of the Boat Operator (Farmer).
- $W \in \{0, 1\}$: Spatial position of the Apex Predator (Wolf).
- $S \in \{0, 1\}$: Spatial position of the Herbivorous Intermediate (Sheep).
- $C \in \{0, 1\}$: Spatial position of the Trophic Base Resource (Cabbage).
The state space contains $|V| = 2^4 = 16$ theoretical configurations residing on the vertices of a 4-dimensional hypercube graph $Q_4$. However, biological trophic predation rules impose non-negotiable forbidden conflict sub-graphs:
$$W = S \neq F \implies \text{Predation Violation (Wolf consumes Sheep)}$$
$$S = C \neq F \implies \text{Consumption Violation (Sheep consumes Cabbage)}$$
Eliminating states that violate either condition leaves exactly $10$ admissible configurations in the valid state graph $G_{valid} = (V_{valid}, E_{valid})$. The objective is to identify a minimal-length path $P = (v_0, v_1, \dots, v_k)$ such that $v_0 = (0,0,0,0)$, $v_k = (1,1,1,1)$, and every transition $(v_i, v_{i+1}) \in E_{valid}$ satisfies boat capacity limitations:
$$\Delta F = |F_{i+1} - F_i| = 1 \quad \text{and} \quad \sum_{X \in \{W, S, C\}} |X_{i+1} - X_i| \le 1$$
Furthermore, an item $X$ can transition if and only if its initial position coincides with the farmer's origin shore ($X_i = F_i$).
3. State-Space Graph Traversal & Physics Engine Architecture
The underlying computational engine separates discrete topological state verification from continuous canvas interpolation.
Breadth-First Search ($BFS$) Optimal Path Proof
Because all admissible edges in $G_{valid}$ possess uniform unit weight $w(e) = 1$ representing a single crossing transition, the shortest trajectory is provably determined via Breadth-First Search in $O(|V| + |E|)$ complexity.
$$\text{Admissible States } V_{valid} = \left\{
\begin{matrix}
(0,0,0,0), & (1,0,1,0), & (0,0,1,0), & (1,1,1,0), & (1,0,1,1), \\
(0,1,0,0), & (0,0,0,1), & (1,1,0,1), & (0,1,0,1), & (1,1,1,1)
\end{matrix}
\right\}$$
The bipartite structure of the state graph partitions $V_{valid}$ into subsets where $\sum s_j \equiv 0 \pmod 2$ and $\sum s_j \equiv 1 \pmod 2$. Consequently, any valid trajectory must alternate between odd-parity and even-parity configurations, requiring an odd integer number of crossings. The minimal admissible solution path is strictly $k = 7$ steps:
$$P^* = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}
\xrightarrow{+F, +S} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}
\xrightarrow{-F} \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}
\xrightarrow{+F, +W} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \end{pmatrix}
\xrightarrow{-F, -S} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}
\xrightarrow{+F, +C} \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \end{pmatrix}
\xrightarrow{-F} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \end{pmatrix}
\xrightarrow{+F, +S} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}$$
Notice that at Step 3, a symmetrical branch exists: the Farmer may alternatively transport the Cabbage ($\mathbf{s}_3 = (1,0,1,1)$) and return with the Sheep ($\mathbf{s}_4 = (0,0,0,1)$), demonstrating the dual isomorphic path geometry of $Q_4$.
Procedural River Hydrodynamics & Render Pipeline
The visual canvas executes a 60 FPS requestAnimationFrame loop driven by continuous wave equations. Water surface elevation $\eta(x, t)$ is computed via a multi-frequency superposition of sinusoidal traveling waves:
$$\eta(x, t) = \sum_{m=1}^{M} A_m \sin(k_m x - \omega_m t + \phi_m)$$
where $A_m$ denotes amplitude, $k_m = \frac{2\pi}{\lambda_m}$ is the spatial wavenumber, and $\omega_m = 2\pi f_m$ represents temporal angular frequency. The boat executes pitch and heave oscillations via numerical damping:
$$\theta_{boat}(t) = \theta_{target} + A_\theta \sin(\omega_0 t) \cdot e^{-\gamma t}$$