Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for 8 Puzzle by PositronicLlama
"""
Solve a sliding block puzzle in the shortest number of moves.
Use breadth-first search and avoid revisiting duplicate positions.
"""
import itertools
import operator
# A list of possible moves and the coordinate change of the empty space
# after taking this move.
DIRECTIONS = [
('U', (0, -1)),
('D', (0, 1)),
('L', (-1, 0)),
('R', (1, 0)),
]
def make_tuple(puzzle):
"""Return a copy of puzzle with lists replaced by tuples."""
return tuple(map(tuple, puzzle))
def find_empty_space(puzzle):
"""
Return the (x, y) coordinates of the empty space (the zero) in this puzzle.
"""
h, w = len(puzzle), len(puzzle[0])
for x, y in itertools.product(range(w), range(h)):
if puzzle[y][x] == 0:
return (x, y)
raise ArgumentError("Puzzle {} has no empty space.".format(puzzle))
def vector_add(a, b):
"""Return the sum of two vectors as a tuple."""
return tuple(map(operator.add, a, b))
def swap_cells(puzzle, a, b):
"""
Return a copy of puzzle with the cells at coordinates a and b swapped.
"""
ax, ay = a
bx, by = b
# There is a more efficient approach that reduces the number of allocations
# in this process, and preserves unchanged tuples, but it is substantially
# more complex.
puzzle = list(map(list, puzzle))
puzzle[ay][ax], puzzle[by][bx] = puzzle[by][bx], puzzle[ay][ax]
return make_tuple(puzzle)
def checkio(puzzle):
"""
Return a sequence of moves as a string that solves the given sliding block puzzle.
The puzzle is a list of lists of pieces (zero represents the empty space).
Possible moves (which indicate the direction to move the empty space:
U - up
D - down
L - left
R - right
"""
h, w = len(puzzle), len(puzzle[0])
# Construct a goal state of the form: ((1, 2, 3), (4, 5, 6), (7, 8, 0))
goal = tuple(zip(*[iter(itertools.chain(range(1, h * w), range(1)))] * w))
initial = make_tuple(puzzle)
if goal == initial:
return ''
visited = set()
# The open list contains tuples of all pending states,
# the (x, y) coordinates of the empty space in the state, and the sequence
# of moves to get to this state.
open = [(initial, find_empty_space(initial), '')]
while open:
# Get the current state and see whether we are done
state, space, moves = open.pop(0)
if state in visited:
continue
visited.add(state)
# Consider all moves, but ignore invalid ones or ones we've seen.
for d, delta in DIRECTIONS:
x, y = new_space = vector_add(space, delta)
if x < 0 or x >= w or y < 0 or y >= h:
continue
new_state = swap_cells(state, space, new_space)
if new_state in visited:
continue
new_moves = moves + d
if new_state == goal:
return new_moves
open.append((new_state, new_space, new_moves))
# No solution
return ''
April 13, 2013
