Koza, zelí, vlk

Koza, zelí, vlk je logická hádanka, v níž hráč (převozník) musí přemístit kozu, zelí a vlka z jednoho břehu řeky na druhý. Ve hře platí následující pravidla:

Hráč má k dispozici loďku, do níž se vejde převozník a maximálně jeden předmět.
Loďku musí vždy řídit převozník.
Pokud zůstanou spolu na jednom břehu bez dozoru převozníka koza a vlk, tak vlk sežere kozu.
Pokud zůstane spolu na jednom břehu bez dozoru převozníka koza a zelí, tak koza sežere zelí.

Strojové řešení

Z algoritmického hlediska se jedná o prohledávání stavového prostoru s návratem (backtracking). Backtrackingový algoritmus v každém svém kroku zkusí převézt jednu věc na druhý břeh a zkontroluje, jestli nedošlo k porušení podmínek úlohy (tj. nebyla sežrána koza nebo zelí). Pokud kontrola proběhne úspěšně, tak se proces opakuje. Pokud daný převoz způsobí nekonzistenci úlohy, tak se algoritmus vrátí do místa posledního rozhodnutí a převeze jinou věc (nebo se vrátí o rozhodnutí výše, pokud již byly všechny možnosti vyzkoušeny). Organizovaným prohledáváním ve stylu pokus-omyl algoritmus nalezne hledanou sekvenci kroků (řešení).

/**
 * 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). 

Strojové řešení

Kód

Doporučujeme