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: Using a form of stochastic local search called Hill Descent, search the space of 5-by-5 Rook Jumping Mazes (RJMs) for a given number of iterations and print the best maze evaluated according to the objective function specified by Rook Jumping Maze Evaluation.
Given a number of iterations from the user, first generate a random 5-by-5 Rook Jumping Maze (RJM) according to the Rook Jumping Maze Representation specification and evaluate it according to the Rook Jumping Maze Evaluation specification. Then for the given number of iterations:
Finally, print the RJM with the best (minimum) objective function evaluation according to the Rook Jumping Maze Evaluation output specification.
More formally, let jump function j be a mapping from cells to legal jump numbers, or 0 in the case of the goal cell. Let objective function (or energy function) e be a function we seek to minimize over jump functions. Let step be a function that takes a jump function j, and generates a "neighboring" jump function j' by making a single, stochastic change: function step chooses from non-goal cells with equal probability, and for that cell c chooses j'(c) from all legal jump numbers not equal to j(c) with equal probability. For all other cells, j'(c) = j(c). Then we may describe our algorithm as follows:
Possible background readings include:
Input Format: a positive integer number of iterations for hill descent optimization
Output Format:
Sample Transcripts (input underlined):
Iterations? 100 1 4 2 2 2 3 2 1 3 3 2 2 1 2 2 3 1 2 2 4 1 4 2 3 0 Moves from start: 0 1 8 8 9 1 8 7 2 -- -- 6 8 7 10 3 5 6 4 7 2 2 -- 3 11 -11
Iterations? 1000 1 2 1 2 2 4 3 1 2 4 4 2 1 3 1 1 3 2 2 3 2 4 1 1 0 Moves from start: 0 1 8 2 7 1 10 9 10 2 4 2 10 3 5 12 7 11 11 6 13 3 14 15 16 -16
Iterations? 10000 1 4 2 3 2 3 3 1 3 2 3 3 2 2 4 1 1 3 3 1 3 2 3 3 0 Moves from start: 0 1 12 7 13 1 16 15 2 17 5 3 13 6 4 9 10 11 8 18 2 2 14 3 19 -19
Questions: