import random, time

random.seed(42)  # Select which puzzle to solve.
SIZE = 4  # Set this to either 3 or 4.
BLANK = '  '  # The string that represents the blank space:

# Constants for directions:
UP = 'up'
DOWN = 'down'
LEFT = 'left'
RIGHT = 'right'


def displayBoard(board):
    """Display `board` on the screen."""
    for y in range(SIZE):
        for x in range(SIZE):
            print(board[x][y] + ' ', end='')
        print()  # Print a newline at the end of the row.


def getNewBoard():
    """Return a list of lists that represents a new tile puzzle."""
    # NOTE: All the single digit numbers have a space in front of them.
    if SIZE == 3:
        return [[' 1', ' 4', ' 7'], [' 2', ' 5', ' 8'],
                [' 3', ' 6', BLANK]]
    elif SIZE == 4:
        return [[' 1', ' 5', ' 9', '13'], [' 2', ' 6', '10', '14'],
                [' 3', ' 7', '11', '15'], [' 4', ' 8', '12', BLANK]]


def findBlankSpace(board):
    """Return an (x, y) tuple of the blank space's location."""
    for x in range(SIZE):
        for y in range(SIZE):
            if board[x][y] == BLANK:
                return (x, y)


def makeMove(b, move):
    """Carry out the given move on the given board in `b`."""
    bx, by = findBlankSpace(b)

    if move == UP:
        b[bx][by], b[bx][by+1] = b[bx][by+1], b[bx][by]
    elif move == LEFT:
        b[bx][by], b[bx+1][by] = b[bx+1][by], b[bx][by]
    elif move == DOWN:
        b[bx][by], b[bx][by-1] = b[bx][by-1], b[bx][by]
    elif move == RIGHT:
        b[bx][by], b[bx-1][by] = b[bx-1][by], b[bx][by]


def undoMove(board, move):
    """Do the opposite move of `move` to undo it on `board`."""
    if move == UP:
        makeMove(board, DOWN)
    elif move == DOWN:
        makeMove(board, UP)
    elif move == LEFT:
        makeMove(board, RIGHT)
    elif move == RIGHT:
        makeMove(board, LEFT)


def getValidMoves(board):
    """Returns a list of the valid moves to make on this board."""
    blankx, blanky = findBlankSpace(board)

    validMoves = []
    if blanky != SIZE - 1:  # Blank space is not on the bottom row.
        validMoves.append(UP)
    if blankx != SIZE - 1:  # Blank space is not on the right column.
        validMoves.append(LEFT)
    if blanky != 0:  # Blank space is not on the top row.
        validMoves.append(DOWN)
    if blankx != 0:  # Blank space is not on the left column.
        validMoves.append(RIGHT)
    return validMoves


def makeRandomMove(board):
    """Perform a slide in a random direction."""
    makeMove(board, random.choice(getValidMoves(board)))


def getNewPuzzle():
    """Get a new puzzle by making random slides from a solved state."""
    board = getNewBoard()
    for i in range(200):
        makeRandomMove(board)
    return board


def solve(board, maxMoves):
    """Attempt to solve the puzzle in `board` in at most `maxMoves`
    moves. Returns True if solved, otherwise False."""
    print('Attempting to solve in at most', maxMoves, 'moves...')
    solutionMoves = []  # A list of UP, DOWN, LEFT, RIGHT values.
    solved = attemptMove(board, solutionMoves, maxMoves)
    if solved:
        displayBoard(board)
        for move in solutionMoves:
            print('Move', move)
            makeMove(board, move)
            print()  # Print a newline.
            displayBoard(board)
            print()  # Print a newline.

        print('Solved in', len(solutionMoves), 'moves:')
        print(', '.join(solutionMoves))
        return True  # Puzzle was solved.
    else:
        return False  # Unable to solve in maxMoves moves.


def attemptMove(board, movesMade, maxMoves, iteration=1, lastMove=None):
    """A recursive function that attempts all possible moves on `board`
    until a solution is found or we've reached the `maxMoves` limit.
    Returns True if a solution was found, in which case, movesMade
    contains the series of moves to solve the puzzle. Returns False
    if no solution was found in `maxMoves` moves."""
    if iteration > maxMoves:
        return False  # BASE CASE

    # Get the valid moves, but don't consider a move that would undo
    # the last move made on this board:
    validMoves = getValidMoves(board)
    if lastMove == UP and DOWN in validMoves:
        validMoves.remove(DOWN)
    if lastMove == DOWN and UP in validMoves:
        validMoves.remove(UP)
    if lastMove == LEFT and RIGHT in validMoves:
        validMoves.remove(RIGHT)
    if lastMove == RIGHT and LEFT in validMoves:
        validMoves.remove(LEFT)

    # Attempt each of the valid moves:
    for move in validMoves:
        # Make the move:
        makeMove(board, move)
        movesMade.append(move)

        if board == getNewBoard():
            # BASE CASE - Solved the puzzle:
            undoMove(board, move)
            return True
        else:
            # RECURSIVE CASE - Attempt another move:
            if attemptMove(board, movesMade, maxMoves, iteration + 1, move):
                # If the puzzle is solved, return True:
                undoMove(board, move)
                return True

        # Undo this last move to set up for the next move:
        undoMove(board, move)
        movesMade.pop()  # Remove the last move since it was undone.
    return False  # BASE CASE - Unable to find a solution.


# Start the program:
gameBoard = getNewPuzzle()
displayBoard(gameBoard)
input('Press Enter to solve...')
startTime = time.time()

maxMoves = 1
while True:
    if solve(gameBoard, maxMoves):
        break  # Break out of the loop when a solution is found.
    maxMoves += 1
print('Run in', round(time.time() - startTime, 1), 'seconds.')