A python version of the tile game solver

tilegame.py

def completion(board):
    "Returns a score of how far the board is from completion"
    total = 0
    for pos in range(9):
        i, j = pos // 3, pos % 3
        val = board[i][j] - 1
        if val < 0: continue
        v1, v2 = val % 3 - j, val / 3 - i
        total += (v1 if v1 > 0 else -1 * v1) + (v2 if v2 > 0 else -1 * v2)
    return total

def find_blank(board):
    y = 0 if -1 in board[0] else 1 if -1 in board[1] else 2
    x = 0 if board[y][0] == -1 else 1 if board[y][1] == -1 else 2
    return x, y

def simulate_move(old, (x, y), (bx, by)):
    board = ([old[0][0], old[0][1], old[0][2]],
             [old[1][0], old[1][1], old[1][2]],
             [old[2][0], old[2][1], old[2][2]])
    board[by][bx], board[y][x] = board[y][x], -1
    return tuple(board[0]), tuple(board[1]), tuple(board[2])

board_cache = {}
def best_move(board, previous_boards, last_move=None,
              blank=None, depth_limit=15):
    """
    Returns a tuple containing:
    - Best score
    - Last move
    - Best board
    """
    key = board
    if (depth_limit < 15 and key in board_cache and
        board_cache[key][2] != board and
        board_cache[key][2] not in previous_boards):
        return board_cache[key]

    if blank is None:
        blank = find_blank(board)

    best_board = board
    best_move_coords = None
    best_score = 100
    for y in xrange(blank[1] - 1, blank[1] + 2):
        if y < 0 or y > 2: continue
        for x in (xrange(blank[0] - 1, blank[0] + 2) if
                  y == blank[1] else [blank[0]]):
            if x < 0 or x > 2: continue
            if last_move == (x, y) or board[y][x] == -1: continue
            # Ignore completed rows
            if y == 0 and board[0] == (1, 2, 3): continue
            if x == 0 and (board[0][0], board[1][0], board[2][0]) == (1, 4, 7):
                continue

            new_board = simulate_move(board, (x, y), blank)
            board_score = completion(new_board)
            if board_score == 0:
                return 0, (x, y), new_board
            if new_board in previous_boards: continue

            if depth_limit == 0:
                new_score = board_score
            else:
                previous_boards.append(new_board)
                new_score, last_move, move_board = best_move(
                        new_board,
                        previous_boards=previous_boards,
                        last_move=blank,
                        blank=(x, y),
                        depth_limit=depth_limit - 1)
                previous_boards.pop()
            if new_score == 0:
                return new_score, (x, y), new_board
            if new_score < best_score:
                best_score, best_board = new_score, new_board
                best_move_coords = x, y

    board_cache[key] = best_score, best_move_coords, best_board
    return best_score, best_move_coords, best_board

def solve(board):
    "Solves a tile game problem"

    score = completion(board)
    print_board(board)
    last_move = None
    counter = 0
    board = tuple(tuple(r) for r in board)
    previous_boards = [board]

    print "Initial score:", score

    while score > 0:
        blank = find_blank(board)
        new_last_move = blank

        move_score, last_move, board = best_move(
            board, last_move=last_move, previous_boards=previous_boards)
        last_move = blank
        score = completion(board)
        print_board(board)
        previous_boards.append(board)
        print "Move score: %d" % move_score
        print "Board score: %d" % score

        counter += 1

    print "Solved in %d moves" % counter


def print_board(board):
    "Prints a tile board"

    p = lambda b: b if b > 0 else "#"
    for line in board:
        print p(line[0]), p(line[1]), p(line[2])
    print "-" * 5

solve([
    [2, 6, 7],
    [8, -1, 1],
    [5, 4, 3]
])