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:

• Russell and Norvig. Artificial Intelligence: A Modern Approach, 3rd edition, Chapter 3 through section 3.4.1 (breath-first search). 
• Cormen et al.  Introduction to Algorithms, 3rd edition, Section 22.2 (breadth-first search)
• Wikipedia article on "Breadth-first search"

Input Format:  (no input)

Output Format:

• Print a randomly generated 5-by-5 RJM 2D-array of jump numbers, with jump numbers separated by a single space.
• Print a blank line.
• Print "Moves from start:" on a single line.
• Print the 2D-array of corresponding cell depths (i.e. min. moves from start) separated by spaces.  For unreachable cells, print "--".  For other cells, print the depth right-justified in a width of two characters.
• Print a blank line.
• Print the output of your objective function on a single line.

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