I wrote a simple 8-Puzzle and solver and am interested in seeing how it might be improved. Please let me know if any style or design changes might enhance the readability/performance of my code.
import random
import itertools
import collections
class Node:
"""
A class representing an Solver node
- 'puzzle' is a Puzzle instance
- 'parent' is the preceding node generated by the solver, if any
- 'action' is the action taken to produce puzzle, if any
"""
def __init__(self, puzzle, parent=None, action=None):
self.puzzle = puzzle
self.parent = parent
self.action = action
@property
def state(self):
"""
Return a hashable representation of self
"""
return str(self)
@property
def path(self):
"""
Reconstruct a path from to the root 'parent'
"""
node, p = self, []
while node:
p.append(node)
node = node.parent
yield from reversed(p)
@property
def solved(self):
""" Wrapper to check if 'puzzle' is solved """
return self.puzzle.solved
@property
def actions(self):
""" Wrapper for 'actions' accessible at current state """
return self.puzzle.actions
def __str__(self):
return str(self.puzzle)
class Solver:
"""
An '8-puzzle' solver
- 'start' is a Puzzle instance
"""
def __init__(self, start):
self.start = start
def solve(self):
"""
Perform breadth first search and return a path
to the solution, if it exists
"""
queue = collections.deque([Node(self.start)])
seen = set()
seen.add(queue[0].state)
while queue:
node = queue.pop()
if node.solved:
return node.path
for move, action in node.actions:
child = Node(move(), node, action)
if child.state not in seen:
queue.appendleft(child)
seen.add(child.state)
class Puzzle:
"""
A class representing an '8-puzzle'.
- 'board' should be a square list of lists with integer entries 0...width^2 - 1
e.g. [[1,2,3],[4,0,6],[7,5,8]]
"""
def __init__(self, board):
self.width = len(board[0])
self.board = board
@property
def solved(self):
"""
The puzzle is solved if the flattened board's numbers are in
increasing order from left to right and the '0' tile is in the
last position on the board
"""
N = self.width * self.width
return str(self) == ''.join(map(str, range(1,N))) + '0'
@property
def actions(self):
"""
Return a list of 'move', 'action' pairs. 'move' can be called
to return a new puzzle that results in sliding the '0' tile in
the direction of 'action'.
"""
def create_move(at, to):
return lambda: self._move(at, to)
moves = []
for i, j in itertools.product(range(self.width),
range(self.width)):
direcs = {'R':(i, j-1),
'L':(i, j+1),
'D':(i-1, j),
'U':(i+1, j)}
for action, (r, c) in direcs.items():
if r >= 0 and c >= 0 and r < self.width and c < self.width and \
self.board[r][c] == 0:
move = create_move((i,j), (r,c)), action
moves.append(move)
return moves
def shuffle(self):
"""
Return a new puzzle that has been shuffled with 1000 random moves
"""
puzzle = self
for _ in range(1000):
puzzle = random.choice(puzzle.actions)[0]()
return puzzle
def copy(self):
"""
Return a new puzzle with the same board as 'self'
"""
board = []
for row in self.board:
board.append([x for x in row])
return Puzzle(board)
def _move(self, at, to):
"""
Return a new puzzle where 'at' and 'to' tiles have been swapped.
NOTE: all moves should be 'actions' that have been executed
"""
copy = self.copy()
i, j = at
r, c = to
copy.board[i][j], copy.board[r][c] = copy.board[r][c], copy.board[i][j]
return copy
def pprint(self):
for row in self.board:
print(row)
print()
def __str__(self):
return ''.join(map(str, self))
def __iter__(self):
for row in self.board:
yield from row
# example of use
board = [[1,2,3],[4,0,6],[7,5,8]]
puzzle = Puzzle(board)
puzzle = puzzle.shuffle()
s = Solver(puzzle)
p = s.solve()
for node in p:
print(node.action)
node.puzzle.pprint()
