Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for 8 Puzzle by Anne29
# So, brute force was too brutish. Let's do bfs.
from collections import deque
# Okay, let's express the compass directions as tuples: (delta x, delta y)
movement = { "U": (-1, 0), "D": (1, 0), "R": (0, 1), "L": (0, -1)}
# We're going to apply moves toa board a lot. Let's encapsulate that idea.
# This code assumes the space is in location (row, col). If it's not, you're
# on your own. Good luck.
def make_move(board, row, col, direction):
new_row = row + movement[direction][0]
new_col = col + movement[direction][1]
if new_row >= 0 and new_row < len(board) and new_col >= 0 and new_col < len(board[0]):
# Make the move:
board[row][col] = board[new_row][new_col]
board [new_row][new_col] = 0
# We're going to see if we can move a lot too.
# This code assumes the space is in location (row, col). If it's not, you're
# on your own. Good luck.
def can_move(board, row, col, direction):
new_row = row + movement[direction][0]
new_col = col + movement[direction][1]
return (new_row >= 0 and new_row < len(board) and new_col >= 0 and new_col < len(board[0]))
def finished(puzzle):
num = 1
for row in puzzle:
for val in row:
if val != num:
return False
num += 1
if num == 9:
return True
def find_blank(puzzle):
for r in range(len(puzzle)):
for c in range(len(puzzle[0])):
if puzzle[r][c] == 0:
return (r, c)
def flatten(puzzle):
result = ""
for row in puzzle:
for piece in row:
result += str(piece)
return result
def rebuild_puzzle(moves):
# Make a deep copy
new_puzzle = []
for row in original:
new_row = []
for piece in row:
new_row.append(piece)
new_puzzle.append(new_row)
#print ('Clone = ', flatten(new_puzzle))
for move in moves:
(row, col) = find_blank(new_puzzle)
make_move(new_puzzle, row, col, move)
return new_puzzle
# Breadth first search seems like the thing to do.
def bfs(puzzle):
# Let's create a queue of moves and paths to that position.
# Originally, we just have the start position
states = deque()
states.append("")
# So, what will we store in the queue? Interesting question,
# since "copies" of arrays are shallow copies. So, let's
# just keep the list of moves to this point and rebuild the board
# to work with it.
visited = {}
# This will have a flattened form of the boards encountered.
# We don't use the moves list since you can get to the same
# board many different ways.
global original
original = puzzle
while len(states) > 0: # boy, I hope there's a solution!
current_moves = states.popleft()
current_board = rebuild_puzzle(current_moves)
flat = flatten(current_board)
# Have I visited this before?
if flat in visited:
continue
#print(flat)
visited[flat] = True
if finished(current_board):
# Yay! Found it!
return current_moves
# Which directions might the space move?
possible_dir = ["U", "D", "L", "R"]
for next_dir in possible_dir:
(row, col) = find_blank(current_board)
if can_move (current_board, row, col, next_dir):
next_board = rebuild_puzzle(current_moves + next_dir)
if flatten(next_board) not in visited:
states.append( current_moves + next_dir)
def checkio(puzzle):
"""
Solve the puzzle
U - up
D - down
L - left
R - right
"""
return bfs(puzzle)
if __name__ == '__main__':
print(checkio([[1, 2, 3],
[4, 6, 8],
[7, 5, 0]]))
Nov. 8, 2013