Block Mazeexpert series
This is the first of two maze problems. The routes to the goal in this case are easy to see. The problem for the solver is to find the shortest route. Of course, you can solve the problem yourself; it is less easy to represent it to the automatic solver.
Above is a simple grid, with some small squares blocked out:
There is a robot in square Ad, and it needs to find its way to the goal in square Dd. At each step it can move to any adjacent square (North, South, East or West) but must avoid the blocked ones.
Find the shortest path it can follow (note that there are 4 equally short paths, so the solution is not unique).
See the “Muddle Management” example on page 5 of the guide for an example showing how to use a non-enumerated sort to make the solver return the smallest solution.
Solutions to this problem exist that will run in less than a second. If the solver is timing out, try putting the function declarations in a different order, and avoid the “hidden” annotation until you are getting an efficient search.
A neat extension of the problem, after you have produced a good encoding that runs fast, is to find a way of making the solver pretty-print the solution. For example, here’s one:
Model 1
path | a b c d e f
–––––+–––––––––––––––––
A | 0
B | 1 2 3
C | 4
D | 11 5
E | 10 6
F | 9 8 7
Solutions found: 1
If that was too easy, try this version: suppose we don’t know which square the robot will be in. Generate a policy to tell it which way to move. That is, find a function which assigns to every non-blocked square (except Dd) a direction, such that following the policy always results in a shortest trajectory to the goal.
Solver
Auto Parser Results
No errors found.