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.
Solution
From the algorithmic point of view the puzzle can be easily solved by a backtracking algorithm. The backtracking algorithm in every step tries to transport one thing to the other bank and then it checks the consistency of the partial solution. If the solution is consistent, than it repeats the step (transports another thing). If not, than the backtracking algorithm returns to the preceding decision and changes it (transports something else, or returns to the previous decision, if all possible objects were already tried out). Using this technique of organized trials and failures the algorithm finds the solution.
Code
/**
* Solves the sheep-cabbage-wolf riddle and prints out its solution
*/
public static void solveSheepCabbageWolf(){
sheepCabbageWolf(false, false, false, false, new LinkedList<String>());
}
/**
* Solves the sheep-cabbage-wolf riddle and prints out its solution (the actual worker method)
* @param sheep true if the sheep is on the right bank, false otherwise
* @param cabbage true if the cabbage is on the right bank, false otherwise
* @param wolf true if the wolf is on the right bank, false otherwise
* @param farmer true if the farmer (boat) is on the right bank, false otherwise
* @param solution partial solution
* @return false if the partial solution is invalid
*/
private static boolean sheepCabbageWolf(boolean sheep, boolean cabbage, boolean wolf, boolean farmer, Deque<String> solution) {
if (sheep && cabbage && wolf && farmer) {
printSolution(solution);
return true;
}
if (!checkConsistency(sheep, cabbage, wolf, farmer)) {
return false;
}
if (solution.isEmpty() || !solution.peek().equals("boatman")) {
solution.addFirst("boatman");
if (sheepCabbageWolf(sheep, cabbage, wolf, !farmer, solution)) {
return true;
}
solution.pop(); //backtrack
}
if (sheep == farmer && (solution.isEmpty() || !solution.peek().equals("sheep"))) {
solution.addFirst("sheep");
if (sheepCabbageWolf(!sheep, cabbage, wolf, !farmer, solution)) {
return true;
}
solution.pop(); //backtrack
}
if (cabbage == farmer && (solution.isEmpty() || !solution.peek().equals("cabbage"))) {
solution.addFirst("cabbage");
if (sheepCabbageWolf(sheep, !cabbage, wolf, !farmer, solution)) {
return true;
}
solution.pop(); //backtrack
}
if (wolf == farmer && (solution.isEmpty() || !solution.peek().equals("wolf"))) {
solution.addFirst("wolf");
if (sheepCabbageWolf(sheep, cabbage, !wolf, !farmer, solution)) {
return true;
}
solution.pop(); //backtrack
}
return false;
}
/**
* Check consistency of the partial solution
* @param sheep if the sheep is on the right bank, false otherwise
* @param cabbage if the cabbage is on the right bank, false otherwise
* @param wolf if the wolf is on the right bank, false otherwise
* @param farmer if the farmer is on the right bank, false otherwise
* @return true if the solution is consistent, false otherwise
*/
private static boolean checkConsistency(boolean sheep, boolean cabbage, boolean wolf, boolean farmer) {
if (sheep == cabbage && sheep != farmer) {
return false;
} else if (sheep == wolf && sheep != farmer) {
return false;
}
return true;
}
/**
* Prints out the solution of the sheep-cabbage-wolf problem
* @param solution
*/
private static void printSolution(Deque<String> solution) {
while (!solution.isEmpty()) {
System.out.print(solution.pollLast() + " ");
}
System.out.println();
}
% farmer, sheep, cabbage, wolf start :- transport(left, left, left, left, empty, X). opposite(left, right). opposite(right, left). safe(X, X, X). safe(X, Y, Z) :- X \\= Y. transport(right, right, right, right, _, []). transport(F, K, Z, V, B, X) :- B \\= empty, opposite(F, F2), safe(K, Z, F2), safe(K, V, F2), transport(F2, K, Z, V, empty, X1), append([farmer], X1, X). transport(F, K, Z, V, B, X) :- F == V, B \\= wolf, opposite(F, F2), opposite(V, V2), safe(K, V2, F2), safe(K, Z, F2), transport(F2, K, Z, V2, wolf, X1), append([wolf], X1, X). transport(F, K, Z, V, B, X) :- F == K, B \\= sheep, opposite(F, F2), opposite(K, K2), safe(K2, Z, F2), safe(K2, V, F2), transport(F2, K2, Z, V, sheep, X1), append([sheep], X1, X). transport(F, K, Z, V, B, X) :- F == Z, B \\= cabbage, opposite(F, F2), opposite(Z, Z2), safe(K, Z2, F2), safe(K, V, F2), transport(F2, K, Z2, V, cabbage, X1), append([cabbage], X1, X).