import random, time
#random.seed(42) # Select which puzzle to solve.
SIZE = 4 # Set this to either 3 or 4.
BLANK = 0
# Constants for directions:
UP = 'up'
DOWN = 'down'
LEFT = 'left'
RIGHT = 'right'
def displayBoard(board):
"""Display `board` on the screen."""
for y in range(SIZE): # Iterate over each row.
for x in range(SIZE): # Iterate over each column.
if board[y * SIZE + x] == BLANK:
print('__ ', end='')
else:
print(str(board[y * SIZE + x]).rjust(2) + ' ', 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.
return list(range(1, SIZE * SIZE)) + [BLANK]
def findBlankSpace(board):
"""Return an [x, y] list of the blank space's location."""
for x in range(SIZE):
for y in range(SIZE):
if board[y * SIZE + x] == BLANK:
return [x, y]
def makeMove(board, move):
"""Carry out the given move on the given board in `board`."""
bx, by = findBlankSpace(board)
blankIndex = by * SIZE + bx
if move == UP:
tileIndex = (by + 1) * SIZE + bx
elif move == LEFT:
tileIndex = by * SIZE + (bx + 1)
elif move == DOWN:
tileIndex = (by - 1) * SIZE + bx
elif move == RIGHT:
tileIndex = by * SIZE + (bx - 1)
board[blankIndex], board[tileIndex] = board[tileIndex], board[blankIndex]
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 getNewPuzzle():
"""Get a new puzzle by making random slides from a solved state."""
board = getNewBoard()
for i in range(50):
validMoves = getValidMoves(board)
makeMove(board, random.choice(validMoves))
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.
cache = set()
hitsMisses = {'hits': 0, 'misses': 0}
st = time.time()
solved = attemptMove(board, solutionMoves, cache, hitsMisses, maxMoves, 0)
duration = round(time.time() - st, 2)
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))
#_log(maxMoves, duration, hitsMisses)
#input('debug: check memory')
return True # Puzzle was solved.
else:
#_log(maxMoves, duration, hitsMisses)
#input('debug: check memory')
return False # Unable to solve in maxMoves moves.
def _log(maxMoves, duration, hitsMisses):
with open('_log.csv', 'a') as fo:
fo.write(str(maxMoves) + '\t' + str(round(duration, 1)) + '\t' + str(hitsMisses['hits']) + '\t' + str(hitsMisses['misses']) + '\t' + str(round(hitsMisses['hits'] / (hitsMisses['hits'] + hitsMisses['misses']) * 100, 2)) + '%\n')
print(str(maxMoves) + '\t' + str(round(duration, 1)) + '\t' + str(hitsMisses['hits']) + '\t' + str(hitsMisses['misses']) + '\t' + str(round(hitsMisses['hits'] / (hitsMisses['hits'] + hitsMisses['misses']) * 100, 2)) + '%')
def attemptMove(board, movesMade, stateCache, cacheHitsMisses, maxMoves, depth):
"""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 depth > maxMoves:
return False # BASE CASE
if board == SOLVED_BOARD:
# BASE CASE - Solved the puzzle:
return True
boardAsBytes = bytes(board)
if boardAsBytes in stateCache:
cacheHitsMisses['hits'] += 1
return False
else:
cacheHitsMisses['misses'] += 1
stateCache.add(boardAsBytes)
# Attempt each of the valid moves:
for move in getValidMoves(board):
# Make the move:
makeMove(board, move)
movesMade.append(move)
# RECURSIVE CASE - Attempt another move:
if attemptMove(board, movesMade, stateCache, cacheHitsMisses, maxMoves, depth + 1):
# 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:
SOLVED_BOARD = getNewBoard()
gameBoard = getNewPuzzle()
displayBoard(gameBoard)
startTime = time.time()
maxMoves = 10
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.')