- Read the puzzle description.
- Launch the applet by clicking on the button above.
- Ensure you have keyboard focus.
- Hit Enter to toggle plowing, use the arrow keys to move around.
- Configure the puzzle as desired.

The applet requires Java 1.5 or higher. It is known to work on Windows XP and Vista under Internet Explorer, Mac OS X Leopard under Safari, and Ubuntu Linux under Firefox.

The applet has a Control Panel on the left for configuring the parameters of the puzzle and has a representation of Grid City in the pane on the right. Each block is depicted along with its four entrances. The plow is represented by a small colored square. The plow is initially green and in the top left corner of Grid City.

As paths are plowed the number inside each block is updated to show its score - that is, the farthest that a pedestrian must walk from that block to get to a neighboring block (north, east, south or west).

In order for you to use the keyboard the Grid City pane must have keyboard focus, which means it is receiving the keystrokes that are being entered. Moving the mouse onto the Grid City pane should be enough to accomplish this, however you may need to cajole the applet to get keyboard focus. One thing that usually works is to click in an edit field in the Control Panel (e.g. the field for editing the number of blocks Grid City has going across) and then move the mouse over to the Grid City pane.

When the Grid City pane has keyboard focus it will be drawn with an interior border, as shown in the image below.

Closeup of Grid City pane with interior border indicating keyboard focus. |

- Move the plow to the desired starting position using the arrow keys.
- Hit Enter to turn the plow red and start plowing.
- Plow a path using the arrow keys.
- Hit Enter to end plowing.

If you have more than one plow (as specified by the "Plowing Rules") you can now position the next plow in its starting position and plow a second path.

The plow is green when it is not plowing and red when it is plowing.

Plowing a path. Tiny indicator arrows point to "offending blocks". |

When the maximum distance from a block to any of its neighbors is not zero, indicator arrows will point to the "offending" block or blocks - that is, the block or blocks that account for the maximum distance. To avoid clutter, no indication will be shown if the distance to all neighbors is infinity.

Indicator arrows can be seen in the image above.

Click on a block in Grid City to enter "Inspect Mode". The selected block will be shaded and red lines will be drawn to show the shortest paths (if any) to its adjacent blocks. Click on the block again to exit "Inspect Mode".

Inspect mode. Paths from the gray block to each neighbor are shown in red. |

- Dimension (blocks across and blocks down)
- These set the size of Grid City as shown in the right pane.
- Building entrances on corners/sides
- This determines the location of the entrances. A corner entrance
is accessible when the adjacent
*intersection*has been plowed; a side entrance is accesible only when the adjacent*street*has been plowed. - Walk through buildings
- When this is set, pedestrians are allowed to enter a building through one entrance and exit through another for the purposes of getting to another building. The cost (distance) involved in doing so is determined by the values in the "Configure Costs" dialog.
- Configure Costs dialog
- This allows you to set the distances involved in walking through a building from one entrance to another.
- Max # plows
- The total number of plows available. 0 indicates an unlimited number of plows. Plows are assumed to work in parallel even though their paths are specified one after the other.
- Max total streets
- The total number of streets that can be plowed by all of the plows. 0 indicates no limit.
- Only start on boundary
- When this is set, plowing must begin at an edge of Grid City. Otherwise plowing can begin anywhere in Grid City.
- Allow retrace
- Retracing is when a plow that is plowing moves over a street that has already been plowed. This is not allowed by default because it is assumed that pedestrians are walking on these streets.

- Score
- The score is the farthest anyone would have to travel to get to an adjacent block. It is the maximum of the scores shown on each block.
- Time
- Plowing a street takes 20 minutes. Moving without plowing takes a negligible amount of time. (Moving without plowing either happens when a plow is moved to its initial position before plowing starts, or when "Allow Retrace" is set and a plow is retracing a street that has already been plowed.) When multiple plows are involved they are assumed to plow in parallel. Therefore the total time reported is the maximum amount of time any plow takes to complete its plowing route.
- Max # Streets
- The most streets that have been plowed by any one plow.
- # Streets
- The number of streets that have been plowed by each plow.
- Plows Used
- The number of plows that have been used, including the current plow if it is currently plowing.
- Plows Left
- If "Max # plows" has been set, this shows the number of plows remaining.
- Streets Plowed
- The total number of streets that have been plowed by all plows.
- Streets Left
- When "Max total streets" has been set, this shows the number of streets that can still be plowed.

