The hobbits and orcs problem

There are several solution paths for the hobbits and orcs problem^{1}. The following table shows one of them (b = boat, H = hobbit, O = orc):

Step | Starting bank | Journey | End bank |
---|---|---|---|

start | bHHHOOO | ||

1 | bHHOO | bHO → | |

2 | bHHOO | ← bH | O |

3 | bHHH | bOO → | O |

4 | bHHH | ← bO | OO |

5 | bHO | bHH → | OO |

6 | bHO | ← bHO | HO |

7 | bOO | bHH → | HO |

8 | bOO | ← bO | HHH |

9 | bO | bOO → | HHH |

10 | bO | ← bH | HHOO |

11 | bHO → | HHOO | |

12 | HHHOOO |

There is a particular point in this solution path where people get into difficulties, and that is Step 6. At this point the action that needs to be taken is to move one creature of each type back to the first side of the river. This seems to be decreasing the similarity between current state and goal state, hence conflicts with the difference reduction heuristic. Consequently, about a third of participants prefer to go back to Step 5^{2}.

### Back to Problem solving

page revision: 10, last edited: 10 Apr 2009 11:25