A simple Python 3 script to brute force a minimal solution to the Rush Hour game.

rushsolver.py

# Rush Hour Solver
# rushsolver.py
# Daniel Rothfus
# This is a fairly slow brute force solver for the game Rush Hour.  This solver
# was inspired by http://acm2013.cct.lsu.edu/localdoc/problems-scripting/1.pdf
# Please note that this solver was made for Python 3, not Python 2.
#
# To use this script, first input the character that will represent the special
# car to remove from the right side of the grid in the following board.  Next,
# input the board in ASCII art on the next 6 rows.  Periods should be used to
# represent empty spaces and each car on the grid should be represented by a
# unique letter that fills all of its initial locations.  (The escapting car
# must have the previously specified special character.) This program will 
# output a minimum number of steps to solving the puzzle if the the board is not
# already solved or that it has no solution. 
#
# An example input, not including comments, would be:
#
# A
# KLG.BB
# KLG.CC
# ....DD
# EE....
# ...HIJ
# AA.HIJ
#
# This program is released under the MIT license:
# Copyright (c) 2013 Daniel Rothfus
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

import heapq

# Format for piece layout is (r, c, rDir, cDir, length, symbol)
# A board, as used in the visited set, is stored as a tuple of all pieces.
# Format for elements in open set (turnNum, board)

def isValid(board):
    "Returns if the cars on the board are in a valid setup or not."
    used = [[False for c in range(6)] for r in range(6)]

    for piece in board:
        r = piece[0]
        c = piece[1]
        for q in range(piece[4]):
            if used[r][c]:
                return False
            used[r][c] = True
            r += piece[2]
            c += piece[3]
    return True

def reachedGoal(board, special):
    "Return true if the special car is in the target position."
    for piece in board:
        if piece[5] == special and piece[1] == 6 - piece[4]:
            return True
    return False

def printBoard(board):
    "Outputs the board to the screen."
    chars = [['.' for c in range(6)] for r in range(6)]
    
    # Put all pieces on the board
    for piece in board:
        r = piece[0]
        c = piece[1]
        for q in range(piece[4]):
            chars[r][c] = piece[5]
            r += piece[2]
            c += piece[3]
    
    # Print the board to the screen
    for row in chars:
        print("".join(row))

def parseBoard():
    "Read a board specification from standard input."
    pieces = {} 
    board = [input() for a in range(6)]
    
    for r in range(len(board)):
        for c in range(len(board[r])):
            if board[r][c] != '.':
            
                # Update direction if necessary         
                if board[r][c] in pieces:
                    piece = pieces[board[r][c]]

                    # See if we have an undefined direction
                    if piece[2:4] == [0, 0]:
                        piece[2] = r - piece[0]
                        piece[3] = c - piece[1]

                    # Add one to length
                    piece[4] += 1
                    pieces[board[r][c]] = piece
                else:
                    pieces[board[r][c]] = [r, c, 0, 0, 1, board[r][c]]
    
    # Return a tuple of all pieces
    return tuple([tuple(a) for a in pieces.values()])

def printSolution(end, parents):
    "Print the solution step by step where end is the ending target and parents\
    is a mapping of a move to its parent move."
    parent = parents[end]
    if(parent):
        level = printSolution(parent, parents)
        print("Step %d:" % level)
        printBoard(end)
        print()
        return level + 1
    else:
        print("Beginning:")
        printBoard(end)
        print()
        return 1

# Read in special character
special = input()

# Parse board
firstBoard = parseBoard()
solved = False

# Check if first board is solution
if reachedGoal(firstBoard, special):
    print("Already Solved")
    print()
    solved = True

# Add initial board to visited set
visited = {firstBoard: None}
openSet = [(0, firstBoard)]

# Now try to brute force all in open set
while len(openSet) > 0 and not solved:

    # Work off of current cheapest
    turn, pieces = heapq.heappop(openSet)
    
    # For each piece
    for p in range(len(pieces)):
        piece = pieces[p]

        # Find all different moves based on its direction of sliding
        forwardMoves = []
        backwardMoves = []
        if piece[2]:
            forwardMoves = ((pos, piece[1], piece[2], piece[3], piece[4], piece[5]) for pos in range(piece[0] + 1, 6 - piece[4] + 1))
            backwardMoves = ((pos, piece[1], piece[2], piece[3], piece[4], piece[5]) for pos in range(piece[0] - 1, -1, -1))
        else:
            forwardMoves = ((piece[0], pos, piece[2], piece[3], piece[4], piece[5]) for pos in range(piece[1] + 1, 6 - piece[4] + 1))
            backwardMoves = ((piece[0], pos, piece[2], piece[3], piece[4], piece[5]) for pos in range(piece[1] - 1, -1, -1))

        # Check out what each move would look like
        for moveSet in (forwardMoves, backwardMoves):
            for move in moveSet:
                tmpCollection = list(pieces)
                tmpCollection[p] = move
                newPieces = tuple(tmpCollection)
                
                # Check if board with new move is valid
                if not isValid(newPieces):
                    break
                
                if newPieces not in visited:
                    visited[newPieces] = pieces
                    heapq.heappush(openSet, (turn + 1, tuple(tmpCollection)))
                    
                    if reachedGoal(newPieces, special):
                        printSolution(newPieces, visited)
                        solved = True

# If we get here, we could not solve the puzzle
if not solved:
    print("No Solution")
    print()