>[!abstract] >The **wolf, goat, and cabbage problem** is typical of a class of logical constraints and sequencing puzzles called *river-crossing puzzles*. A farmer must transport a wolf, a goat, and a cabbage across a river using a boat that can carry only one "passenger" at a time. However, if left alone, the wolf will eat the goat, and the goat will eat the cabbage. The solution requires some creativity in the form of bringing one passenger back from the other bank before completing the puzzle. Many variants of river crossing problems have appeared throughout cultures and history with different numbers of constraints. Another example is the *missionaries and cannibals problem*, in which three missionaries and three cannibals must cross the river, with the constraint that the cannibals on either bank must not outnumber the missionaries. >[!tip] Solution >We can describe the state of the system with the vector $\langle w, g, c, f \rangle$ and the values $\{0, 1\}$ to indicate whether the wolf, goat, cabbage, and farmer (respectively) are on the left ($0$) or right ($1$) bank. Initially, all of them are on the left bank: > >$n_0 = \langle 0, 0, 0, 0\rangle$ > >The farmer can only move one "passenger" at a time. We update the state accordingly by adding $1$ to that passenger's state (and the farmer's) when crossing from left to right, and subtracting $1$ when crossing from right to left. > >Now, there are a few states that we must avoid, according to the rules: wolf and goat together without the farmer, and goat and cabbage together without the farmer. This is true on either bank of the river. We can write the non-permissible states as: > >$\langle 0, 0, 0, 1\rangle$ (all but farmer on the left bank) >$\langle 1, 1, 1, 0 \rangle$ (all but farmer on the right bank) >$\langle 0, 0, 1, 1 \rangle$ (wolf and goat alone on the left bank) >$\langle 1, 1, 0, 0 \rangle$ (wolf and goat alone on the right bank) >$\langle 1, 0, 0, 1 \rangle$ (goat and cabbage alone on the left bank) >$\langle 0, 1, 1, 0 \rangle$ (goat and cabbage alone on the right bank) > >From there, it is possible to brute force all permissible transitions to state $n+1$ from state $n$, skipping any branch containing a non-permissible state, until the goal is reached, which is written as: > >$n_k = \langle 1, 1, 1, 1 \rangle$ > >So, starting from the initial state $n_0$, there are three possible states $n_1$: > >$n_1' = \langle 1, 0, 0, 1 \rangle$ (farmer crosses with wolf) >$n_1'' = \langle 0, 1, 0, 1 \rangle$ (farmer crosses with goat) >$n_1''' = \langle 0, 0, 1, 1 \rangle$ (farmer crosses with cabbage) > >Of these, only $n_1''$ is permissible, so we keep it and prune the others. Then the farmer returns: > >$n_2 = \langle 0, 1, 0, 0 \rangle$ (goat alone on the right bank) > >From there, the farmer can only either take the wolf or the cabbage: > >$n_3' = \langle 1, 1, 0, 1 \rangle$ (cabbage alone on the left bank) >$n_3'' = \langle 0, 1, 1, 1 \rangle$ (wolf alone on the left bank) > >Now, if the farmer returns to the left bank empty-handed, we will run into a non-permissible state (wolf and goat, or goat and cabbage alone on the right bank). Should the farmer return with either the wolf (from $n_3'$) or the cabbage (from $n_3''$), we would just loop back to state $n_2$. Therefore, the only option left is that the farmer must return with the goat: > >$n_4' = \langle 1, 0, 0, 0 \rangle$ (wolf alone on the right bank) >$n_4'' = \langle 0, 0, 1, 0 \rangle$ (cabbage alone on the right bank) > >Next, because the farmer cannot leave the goat and cabbage (from $n_4'$) or the wolf and goat (from $n_4''$) alone on the left bank, he must take one to the right. Brute forcing the next step shows that the farmer must take the cabbage (from $n_4'$) and the wolf (from $n_4''$) in order to achieve the only permissible state: > >$n_5 = \langle 1, 0, 1, 1 \rangle$ (goat alone on the left bank) > >Now, the farmer can cross left to fetch the goat: > >$n_6 = \langle 1, 0, 1, 0 \rangle$ (wolf and cabbage together on the right bank) > >And, finally, the farmer brings back the goat to the right bank, reaching the goal $n_k$ after seven steps: > >$n_7 = \langle 1, 1, 1, 1 \rangle$ >[!related] >- **North** (upstream): — >- **West** (similar): — >- **East** (different): — >- **South** (downstream): —