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

view source
print?
01./**
02. * Solves the sheep-cabbage-wolf riddle and prints out its solution
03. */
04.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 otherwise
10. * @param cabbage true if the cabbage is on the right bank, false otherwise
11. * @param wolf true if the wolf is on the right bank, false otherwise
12. * @param farmer true if the farmer (boat) is on the right bank, false otherwise
13. * @param solution partial solution
14. * @return false if the partial solution is invalid
15. */
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(); //backtrack
30.    }          
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(); //backtrack
37.    }
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(); //backtrack
44.    }
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(); //backtrack
51.    }    
52.    return false;
53.}
54. 
55./**
56. * Check consistency of the partial solution
57. * @param sheep if the sheep is on the right bank, false otherwise
58. * @param cabbage if the cabbage is on the right bank, false otherwise
59. * @param wolf if the wolf is on the right bank, false otherwise
60. * @param farmer if the farmer is on the right bank, false otherwise
61. * @return true if the solution is consistent, false otherwise
62. */
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.}
71. 
72./**
73. * Prints out the solution of the sheep-cabbage-wolf problem
74. * @param solution
75. */
76.private static void printSolution(Deque<String> solution) {
77.    while (!solution.isEmpty()) {
78.        System.out.print(solution.pollLast() + " ");
79.    }
80.    System.out.println();
81.}
view source
print?
01.% farmer, sheep, cabbage, wolf                           
02.start :- transport(left, left, left, left, empty, X).
03. 
04.opposite(left, right).
05.opposite(right, left).
06. 
07.safe(X, X, X).
08.safe(X, Y, Z) :- X \\= Y.
09. 
10.transport(right, right, right, right, _, []).
11. 
12.transport(F, K, Z, V, B, X) :-
13.  B \\= empty,
14.  opposite(F, F2),
15.  safe(K, Z, F2),
16.  safe(K, V, F2),
17.  transport(F2, K, Z, V, empty, X1),
18.  append([farmer], X1, X).  
19. 
20.transport(F, K, Z, V, B, X) :-
21.  F == V,
22.  B \\= wolf,
23.  opposite(F, F2),
24.  opposite(V, V2),
25.  safe(K, V2, F2),
26.  safe(K, Z, F2),   
27.  transport(F2, K, Z, V2, wolf, X1),
28.  append([wolf], X1, X).
29. 
30.transport(F, K, Z, V, B, X) :-
31.  F == K,
32.  B \\= sheep,
33.  opposite(F, F2),
34.  opposite(K, K2),
35.  safe(K2, Z, F2),
36.  safe(K2, V, F2),
37.  transport(F2, K2, Z, V, sheep, X1),
38.  append([sheep], X1, X).
39. 
40.transport(F, K, Z, V, B, X) :-
41.  F == Z,
42.  B \\= cabbage,
43.  opposite(F, F2),
44.  opposite(Z, Z2),
45.  safe(K, Z2, F2),
46.  safe(K, V, F2),
47.  transport(F2, K, Z2, V, cabbage, X1),
48.  append([cabbage], X1, X).







  1. Home
  2. Puzzles
       
 

Place for your banner

Here is the position ready for our customer's banners.