Rook Jumping Maze Evaluation

Rook Jumping Maze Instructions: Starting at the circled cell in the upper-left corner, find a path to the goal cell marked G.  From each numbered cell, one may move that exact number of cells horizontally or vertically in a straight line.  How many moves does the shortest path have?

Solution (select to reveal): [19 moves: RDLRUDRLRLUDLDRRUDD]

Problem:  Generate and print a random 5-by-5 Rook Jumping Maze (RJM) where there is a legal move (jump) from each non-goal state.  Then, for each cell, compute and print the minimum number of moves needed to reach that cell from the start cell, or "--" if no path exists from the start cell, i.e. the cell is unreachable.

First, generate and print a random 5-by-5 Rook Jumping Maze (RJM) according to the Rook Jumping Maze Representation specification.

There are many features of a good RJM.  One obvious feature is that the maze has a solution, i.e. one can reach the goal from the start.  One simple measure of maze quality is the minimum number of moves from the start to the goal.  For simplicity, we will limit our attention to these, although consideration of other features is an interesting exercise (see Maze Evaluation II).

Using breadth-first search, or some other suitable graph algorithm, compute the minimum distance (i.e. depth, number of moves) to each cell from the start cell.  Create an objective function (a.k.a. energy function) that returns the negated distance from start to goal, or a large positive number (e.g. 1,000,000) if no path from start to goal exists.  Then the task of maze generation can be reformulated as a search through changes in the maze configuration so as to minimize this objective function.

Possible background readings include:

Input Format:  (no input)

Output Format:

Sample Transcripts:

2 2 2 4 3 
2 2 3 3 3 
3 3 2 3 3 
4 3 2 2 2 
1 2 1 4 0 

Moves from start:
 0  3  1  4  2 
 7  5  5  6  4 
 1  4  2  2  3 
 5  6  4 --  3 
--  4  3  4  5 

-5

3 3 2 4 3 
2 2 2 1 1 
4 3 1 3 4 
2 3 1 1 3 
1 1 3 2 0 

Moves from start:
 0  4 --  1  5 
 2 --  3  5  4 
 4  4  3  3  5 
 1  3  2  3  4 
 4  3  3  2 -- 

1000000

2 1 3 3 4 
4 3 2 3 4 
3 2 2 1 4 
2 1 3 1 2 
2 2 1 1 0 

Moves from start:
 0  7  1 -- -- 
 4  8 --  3  5 
 1  6  3  2  3 
-- --  2  3  4 
--  5  4  4  5 

-5

Todd Neller