# Rook Jumping Maze Evaluation II

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:  Define a better maze evaluation function and argue why it leads to improved maze quality.  Compare and contrast the results obtained with your new evaluation function versus the previous evaluation function using the same stochastic local search technique for each.

There are many features of a good Rook Jumping Maze (RJM).  Previously, we evaluated RJMs according to solvability and the shortest distance to the goal.  However, there are many other features that may be considered as well.  Here, we describe a few:

• Black holes* - A black hole is a dead-end.  Define a reachable cell to be a cell one can reach from the start through a sequence of legal moves.  Define a reaching cell to be a cell from which one can reach the goal through a sequence of legal moves.  A cell is part of a black hole if it is a reachable, non-reaching cell.
• White holes* - Some puzzlers seek to trace backwards from the goal to the start.  A white hole is a back-tracing dead end.  A cell is part of a white hole if it is an unreachable, reaching cell.
• Start and goal positions - Is anything gained/lost by allowing the position of the start and/or goal cell to vary?
• Shortest solution uniqueness - How does knowledge that there is a unique shortest solution affect the maze solving experience?
• Forward/backward decisions - Sometimes there is only a single legal "forced" move from a cell.  How do the number of forward decisions affect the maze solving experience?  This is related to a game-tree branching factor.  Initial forced moves are especially noticeable.  For back-tracing puzzlers, consider also the number of backward decisions, i.e. the number of cells for which there are multiple possible predecessors.
• Same jump clusters - Same jump clusters are sets of cells that all have the same jump number and reach each other without leaving the cluster.  For example, consider the maze above. The two leftmost 3s of the second row and the 3 of the bottom row form a 3-jump cluster.   How do same-jump clusters affect the maze solving experience?  Are some better than others?
• Solution direction variability - Again, consider the maze above.  Part of the shortest solution begins at the second 3 in the third row and proceeds right-left-right-left.  How does such back-and-forth within the same row or column affect the maze solving experience?

Select one or more of the features above that you consider most important, compute measures for maze evaluation, and seek to improve upon the previous RJM evaluation function.  Generate sets of puzzles using the old and new evaluation functions, compare and contrast the puzzles, and argue why your new evaluation function improves the average quality of your mazes.

*The descriptive maze terms "black hole" and "white hole" were coined by maze designer Adrian Fisher.

Possible background readings include:

Todd Neller