Due date: Wednesday, November 5, 2025.
Write a python function that solves the problem of the jealous
husband. See an example of the implementation of the goat-wolf-cabbage
problem in the following files, as discussed in class:
goat.py
Problem. 3 man and woman couples are traveling together. They encounter a river they must cross and there is one boat that can hold up to 2 people at a time, 1 person crossing also being allowed (but the boat doesn't cross by itself). For jealousy reasons, the men don't want their wives to be in the presence of another man without them.
The constraints here are that a state is considered safe if on neither side of the river the number of men exceeds the number of women because that would leave one woman without her husband on the other side. Note that a special case with all 3 women on one side and all 3 men on the other is still considered safe.
Implementation suggestions; (or use your own model). The state can be represented by 3 numbers, W for the women on the initial side, M for the number of men on the same side, and B for where the boat is (can be 0/1 or true/false). The number of women and men on the other side is 3-W and 3-M and doesn't need to be stored (or you can store all 5 value if that seems easier). You can group the 3 of them in a list or tuple to identify a state.
If you use the code in the file goat.py, you can focus on implementing the functions safe_state, goal_reach, and expand_states.
It would help to define a function move_state(state, x, y), where x is the number of women you want to move and y is the number of men, and the state is like (W, M, B) as described above. The constraint is that x + y > 0 to have a proper child of a state, and x + y <= 2 because the boat can hold only two people. In the function, if B == 1 (boat is on the left), you'd return a state where you subtract x from W and y from M, and if not, you'd add them instead. In the subtraction, you have to make sure that the result is not less than 0, and in the addition, that it's not greater than 3. If either condition is not satisfied, you can return None to signify that this is not a valid move.
In the function safe_state(state), assuming that the state is the same as above, you'd have to check that on each side, the number of women is larger than or equal to the number of men, or one of them is 0.
In the function goal_reach(state), you just have to check that all the men and women are on the other side, meaning that W == M == 0.
In the function expand_state(state), you'd have to have a loop for all the values of x and y such that x+y > 0 and x+y <= 2. For each of them, you call the function move_state, and if it returns something other than None and it is a safe state, you add it to the list of children of that state.
The function search_sol can probably be used unchanged.
The functions print_path and solve_goat need to be adapted to the new problem.
Note. The problem is solvable with a linear search without backtracking, but you have to make sure that the child states where 2 people are moved are generated and evaluated before those that move just one person at a time. But the algorithm should work either way.
Upload all the functions in one python file on Canvas in Assignments - Homework 9.