'''
This is a program that solves a tile puzzle (https://en.wikipedia.org/wiki/Sliding_puzzle).
It was used to solve a puzzle in a point and click game (http://akarika.net/games/escape/loom_blend.htm).
'''
import queue
#draw the 3x3 grid with the starting configuration of the tiles
#space is used to mean empty tile
start = '''
┘│<
┐─┐
└┌
'''
#draw the 3x3 grid with the goal configuration of the tiles
goal = '''
┌─┐
└┐│
<┘
'''
#throwable object containing moves history to reach goal
class ReachedGoal(Exception):
def __init__(self, history):
super().__init__()
self.history = history
#perform breath first search on tree of moves and stop as soon as a goal configuration is reached
#this will give the shortest path from start configuration (the root of the tree) to the goal configuration
encoded_goal = ''.join(ele for row in goal.strip('\n').split('\n') for ele in row)
grid = [ list(row) for row in start.strip('\n').split('\n') ]
encoded_grid = ''.join(ele for row in grid for ele in row)
visited = { encoded_grid }
q = queue.Queue()
q.put((grid, [])) #(current grid, moves history)
try:
while not q.empty():
(grid, history) = q.get()
for y in range(3):
for x in range(3):
if grid[y][x] == ' ':
#try moving all possible tiles adjacent to the empty tile
for (dy, dx) in [(0,1), (0,-1), (1,0), (-1,0)]:
if not (0 <= y+dy < 3 and 0 <= x+dx < 3):
continue
new_history = history + [ (y+dy, x+dx) ]
new_grid = [ list(row) for row in grid ] #copy current tile configuration
(new_grid[y][x], new_grid[y+dy][x+dx]) = (new_grid[y+dy][x+dx], new_grid[y][x])
encoded_new_grid = ''.join(ele for row in new_grid for ele in row)
if encoded_new_grid in visited:
continue
#goal has been reached
if encoded_new_grid == encoded_goal:
raise ReachedGoal(new_history)
visited.add(encoded_new_grid)
q.put((new_grid, new_history))
break
except ReachedGoal as e:
#display history of moves performed in order to reach goal configuration
grid = [ [ ' ' for _ in range(3) ] for _ in range(3) ]
for (step, (h_y, h_x)) in enumerate(e.history):
grid[h_y][h_x] = 'X'
print('Step', step+1)
for row in grid:
print('|'+''.join(row)+'|')
print()
grid[h_y][h_x] = ' '