Python 8-Puzzle and solver

Question

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()

Answer 1

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 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 <= 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__(self, last, prev_holes=None):
 self.last = last
 self.prev_holes = prev_holes or []
 def branch(self, destination):
 """
 Makes a MoveSequence with the same history followed by a move of
 the hole to the specified destination index.
 """
 return MoveSequence(self.last.move(destination),
 self.prev_holes + [self.last.hole])
 def __iter__(self):
 """
 Generator of puzzle states, starting with the initial configuration
 """
 states = [self.last]
 for hole in reversed(self.prev_holes):
 states.append(states[-1].move(hole))
 yield from reversed(states)
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 MoveSequence of the solution,
 if it exists 
 """
 queue = deque([MoveSequence(self.start)])
 seen = set([self.start])
 if self.start.solved:
 return queue.pop()
 for seq in iter(queue.pop, None):
 for destination in seq.last.possible_moves:
 attempt = seq.branch(destination)
 if attempt.last not in seen:
 seen.add(attempt.last)
 queue.appendleft(attempt)
 if attempt.last.solved:
 return attempt
# https://docs.python.org/3/library/itertools.html#itertools-recipes
def pairwise(iterable):
 "s -> (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)

• rookie: you write that "For a 3 × 3 puzzle, if it reaches 20 steps, that's an extra 40000 guesses that you would check unnecessarily." Can you explain how you got this number?
• 200_success: By simulation. That explains the print() statement that I accidentally inserted while writing Rev 1 of this review and removed in Rev 2. Running the program, piped to uniq -c to count consecutive lines, you'll see that if it reaches 21 steps, then there will have been about 40000 guesses for 20-step solutions.

Answer 2

Your imports are ordered in reverse. Typically one would have them alphabetical.

It seems to me that Node should abandon state and instead Puzzle, which seems logically immutable, should get a __hash__. This way you can use child.puzzle as a more logical alternative to child.state. This does, however, require both a __hash__ and an __eq__ method on Puzzle.

Node.path can just return reversed(p); using yield from is overkill.

Node can be a namedtuple; I encourage this because it gives free immutability and is pretty convenient to use.

I would do an explicit check

while node is not None:

over the implicit one; logically you are checking for a sentinel and that's the canonical way to express it. Using while node would imply that you expect a Node could be falsy.

solved doesn't need to be a property; just set it during initialization. Personally, though, writing node.puzzle.solved the one time you use it seems more natural. The same goes for actions; you aren't buying much per unit of work.

path is a property but entails a nontrivial amount of work. It's rarely a good idea to hide work like that under attribute access; I suggest making it a fully-fledged method. For some reason it also feels to me that it should be a standalone function. I'm not sure why.

This gives

class Node(namedtuple("NodeFields", ["puzzle", "parent", "action"])):
 """
 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
 """
 __slots__ = ()
 def __new__(cls, puzzle, parent=None, action=None):
 return super().__new__(cls, puzzle, parent, action)
def path(node):
 """
 Reconstruct a path from to the root 'parent'
 """
 seen = []
 while node is not None:
 seen.append(node)
 node = node.parent
 return reversed(seen)

Solver definitely shouldn't be a class. It has no meaninful state and it has only a single method. Just make it a function:

def solve(start):
 """
 Perform breadth first search and return a path
 to the solution, if it exists 
 """

You have (with my prior changes)

seen = set()
seen.add(queue[0].state)

This could just be

seen = {queue[0].state}

The delayed action from actions doesn't give a noticeable speed improvement and adds code complexity. For that reason, I suggest you remove create_move and just use self._move. As before, make actions a full method, not a property, since it's not a trivial computation.

actions spends a lot of effort finding the 0 before actually giving results. This would be a lot faster if Puzzle tracked the 0. You can also use chained comparisons to make the check neater.

solved is a very hefty check for something called so often. It shouldn't be a property but, more importantly, it should short-circuit. A quick idea is just

return all(map(eq, self, range(1, self.width**2)))

copy can be simplified to

board = [row[:] for row in self.board]
return Puzzle(board)

At this point the hash function I'm using is

hash(tuple(map(tuple, self.board)))

Since these get hashed a fair bit and the class should be immutable, it seems sensible to make board a tuple and simplify __hash__ to just self.board. copy is only called from _move, which can be merged to create

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
 """
 def repl2d(tup, i, j, val):
 inner = tup[i][:j] + (val,) + tup[i][j+1:]
 return tup[:i] + (inner,) + tup[i+1:]
 i, j = at
 r, c = to
 board = self.board
 board = repl2d(board, i, j, self.board[r][c])
 board = repl2d(board, r, c, self.board[i][j])
 return Puzzle(board)

In theory this has speed benefits for larger grids since you don't need to copy the whole grid each time. It loses this benefit on 3x3s, though, where it actually does more work in the worst case.

These changes make it reasonable for Puzzle to also be a namedtuple since it's actually immutable. This gives us __hash__ and __eq__ for free.

__iter__ can be just

return itertools.chain.from_iterable(self.board)

I've mentioned a lot of times about thing that shouldn't be properties; I actually think it makes sense for width to be a property.

actions doesn't need to yield names for the move (eg 'D', 'R') since these can be reconstructed after the whole sequence is made. action would then become a property on Node. Doing so actually doubles speed for me since there is less packing and unpacking to do.

Since much of the time is spent in move, it would make sense to flatten the grid so that move can be simpler, even at the cost of potentially complicating other sections. This gives another 2x improvement to speed.

In solve, you can now push a little more into the if by directly hashing board instead of the Node.

