Background
A very common problem when teaching about algorithms and data structures is to find the shortest path between two points in a maze, where the maze is represented as a grid and each square is either clear or blocked. For example we might be given a grid like this, where black squares are blocked, and told to find the shortest path length between the two red squares. For example in this case the shortest path is shown in purple:
I’m not going to ask you to solve that problem. If you never did this kind of thing before, then it’s pretty fun, and it’s a very useful algorithm in real-life programming – but we’re going to look at a slightly less common problem.
The problem
The challenge is that given 2 points (x1,y1) & (x2,y2), and a square NxN grid, you have to build a maze which maximises the shortest path between the 2 points. In other words the grid starts off all white squares, and you have to add black squares to make the shortest possible journey from one point to the other as long as it can be. You can’t make it impossible to get between the 2 points, and you can’t block either of the two points given.
There are 2 versions of this problem. The easier version is simply to write a function which returns the maximum length the shortest path could be, given x1,x2,y1,y2 & N.
The harder version requires you to also calculate the smallest number of cells in the grid you must block to achieve this path length.
Obviously it gets harder as the grid gets bigger. Initially, how about a solution that would take no more a than a couple of seconds for N<=20. If you can do that, then what about for N=100?
Example function signature (C/C++/Java/C#):
void nastyMaze(int x1,int y1,int x2,int y2,int N);
Please feel free to post your ideas or code as comments. If you find the problem interesting, please tell me – if you find it too hard or too boring then please tell me that too!
December 6, 2007 at 3:49 pm |
Why is the function void? I would expect an int.
December 6, 2007 at 3:58 pm |
It could be. Or you can print out the answer from within the function. I just gave the signature to make it clear what the input variables are.
December 6, 2007 at 6:10 pm |
Ok, I saw “write a function which returns”, that’s why I expected an int.
December 9, 2007 at 6:00 pm |
For a start I made a brute force search. I had no idea how fast it would be, but it was possible to solve the example case fast enough. The longest path is 34 with this maze:
####…#
####F#.#
#S..##..
###…#.
…##.#.
.#….#.
..#####.
#…….
What I do is basically a depth first search from start to finish where I stop when I enter a square that is adjacent to a square previously in the path.(Except the preceding square of course.) The rest of the maze is blocked. I think this gives the right answer for part one.
Maybe I should prune way more, in cases where it’s impossible to reach the finish square or find a clever way for an upper bound given a begin of a path, but I have no good idea how to do that.
100*100 seems impossible with this approach, but it gives nice pictures for small cases.
Here is the (java) code:
import java.util.*;
public class Maze
{
static int MAXN=10;
static int W=MAXN+2;
static int[] field=new int[W*W];
static int[] path=new int[W*W];
static int[] vis=new int[W*W];
static int longest;
static int x1,y1,x2,y2,N;
static long time;
static int transform(int x, int y)
{
return (y+1)*W+x+1;
}
static int[] detransform(int z)
{
return new int[]{(z%W)-1,(z/W)-1};
}
static void go(int z, int d)
{
if(vis[z]>1)
{
if(vis[z]==11 && d>=longest)
{
longest=d+1;
System.out.println(“new longest: “+longest+”. found after: “+(System.currentTimeMillis()-time)/1000.0+” seconds”);
for(int i=0;i<d;i++)
path[i]=field[i];
path[d]=z;
drawMaze();
}
}
else
{
field[d]=z;
vis[z]++; vis[z+1]++; vis[z-1]++; vis[z+W]++; vis[z-W]++;
go(z+1,d+1); go(z-1,d+1); go(z+W,d+1); go(z-W,d+1);
vis[z]–; vis[z+1]–; vis[z-1]–; vis[z+W]–; vis[z-W]–;
}
}
static void initMaze(int xx1,int yy1, int xx2, int yy2, int NN)
{
longest=0;
x1=xx1; y1=yy1; x2=xx2; y2=yy2; N=NN;
System.out.println(“\n***************************************”);
System.out.println(“* Testcase: x1=”+x1+”, y1=”+y1+”, x2=”+x2+”, y2=”+y2+”, N=”+N);
System.out.println(“***************************************”);
Arrays.fill(vis,2);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
vis[transform(i,j)]=0;
}
static int nastyMaze(int xx1,int yy1, int xx2, int yy2, int NN)
{
initMaze(xx1, yy1, xx2, yy2, NN);
int start=transform(x1,y1);
int goal=transform(x2,y2);
vis[start]=1;
vis[goal+1]=10; vis[goal-1]=10; vis[goal+W]=10; vis[goal-W]=10;
time=System.currentTimeMillis();
go(start,0);
System.out.println(“\nsearch done. it took: “+(System.currentTimeMillis()-time)/1000.0+” seconds”);
drawMaze();
return longest;
}
static void drawMaze()
{
char[][] grid=new char[N][N];
for(int i=0;i<N;i++)
Arrays.fill(grid[i],’#');
for(int i=0;i<longest;i++)
{
int[] res=detransform(path[i]);
grid[res[1]][res[0]]=’.';
}
grid[y1][x1]=’S';
grid[y2][x2]=’F';
System.out.println(“draw maze:”);
for(int i=0;i<N;i++)
System.out.println(grid[i]);
System.out.println();
}
public static void main(String[] args)
{
System.out.println(“longest shortest path: “+nastyMaze(1,2,4,1,8)); // example case
System.out.println(“longest shortest path: “+nastyMaze(0,0,0,6,7)); // simple zig zag figure
System.out.println(“longest shortest path: “+nastyMaze(0,0,0,7,8));
System.out.println(“longest shortest path: “+nastyMaze(0,0,7,7,8));
System.out.println(“longest shortest path: “+nastyMaze(0,0,0,1,8)); // oops, cornercase
System.out.println(“longest shortest path: “+nastyMaze(3,3,6,6,9)); // nice path, but running time 21 sec
//This one takes 210 second on my computer, so I commented it out
//Best case is found after 14 seconds
//System.out.println(“longest shortest path: “+nastyMaze(0,0,8,8,9)); // simple zig zag good, but not best
}
}
December 10, 2007 at 11:07 am |
Nice problem!
January 28, 2008 at 1:32 pm |
Don’t you write programming problems anymore?
January 28, 2008 at 2:11 pm |
I had a document containing a lot, but it got lost… I’ll try to remember some or think up some new ones quite soon.
March 13, 2008 at 7:33 am |
You could use this for Desktop Tower Defense!
September 6, 2008 at 11:46 pm |
So you’re asking people for the A* method?
September 7, 2008 at 2:30 pm |
I don’t think so. You’re not finding the path through an existing maze, but finding a maze which makes the shortest possible path between two points as long as possible.
The naive way is to build every single possible maze and then test the shortest path between the points on each one.
But an NxN grid has N*N tiles and each can be filled/empty, so there are 2^(N*N) possible mazes. And then A*/BFS/DFS are not trivial (I think O(N^2)) that would give the whole algorithm something like O(2^(N^2).N^2) which is horrific!