title: Rush Hour - Solving the game
body: <p><strong>Rush Hour</strong><br>
  if you're not familiar with it, the game consists of a collection of cars of varying sizes, set either horizontally or vertically, on a NxM grid that has a single exit.<br>
  Each car can move forward/backward in the directions it's set in, as long as another car is not blocking it. You can <strong>never</strong> change the direction of a car.<br>
  There is one special car, usually it's the red one. It's set in the same row that the exit is in, and the objective of the game is to find a series of moves (a move - moving a car N steps back or forward) that will allow the red car to drive out of the maze.  </p>
  
  <p>I've been trying to think how to solve this problem computationally, and I can really not think of any good solution.<br>
  I came up with a few:</p>
  
  <ol>
  <li>Backtracking. This is pretty simple - Recursion and some more recursion until you find the answer. However, each car can be moved a few different ways, and in each game state a few cars can be moved, and the resulting game tree will be HUGE.</li>
  <li>Some sort of constraint algorithm that will take into account what needs to be moved, and work recursively somehow. This is a very rough idea, but it is an idea.</li>
  <li>Graphs? Model the game states as a graph and apply some sort of variation on a coloring algorithm, to resolve dependencies? Again, this is a very rough idea.  </li>
  <li>A friend suggested genetic algorithms. This is sort of possible but not easily. I can't think of a good way to make an evaluation function, and without that we've got nothing.</li>
  </ol>
  
  <p>So the question is - How to create a program that takes a grid and the vehicle layout, and outputs a series of steps needed to get the red car out?  </p>
  
  <p>Sub-issues:</p>
  
  <ol>
  <li>Finding <strong>some</strong> solution.</li>
  <li>Finding an <strong>optimal</strong> solution (minimal number of moves)</li>
  <li>Evaluating how good a current state is</li>
  </ol>
  
  <p>Example: How can you move the cars in this setting, so that the red car can "exit" the maze through the exit on the right?<br>
  <a href="https://i.stack.imgur.com/NzztF.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NzztF.jpg" alt=""></a><br>
  <sub>(source: <a href="http://scienceblogs.com/ethicsandscience/upload/2006/12/RushHour.jpg" rel="nofollow noreferrer">scienceblogs.com</a>)</sub>  </p>