patternpythonMinor
Python 8-Puzzle and solver
Viewed 0 times
andsolverpuzzlepython
Problem
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:
```
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:
Solution
Even though this is a brute-force enumeration algorithm, we can still make a few optimizations.
Termination
You check whether each puzzle is solved when you remove it from the queue. It would be more efficient to check when enqueuing it. The difference is that you won't realize that you've already solved the puzzle until after trying all of the other guesses for paths of the same length. For a 3 × 3 puzzle, if it reaches 20 steps, that's an extra 40000 guesses that you would check unnecessarily.
Representation
Storing the board as a flattened array would make it more convenient to copy and to search. (You eventually flatten every one of your puzzle states anyway when calling
In
With a linear representation, you can uniquely identify a move as the \$\Delta \mathrm{index}\$ of the hole (±1 for horizontal, and ±width for vertical movements).
But it gets even better. You can reconstruct the entire history of a puzzle state if you know the most recent state and the indexes of the holes of all the past states. That, I think, is preferable to keeping a linked list of 3 × 3 snapshots of every previous attempt, as you do in your
Stringification
For the algorithm to work, you need to keep a
A more proper solution would be to make
Classes
The code would be easier to understand if you presented the classes in reverse order:
Rather than defining
Instead of hard-coding 1000 moves for
Suggested implementation
Termination
You check whether each puzzle is solved when you remove it from the queue. It would be more efficient to check when enqueuing it. The difference is that you won't realize that you've already solved the puzzle until after trying all of the other guesses for paths of the same length. For a 3 × 3 puzzle, if it reaches 20 steps, that's an extra 40000 guesses that you would check unnecessarily.
Representation
Storing the board as a flattened array would make it more convenient to copy and to search. (You eventually flatten every one of your puzzle states anyway when calling
Puzzle.solved().) Another advantage is that the location of any tile (or hole) can be represented as a single integer rather than as a pair of numbers — this is important, as we shall see.In
Puzzle.actions(), you generate the list of all possible moves. To do so, you must find up to four neighbours of the hole. You accomplish that by searching all width * width locations for the hole. If it were a linear list, we could just call .index(0) instead of doing a two-dimensional search. Better yet, just cache the location of the hole.With a linear representation, you can uniquely identify a move as the \$\Delta \mathrm{index}\$ of the hole (±1 for horizontal, and ±width for vertical movements).
But it gets even better. You can reconstruct the entire history of a puzzle state if you know the most recent state and the indexes of the holes of all the past states. That, I think, is preferable to keeping a linked list of 3 × 3 snapshots of every previous attempt, as you do in your
Node class.Stringification
For the algorithm to work, you need to keep a
set of all previously seen board states. Items to be placed in a set must be hashable, and to meet that requirement, you store Node.state, which returns a stringified representation of the data. I find that unclean. The __str__() function would be more appropriate for producing a human-friendly display, but curiously, you defined a specialized Puzzle.pprint() method for that.A more proper solution would be to make
Puzzle hashable by defining its __hash__() and __eq__() methods.Classes
Node is too generic of a name. I suggest MoveSequence.The code would be easier to understand if you presented the classes in reverse order:
Puzzle, then MoveSequence, then Solver.Rather than defining
Puzzle.copy() and Puzzle._move(), I would make Puzzle immutable, such that Puzzle.move() always returns a new Puzzle.Instead of hard-coding 1000 moves for
Puzzle.shuffle(), it should take a moves parameter that defaults to 1000.Suggested implementation
from collections import deque
from itertools import chain, tee
from math import sqrt
from random import choice
class Puzzle:
HOLE = 0
"""
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, hole_location=None, width=None):
# Use a flattened representation of the board (if it isn't already)
self.board = list(chain.from_iterable(board)) if hasattr(board[0], '__iter__') else board
self.hole = hole_location if hole_location is not None else self.board.index(Puzzle.HOLE)
self.width = width or int(sqrt(len(self.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
"""
return self.board == list(range(1, self.width * self.width)) + [Puzzle.HOLE]
@property
def possible_moves(self):
"""
A generator for the possible moves for the hole, where the
board is linearized in row-major order. Possibilities are
-1 (left), +1 (right), -width (up), or +width (down).
"""
# Up, down
for dest in (self.hole - self.width, self.hole + self.width):
if 0 (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
if __name__ == '__main__':
board = [[1,2,3],
[4,0,6],
[7,5,8]]
puzzle = Puzzle(board).shuffle()
print(puzzle)
move_seq = iter(Solver(puzzle).solve())
for from_state, to_state in pairwise(move_seq):
print()
print(Puzzle.direction(from_state, to_state))
print(to_state)Code Snippets
from collections import deque
from itertools import chain, tee
from math import sqrt
from random import choice
class Puzzle:
HOLE = 0
"""
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, hole_location=None, width=None):
# Use a flattened representation of the board (if it isn't already)
self.board = list(chain.from_iterable(board)) if hasattr(board[0], '__iter__') else board
self.hole = hole_location if hole_location is not None else self.board.index(Puzzle.HOLE)
self.width = width or int(sqrt(len(self.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
"""
return self.board == list(range(1, self.width * self.width)) + [Puzzle.HOLE]
@property
def possible_moves(self):
"""
A generator for the possible moves for the hole, where the
board is linearized in row-major order. Possibilities are
-1 (left), +1 (right), -width (up), or +width (down).
"""
# Up, down
for dest in (self.hole - self.width, self.hole + self.width):
if 0 <= dest < len(self.board):
yield dest
# Left, right
for dest in (self.hole - 1, self.hole + 1):
if dest // self.width == self.hole // self.width:
yield dest
def move(self, destination):
"""
Move the hole to the specified index.
"""
board = self.board[:]
board[self.hole], board[destination] = board[destination], board[self.hole]
return Puzzle(board, destination, self.width)
def shuffle(self, moves=1000):
"""
Return a new puzzle that has been shuffled with random moves
"""
p = self
for _ in range(moves):
p = p.move(choice(list(p.possible_moves)))
return p
@staticmethod
def direction(a, b):
"""
The direction of the movement of the hole (L, R, U, or D) from a to b.
"""
if a is None:
return None
return {
-a.width: 'U',
-1: 'L', 0: None, +1: 'R',
+a.width: 'D',
}[b.hole - a.hole]
def __str__(self):
return "\n".join(str(self.board[start : start + self.width])
for start in range(0, len(self.board), self.width))
def __eq__(self, other):
return self.board == other.board
def __hash__(self):
h = 0
for value, i in enumerate(self.board):
h ^= value << i
return h
class MoveSequence:
"""
Represents the successive states of a puzzle taken to reach an end state.
"""
def __init__(sContext
StackExchange Code Review Q#76906, answer score: 5
Revisions (0)
No revisions yet.