Skip to content

Instantly share code, notes, and snippets.

@mattbasta
Last active September 25, 2015 13:38
Show Gist options
  • Save mattbasta/930446 to your computer and use it in GitHub Desktop.
Save mattbasta/930446 to your computer and use it in GitHub Desktop.
A python version of the tile game solver
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]
])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment