# River Crossing

## Task

A farmer has five animals on one side. He needs to get all animals to the other
side of the river. Unfortunately, he only has two spaces available on his boat
and some animals cannot be left on their own. Find a series of boat crossings to
get all animals to the other side.

## Animals

* 2 Wolves 
* 1 Fox 
* 1 Chicken 
* 1 Worm

## Constraints

* Wolves eat foxes. 
* Wolves eat chickens. 
* Foxes eat chickens. 
* Chickens eat worms. 

## Solution

The problem is solved using Answer Set Planning in
[DLV](https://www.dlvsystem.it/dlvsite/dlv-download/) with the planning
frontend. The planning frontend can be invoked with the `-FP` switch.

The command to run the solver is

```bash
dlv -FP -n=1 -stats -planlength=7 -planminactions=1 -planmaxactions=1 crossing.plan crossing.bk
```

```
STATE 0: boat_here, here(wolf1), here(wolf2), here(fox), here(chicken), here(worm)
ACTIONS: crossTogether(chicken,fox)
STATE 1: here(wolf1), here(wolf2), -here(fox), -here(chicken), here(worm), -boat_here
ACTIONS: cross(fox)
STATE 2: here(wolf1), here(wolf2), here(fox), -here(chicken), here(worm), boat_here
ACTIONS: crossTogether(fox,worm)
STATE 3: here(wolf1), here(wolf2), -here(fox), -here(chicken), -here(worm), -boat_here
ACTIONS: cross(chicken)
STATE 4: here(wolf1), here(wolf2), -here(fox), here(chicken), -here(worm), boat_here
ACTIONS: crossTogether(wolf1,wolf2)
STATE 5: -here(wolf1), -here(wolf2), -here(fox), here(chicken), -here(worm), -boat_here
ACTIONS: cross(fox)
STATE 6: -here(wolf1), -here(wolf2), here(fox), here(chicken), -here(worm), boat_here
ACTIONS: crossTogether(chicken,fox)
STATE 7: -here(wolf1), -here(wolf2), -here(fox), -here(chicken), -here(worm), -boat_here
PLAN: crossTogether(chicken,fox); cross(fox); crossTogether(fox,worm); cross(chicken); crossTogether(wolf1,wolf2); cross(fox); crossTogether(chicken,fox)
```