See the board game/puzzle Rush Hour.
Througout this work, terminology from graph theory and finite state machines will be used interchangeably.
We consider the RH Graph. The nodes represent a given placement of cars and trucks on the RH board given the constraint that the red car is in the proper exit row. The edges represent a legal RH move of a single vehicle a single space.
The remainder of the notebook is focused on the following topics
Constructing the RH Graph
Defining feasibly computable subsests of the nodes of the RH Graph
combinatorial class
Two nodes $v_1$ and $v_2$ corresponding to RH boards $b_1$, $b_2$ are topologically equivalent if $b_1$ and $b_2$ have the same number of cars and if $b_1$ and $b_2$ have the same number of trucks.
A combinatorial class is the natural class from the partition induced by combinatorial equivalence.
* topological class
Two nodes $v_1$ and $v_2$ corresponding to RH boards $b_1$, $b_2$ are topologically equivalent if for each row $r_i$ in $b_1$ and $b_2$ have the same number cars and trucks in the same order.
A topological class is the natural class from the partition induced by topological equivalence.
TODO: insert examples of topologically equivalent nodes
* Brute force construction of all possible nodes (i.e. all possible arrangements of vehicles on RH board) within a defined subset of V(RH)
Recursive algorithm coupled with generating function
* Compute Edges and Components
* Compute breadth-first forrest of a given topological class.
* Start with list of all nodes for a given topological class
* Explicitly construct neighbors for a given node.
* Apply bookeeping to the list to the list of nodes
* Compute Solution Paths
Graphical Node Traversal of RH Graph
Graph Analytics
Global metrics
Component Analysis
We assume the red car is in the proper exit row. Given this assumption, possible arrangement of cars and trucks represents a state. A legal Rush Hour move represents a transition from one state to another.
Back of the napkin suggest the set of states alone is nearly a 1TB of data.
My approach requires having a full graph in ram. The first step is to cut down the state graph to sub graphs containing a reasonable number of connected components.
From the state graph, we compute nested subsets of states based on numerical or geometric propeties. From there we produce connected components. Then starting with the final states, we compute the minimal solution paths. All nested structures and solution paths are persisted to a database.
First consider segmenting the set of states purely by the number of cars and trucks $(c,t)$ on the board. With the red car fixed to the exit row, this gives us 60 combinatorial classes.
Given two states $x, y$ with rows $x_{r_i}$ and columns $x_{c_i}$ with $0 < i <7$ and $y$ with with $y_{r_i}$ and ${y_{c_i}$. Then $x$ and $y$ are topologically equivalent if and only if $x_{r_i}$ has the same number of cars and trucks as $y_{r_i}$ and $x_{c_j}$ has the same number of cars and trucks as $y_{c_j}$. Note, a topological class is a subgraph of the full RH Graph, but that topological graph is not necessarily connected.
A state S in the RH Graph is solvable if there is a solution path that contains $s$.
The full set of states in the RH Graph is brute force computed one combinatorial class at a time.
Configuration
In [5]:
CombClasses = [(c,t) for c in range(1,13) for t in (0,1,2,3,4)]
In [6]:
len(CombClasses)
Out[6]:
In [50]:
from matplotlib.path import Path
import matplotlib.patches as patches
board_background = [["","0.75",[(x,y) for x in range(6) for y in range(6)]]]
placements = board_background + [ ["X","red",[(2,1),(2,2)]] ,["Q","green",[(2,4),(3,4),(4,4)] ], ["R",'pink',[(5,2),(5,3)] ]]
codes = [Path.MOVETO,Path.LINETO,Path.LINETO,Path.LINETO,Path.CLOSEPOLY]
fig = plt.figure()
ax = fig.add_subplot(231)
plt.axis('off')
ax.set_xlim(0,7.)
ax.set_ylim(0,7.)
for x in placements:
color = x[1]
text = x[0]
for y in x[2]:
verts = [(y[1],6-y[0]), (y[1]+1,6-y[0]), (y[1]+1,6-y[0]-1),(y[1],6-y[0]-1),(0.,0.)]
path = Path(verts,codes)
patch = patches.PathPatch(path, facecolor=color,lw=1)
ax.add_patch(patch)
ax.text( y[1]+.5,6 - y[0]-.5,text,horizontalalignment='center',verticalalignment='center',weight='bold')
ax = fig.add_subplot(233)
plt.axis('off')
ax.set_xlim(0,6.)
ax.set_ylim(0,6.)
offset = 0
for x in placements:
color = x[1]
text = x[0]
for y in x[2]:
verts = [(y[1],6-y[0]), (y[1]+1,6-y[0]), (y[1]+1,6-y[0]-1),(y[1],6-y[0]-1),(0.,0.)]
path = Path(verts,codes)
patch = patches.PathPatch(path, facecolor=color,lw=1)
ax.add_patch(patch)
ax.text( y[1]+.5,6 - y[0]-.5,text,horizontalalignment='center',verticalalignment='center',weight='bold')
ax = fig.add_subplot(232)
plt.axis('off')
ax.set_xlim(0,3)
ax.set_ylim(0,6)
ax.arrow(0,3,3,0, head_width=.5, head_length=.5,shape="full",length_includes_head="True",color="Black")
plt.show()
We now start with computing the states of the RH Graph. We compute the states for a single given combainatorial class at a time. This approach permits a natural recursive solution that is relatively straight forward to reason thorugh for correctness. We make use of generators to compute the states for two reasons: we can compute the very large sets of states within limited RAM and we are able to decouple the computation of the states from the persistence logic.
In [ ]:
The RH Graph has far too many vertices to hold in RAM on my machine. Furthermore, computing edges and additional structures puts further pressure on memory. The next section describes approaches to build subgraphs of the RH Graph.
Combinatorial Class
Two vertices $v_1$ and $v_2$ in the RH Graph are in the same combinatorial class if the associated boards $b_1$ and $b_2$ have the same number of cars and trucks. Since any edge in the RH Graph must connect two vertices with the same number of cars and trucks, we can see that the vertices in a given combinatorial class induce a subgraph of the RH graph.
Topological Class
Two vertices $v_1$ and $v_2$ are in the same topological class if the associated boards $b_1$ and $b_2$ exhibit the following properties:
Note that a topological class is a refinement of a combinatorial class.
We have a straight forward recursive algorithm to generate all vertices within a given combinatorial class. At the time a vertex $v$ is generated, we can ascertain and note that the topological class of that $v$.
In [ ]:
topological_class = 10
In [ ]: