Exercise Session #6
Exercise 1. Solve the following river-crossing puzzle using ASP. This is the description of the puzzle from Wikipedia:
In the missionaries and cannibals 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, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board.
So, there is a river with two banks, and one boat that can cross the river. Initially, the three missionaries, the three cannibals and the boat are on one bank, and the goal is to get all missionaries and cannibals to the other bank. The boat can cross with either one or two people aboard. It may never happen that, on either of the banks, the cannibals outnumber the missionaries (and there is at least one missionary on that bank). How can all people get to the other side, taking into account this restriction, and what is the smallest number of river crossings to achieve this goal?
Hints:
View this puzzle as a planning problem:encode the initial state of the world,
express what actions are available,
generate a sequence of actions to perform,
express the changes in the state of the world (at subsequent time steps) based on the actions performed,
express that the performed actions are possible (based on the state of the world when they are performed),
express a constraint that the goal must be reached.
The shortest solution involves 11 moves.
Exercise 2. Use ASP to find a shortest solution to the following sliding puzzle, that works as follows. It is played on a 3×3 grid, where 8 of the 9 cells are filled with a piece—and so the last remaining cell is empty. You may move, into the empty cell, one of the pieces from the directly neighboring cells. You are given an initial configuration of the grid (Figure 1a), and a goal configuration of the grid (Figure 1b), and the task is to find a sequence of moves that leads from the initial configuration to the goal configuration.
(a) The initial configuration (b) The goal configuration Figure 1: Initial and goal configuration for the sliding puzzle.
Hints:
Again, view this puzzle as a planning problem.
The shortest solution involves 30 moves.
