Wolf, sheep, cabbage - Algoritmy.net
Wolf, sheep, cabbage is a logic puzzle, in which the player (boatman) has to transport a wolf, a sheep and a cabbage from one river bank to the other. In the game the player must obey these rules:
http://yongouyang.blogspot.com/2013/04/solving-farmer-wolf-goat-cabbage-riddle.html
It is a task that given an initial state, a final state, and a set of rules, one will start from the initial state and try to reach to the final state by passing through some intermediate states. Each move will transform from one state to the other, and there might be multiple valid moves from a given state. Such a collection of interconnected states can be represented by State Space Graph.
Let's use 'f', 'c', 'g', 'w' to denote the farmer, the cabbage, the goat, and the wolf, and use '|' to separate the river where left of the '|' denotes west bank and right of the '|' denotes east bank. Initially, they are all at the west bank of the river, which is represented as 'fcgw |' as shown below. We can solve the riddle by figuring out what the possible and valid moves are, using either Breadth-First Search or Depth-First Search, on a state space graph shown below
Depth First Search
I use DFS to find the first possible solution to the riddle, where it looks like this
or with a possibility of backtracking like this
Breadth First Search
I can build a complete state space graph using BFS, excluding the red states as shown below
http://www.geeksforgeeks.org/missionaries-and-cannibals/
Read full article from Wolf, sheep, cabbage - Algoritmy.net
Wolf, sheep, cabbage is a logic puzzle, in which the player (boatman) has to transport a wolf, a sheep and a cabbage from one river bank to the other. In the game the player must obey these rules:
- The player can use a boat to transport the objects, but he may take at maximum one thing with him every time.
- If the sheep remains unguarded on the same bank as the cabbage, than the sheep will eat the cabbage.
- If the wolf remains unguarded on the same bank as the sheep, than the wolf will eat the sheep.
public static void solveSheepCabbageWolf(){05.sheepCabbageWolf(false, false, false, false, new LinkedList<String>());06.}07./**08.* Solves the sheep-cabbage-wolf riddle and prints out its solution (the actual worker method)09.* @param sheep true if the sheep is on the right bank, false otherwise10.* @param cabbage true if the cabbage is on the right bank, false otherwise11.* @param wolf true if the wolf is on the right bank, false otherwise12.* @param farmer true if the farmer (boat) is on the right bank, false otherwise13.* @param solution partial solution14.* @return false if the partial solution is invalid15.*/16.private static boolean sheepCabbageWolf(boolean sheep, boolean cabbage, boolean wolf, boolean farmer, Deque<String> solution) {17.if (sheep && cabbage && wolf && farmer) {18.printSolution(solution);19.return true;20.}21.if (!checkConsistency(sheep, cabbage, wolf, farmer)) {22.return false;23.}24.if (solution.isEmpty() || !solution.peek().equals("boatman")) {25.solution.addFirst("boatman");26.if (sheepCabbageWolf(sheep, cabbage, wolf, !farmer, solution)) {27.return true;28.}29.solution.pop(); //backtrack30.} 31.if (sheep == farmer && (solution.isEmpty() || !solution.peek().equals("sheep"))) {32.solution.addFirst("sheep");33.if (sheepCabbageWolf(!sheep, cabbage, wolf, !farmer, solution)) {34.return true;35.}36.solution.pop(); //backtrack37.}38.if (cabbage == farmer && (solution.isEmpty() || !solution.peek().equals("cabbage"))) {39.solution.addFirst("cabbage");40.if (sheepCabbageWolf(sheep, !cabbage, wolf, !farmer, solution)) {41.return true;42.}43.solution.pop(); //backtrack44.}45.if (wolf == farmer && (solution.isEmpty() || !solution.peek().equals("wolf"))) {46.solution.addFirst("wolf");47.if (sheepCabbageWolf(sheep, cabbage, !wolf, !farmer, solution)) {48.return true;49.}50.solution.pop(); //backtrack51.} 52.return false;53.}63.private static boolean checkConsistency(boolean sheep, boolean cabbage, boolean wolf, boolean farmer) {64.if (sheep == cabbage && sheep != farmer) {65.return false;66.} else if (sheep == wolf && sheep != farmer) {67.return false;68.}69.return true;70.}It is a task that given an initial state, a final state, and a set of rules, one will start from the initial state and try to reach to the final state by passing through some intermediate states. Each move will transform from one state to the other, and there might be multiple valid moves from a given state. Such a collection of interconnected states can be represented by State Space Graph.
Let's use 'f', 'c', 'g', 'w' to denote the farmer, the cabbage, the goat, and the wolf, and use '|' to separate the river where left of the '|' denotes west bank and right of the '|' denotes east bank. Initially, they are all at the west bank of the river, which is represented as 'fcgw |' as shown below. We can solve the riddle by figuring out what the possible and valid moves are, using either Breadth-First Search or Depth-First Search, on a state space graph shown below
or with a possibility of backtracking like this
http://www.geeksforgeeks.org/missionaries-and-cannibals/
Question: In this problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, that the missionaries present on the bank cannot be outnumbered by cannibals. The boat cannot cross the river by itself with no people on board.