It is possible to specify an entire puzzle configuration in one go using the "Set Puzzle" dialog (bottom of the Control Panel). It is also possible to run a script (a sequence of key commands) using the "Run Script" dialog (also at the bottom of Control Panel). The dialog will come up with the key commands that have been entered so far.

*Because of Java applet security restrictions it is currently not
possible to copy from or paste to these dialogs.*

The applet should be reasonably responsive for small grid sizes (up to 8 x 10). For larger grid sizes the applet will become noticeably slow and may take several seconds to respond to an action. Currently the applet is not set up to show a busy cursor (e.g. hourglass) to indicate when it is performing a slow computation.

This section discusses the algorithm that is used internally to compute the shortest paths. The shortest paths have to be recomputed every time a street is plowed or any time a change is made to the configuration. Ideally this recomputation should occur within a few hundred milliseconds so that the user delay is minimal and the applet doesn't feel sluggish.

To compute the shortest paths between blocks I construct a graph where every intersection and every entrance is a vertex, and then I connect:

- adjacent intersections if the connecting street has been plowed, with an edge weight (distance) of 1.
- each corner entrance (if entrances are on corners) to its intersection if that intersection has been plowed, with an edge weight of 0.
- each side entrance (if entrances are on sides) to the two nearest intersections (weight=0.5) and the entrance across the street (weight=0), if that street has been plowed.
- entrances on the same block to each other, if "Walk through buildings" is checked. The edge weights are determined by the values in the "Configure Costs" dialog on the Control Panel and are defaulted to 1.

So with an 8x10 grid there are 99 intersections and 320 entrances for 419 vertices in total. If, for example, every street is plowed that makes 178 edges connecting intersections (9*10 for the north-south streets and 8*11 for the east-west streets). Each intersection can service up to four entrances (regardless of whether entrances are on corners or sides), yielding another 396 (=99*4) edges at most. If "Walk through buildings" is checked there are 480 (=80*choose(4,2)) edges connecting entrances within the blocks. So in the worst case there are 1054 edges (=178+396+480) for an 8x10 grid.

To compute the shortest paths I run Dijkstra's algorithm from each entrance vertex. Originally I used BFS which is much faster but Dijkstra's algorithm supports arbitrary nonnegative weights (e.g. for walking through buildings) and allows for a much more natural graph construction. The internal MIN-QUEUE inside Dijkstra is a naive linear implementation, so the total running time is O(V^3), that is, cubic in the number of vertices.

I considered all-pairs shortest paths algorithms but these are typically cubic or at best O(V^2 lg V) and for a graph this small I felt the extra overhead of the more complicated algorithm would offset the improvement in going from V to lg V. I also considered a binary MIN-QUEUE implementation so that finding the min would happen in log rather than linear time, but again for this number of vertices I felt the considerable overhead of managing the heap and keeping the handles in sync would not yield much improvement.

I did introduce a few optimizations that made a substantial difference in the response time of the applet.

- I only compute shortest paths from entrances (not all vertices).
- In Dijkstra's algorithm I terminate early if the item off the MIN-QUEUE has a distance of infinity from the source vertex. This means the graph is not connected. This optimization makes a huge difference in the beginning when most blocks are not connected.
- In Dijkstra's algorithm I terminate early if all the adjacent blocks are accounted for (since Dijkstra's algorithm guarantees that when a vertex is pulled off the queue, the computed path is a shortest path). This optimization makes a noticeable difference in the end when most blocks are connected.
- "Checkerboard Optimization": Adjacent blocks would have opposite colors on a checkerboard. Since this is an undirected graph and so shortest paths are symmetric, I only need to compute paths from blocks of one color. Naturally this leads to about a factor of two speedup.

*Written by Arefin Huq
Comments? Email me at arefin@gmail.com*