Solving a Logic Maze: Shortest Path to the Goal

[madameChing]

Hi guys,

I'm new to logic and have a logic maze to solve.
basically there is a "solver" program which takes in a set of predicates which must be satisfied to obtain a solution. here's a reproduction of the question below:

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.

Here is a simple grid, with some small squares blocked out:

        a     b     c     d     e     f

     +-----+-----+-----+-----+-----+-----+
     |     |     |     |  o  |     |*****|
  A  |     |     |     | [:] |     |*****|
     |     |     |     | / \ |     |*****|
     +-----+-----+-----+-----+-----+-----+
     |*****|     |*****|     |     |     |
  B  |*****|     |*****|     |     |     |
     |*****|     |*****|     |     |     |
     +-----+-----+-----+-----+-----+-----+
     |     |     |     |*****|     |     |
  C  |     |     |     |*****|     |     |
     |     |     |     |*****|     |     |
     +-----+-----+-----+-----+-----+-----+
     |     |*****|*****|     |*****|     |
  D  |     |*****|*****| [G] |*****|     |
     |     |*****|*****|     |*****|     |
     +-----+-----+-----+-----+-----+-----+
     |     |*****|     |     |*****|     |
  E  |     |*****|     |     |*****|     |
     |     |*****|     |     |*****|     |
     +-----+-----+-----+-----+-----+-----+
     |     |     |     |     |     |     |
  F  |     |     |     |     |     |     |
     |     |     |     |     |     |     |
     +-----+-----+-----+-----+-----+-----+

There is a robot in square Ad, and he needs to find his way to the goal (G) in square Dd. At each step he can move to any adjacent square (North, South, East or West) but must avoid the blocked ones.

Find the shortest path he can follow.

--------
There are 3 types of things to define: sorts, functions and the clauses (predicates that must be satisfied).

I have defined my sorts as such:
#sorts
row enum: A,B,C,D,E,F.

col enum:a,b,c,d,e,f.

dir enum: up,down,left,right.

---
then the functions:

pos: row,col -> int {partial all_different}

obs: row,col -> bool {print: none}

goal: row,col -> bool {print:none}

start: row,col -> bool {print:none}

next: row,col,dir -> bool{partial print:none}

---
note: partial means that the function may be undefined for certain arguments
all_different means no two arguments give the same value.

---
clauses - this is where I am stuck.
I want to tell the solver that there is a next cell if it is not an obstacle, it is not out of range and the goal has not been reached.

The solution should look something like:

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

So far, I have define some clauses :

pos(A,d) = 0 .x=B, y=d -> goal(x,y).

%define obstacles
obs(A,f).
obs(B,a).
obs(B,c).
obs(C,d).
obs(D,b).
obs(D,c).
obs(D,e).
obs(E,b).
obs(E,e).

%there does not exist a pos(x,y) at an obstacle
EST(x), EST(y), EST(pos(x,y)) -> NOT(obs(x,y)).

%this assigns a number to every cell except the obstacles (which is not exactly what i want of course).

---
sorry that it is a long post. any ideas/hints/tips very welcome and appreciated.

thanks!

 

[Hurkyl]

Wrap your preformatted text in [ code ] ... [ /code ] tags so it shows up right.

 

[madameChing]

Thanks for the tip Hurkyl!
much more comprehensible now. didn't know know to.

 

[NanoTec]

-I’m unfamiliar with the language or logic scheme you are using, but
-Here is the simplest algorithm for determining the path

Create an array: a grid a-f x A-F
Fill is array with a number > 6*6 = 36 ( assume least optimal )
Place a zero at the robots position.

Look at every cell in this array and…
If that cell has an adjacent cell to it ( which is not blocked or off the edge )
And the number in the adjacent cell is > the number in the current cell +1
Then assign that cell the number in the current cell +1
Repeat this until the goal is reached OR no cells are changed.

(Thinning it out to look like the solution)
Do not display any cell which does not have a higher neighbor OR is >= the number in the ‘goal’ unless it is the goal.

-If you want to tell the “solver” that there is a next cell it is as you stated, the adjacent cell is only a possibility if its not an obstacle, its not out of range, and the goal has not been reached. But there are few things you can do to directly eliminate any other possibilities without trying them.

-Note that the above method finds equivalent paths not shown in your solution, is this still correct?

To improve things quite a bit in terms of speed you can:
Only reevaluate cells adjacent to cells that have changed.
Make a pass though beforehand and add barriers to any cells with three adjacent barriers, repeat.
Simultaneously derive a path from the goal to the robot until it intersects the robot goal path.
Divide the board into quadrants around the goal, sum the barriers in each quadrant and have the search look in quadrants with the fewest barriers first.