Since I've been talking about speed, my solution is between 2 and 10 times as fast as 200_success' and some similar significant amount faster than the original. It's really hard to time due to random factors such as hash randomization so take these times with a grain of salt.

Oh, also I'll steal 200_success' idea to check for solved solutions before they are added to the queue.

A final style point: solve can return None since impossible puzzles do exist. This should be documented in the docstring to tell people to check for it.

Here's the code:

import random
from collections import deque, namedtuple
from operator import eq
class Puzzle(namedtuple("PuzzleFields", ["board", "width", "zero_at"])):
 """
 A class representing an '8-puzzle'.
 - 'board' should be a square list of lists with integer entries 0...width2-1
 e.g. [[1,2,3],[4,0,6],[7,5,8]]
 """
 __slots__ = ()
 def __new__(cls, board, width, zero_at=None):
 if zero_at is None:
 zero_at = board.index(0)
 return super().__new__(cls, board, width, zero_at)
 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
 """
 # 0 is on board, so must be in last place
 return all(map(eq, self.board, range(1, self.width**2)))
 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'.
 """
 at = self.zero_at
 if at >= self.width:
 yield self._move(at - self.width)
 if at + self.width < len(self.board):
 yield self._move(at + self.width)
 if at % self.width:
 yield self._move(at - 1)
 if (at + 1) % self.width:
 yield self._move(at + 1)
 def shuffle(self):
 """
 Return a new puzzle that has been shuffled with 1000 random moves
 """
 puzzle = self
 for _ in range(1000):
 puzzle = random.choice(list(puzzle.actions()))
 return puzzle
 def _move(self, to):
 """
 Return a new puzzle where 'zero_at' and 'to' tiles have been swapped.
 NOTE: all moves should be 'actions' that have been executed
 """
 a, b = min(self.zero_at, to), max(self.zero_at, to)
 board = list(self.board)
 board[a], board[b] = board[b], board[a]
 return Puzzle(tuple(board), self.width, to)
 def pprint(self):
 for i in range(0, len(self.board), self.width):
 print(self.board[i:i+self.width])
class Node(namedtuple("NodeFields", ["puzzle", "parent"])):
 """
 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
 """
 __slots__ = ()
 def __new__(cls, puzzle, parent=None):
 return super().__new__(cls, puzzle, parent)
 @property
 def action(self):
 if self.parent is None:
 return None
 diff_to_action = {
 +self.puzzle.width: 'D',
 -self.puzzle.width: 'U',
 +1: 'R',
 -1: 'L',
 }
 return diff_to_action[self.puzzle.zero_at - self.parent.puzzle.zero_at]
def path(node):
 """
 Reconstruct a path from to the root 'parent'
 """
 seen = []
 while node is not None:
 seen.append(node)
 node = node.parent
 return reversed(seen)
def solve(start):
 """
 Perform breadth first search and return a path
 to the solution, if it exists (otherwise None).
 """
 queue = deque([Node(start)])
 seen = {start}
 if start.solved():
 return path(Node(start, None))
 while queue:
 node = queue.pop()
 for move in node.puzzle.actions():
 if move.board not in seen:
 if move.solved():
 return path(Node(move, node))
 queue.appendleft(Node(move, node))
 seen.add(move.board)
def main():
 board = 1,2,3, 4,0,6, 7,5,8
 puzzle = Puzzle(board, 3)
 puzzle = puzzle.shuffle()
 p = solve(puzzle)
 for node in p:
 print(node.action)
 node.puzzle.pprint()
 print()
if __name__ == "__main__":
 main()

• 200_success: Much of the performance of this solution, relative to mine, is due to the use of tuples and namedtuples instead of objects and lists. Another benefit is that tuples, unlike lists, are hashable, so there is no need to override Puzzle.__eq__ and Puzzle.__hash__ as I did.

Answer 3

Looks very good overall. A few things that caught my eye:

• Using ''.join(map(str, self)) as the string representation will be ambiguous with larger puzzles. Use a separator character.
• Why must the puzzle be square? You could work with any rectangular puzzle with minimal extra effort.
• Puzzle.actions would be more efficient if it first located the empty position and only there explored the four directions. An additional optimization would be to keep track of the empty position after every move.
• Python has chained comparison: if 0 <= r < self.width and 0 <= c < self.width

• Puzzle.copy could be written more concisely:

  def copy(self):
   board = [row[:] for row in self.board]
   return Puzzle(board)
  

• In Node.path, yield from reversed(p) could be replaced by return reversed(p) because reversed returns an iterator. However, since a list has already been built, returning an iterator does not save any memory. You might as well reverse and return the list directly.

Answer 4

Your code is clean and readable. To be honest I always avoid using functions in functions, I find them confusing, but I read the following:

However, as a rule of thumb, if the function is complex (more than 10 lines) it might be a better idea to declare it on the module level.

which doesn't seem to be the case. (source)

I can only suggest to use a main function, which makes it possible to reuse your code as a module for other projects (thinking ahead), such as this.

• rookie: Thanks @DJanssens. That's good thinking -- I would like to make a GUI for this.
• DJanssens: @rookie perhaps take a look at wiki.python.org/moin/TkInter for that, in case you didn't know.
• rookie: Yes, for sure. I will probably be back to CR with some questions on the MVC pattern in the near future :)
• DJanssens: I'm not a big fan of nesting classes/functions myself. But it's perfectly possible, since they are very related. It however limits the reuse of the node class. I never really found a clear guideline on this myself either.
• Janne Karila: @rookie A nested function can access local variables of the outer function, but a nested class does not enjoy a similar benefit. Nesting hurts readability.