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 n-by-n Rook Jumping Maze (RJM) (5 £ n £ 10) where there is a legal move (jump) from each non-goal state.
Let array row and column indices be (rmin, ..., rmax) and (cmin, ..., cmax), respectively, where rmax - rmin+ 1 = cmax - cmin+ 1 = n. The RJM is represented by a 2D-array of jump numbers. A cell's jump number is the number of array cells one must move in a straight line horizontally or vertically from that cell. The start cell is located at (rmin, cmin). For the goal cell, located at (rmax, cmax), let the jump number be zero. For all non-goal cells, the randomly generated jump number must allow a legal move. In the example 5-by-5 maze above, legal jump numbers for the start cell are {1, 2, 3, 4}, whereas legal jump numbers for the center cell are {1, 2}. In general, the minimum legal jump number for a non-goal cell is 1, and the maximum legal jump number for a non-goal cell (r, c) is the maximum of rmax - r, r - rmin, cmax - c, and c - cmin. This defines a directed graph where vertices are cells, edges are legal jumps, and the outdegree is 0 for the goal cell vertex and positive otherwise.
Input Format: an integer 5 £ n £ 10
Output Format:
Sample Transcripts (input underlined):
Rook Jumping Maze size (5-10)? 5 3 2 4 4 4 3 1 2 2 2 2 1 1 2 2 1 3 2 2 1 2 4 4 3 0
Rook Jumping Maze size (5-10)? 6 5 2 1 1 1 2 4 3 4 3 1 5 5 2 3 1 4 1 3 1 2 1 4 1 3 4 1 1 4 5 4 3 4 5 2 0
Rook Jumping Maze size (5-10)? 10 6 2 4 6 6 8 3 7 2 5 3 7 1 6 2 6 8 8 8 5 8 8 7 4 3 6 5 6 5 2 1 8 1 6 1 4 5 7 5 1 7 5 6 4 5 4 1 7 4 9 3 8 4 2 3 3 3 6 4 9 8 3 1 2 3 5 1 4 5 4 5 8 3 1 7 2 7 3 5 9 9 1 4 5 7 5 7 6 8 2 4 6 3 7 6 2 5 9 1 0