Lab 6: Backtracking
The point of this lab is to search and backtrack. The domain will
be a maze, and it will be a relatively simple maze. The system
should try a path. If it fails it should backtrack and try a
- Here is a maze:
- S is the start, and G is the goal.
Encode the maze as a series of facts. I did it with
- At any point there will be at most three choices,
with one of those choices being where you came from; this means
that you only need to remember one possible place to back up to
at each point.
- There will be no cycles. This means that you can't get back
to a place you've already been without backing up.
- Make a system that solves every maze with the two simplifications.
There are at least three ways to do this:
- Solve this particular problem, then try to fix it up.
- Solve it in sections. Here's the way I broke the problem down.
- Make a rule that moves the user. Be careful, if you run, the
rule might loop (use the Execution menu with the Halt item).
- Modify the rule so that it remembers where it's been and
doesn't go back.
- Implement backtracking. I did this in three steps.
- Make a new rule that works when there are two options, travel
down one and stack the other. I had to use a neq test on
this. I also used (declare (salience 10)) so that the
two option rule is preferred over the one option rule.
- Modify the rule so that it stacks the alternative. I used
a stackHt and stack variable and filled in the untaken path.
I only kept one instance of stackHt but had one variable
for each stack element.
- Add a rule to backtrack when there are no other options. That
is, if there is a deadend, pop the stack and move to that
- Add a rule to stop when the user is at the goal.
- Try to solve it all in one step. The eventual solution I get
has seven rules.
- Design your own maze and show the system running on it.
- Are you confident it will run on all reasonable mazes?
- What will happen if there are cycles?
- What would you do if there were more than three choices at any