layout | title | permalink |
---|---|---|
default |
Solving puzzles |
/puzzles |
This problem is to encourage you to follow the excellent presentation by Raymond Hettinger at PyCon 2019. In particular, you should now be able to solve the following problems with the generic solver presented on this page. You will find the model for two problems.
The solver is based on the iteration protocol, in particular the __iter__
method and yield
keywords to generate neighbouring positions. The author insist in their video, but a breadth-first search (BFS) is called, which is the safest option when the shortest path solution needs to be found or when some paths have a potential to wander around infinitely (i.e. you can randomly twist a Rubik's cube all day and never come near a solution). However, you may want to switch to depth-first search (DFS) for the puzzles below, using the option solve(depthFirst=True)
.
IndexError: pop from an empty deque exception
This means you finished exploring the search without finding a solution: check your
isgoal()
function first, then that you did not miss any possible neighbour during the iteration.
class NQueens(Puzzle):
"""
- ♛ - - - - - -
- - - ♛ - - - -
- - - - - ♛ - -
- - - - - - - ♛
- - ♛ - - - - -
♛ - - - - - - -
- - - - - - ♛ -
- - - - ♛ - - -
Given n=8 queens, place them on an n × n chessboard so that no two queen
attach each other in line, column and diagonal.
"""
n = 8
pos = tuple()
def isgoal(self) -> bool:
pass # <<-- FILL HERE
def __repr__(self):
return "" # <<-- FILL HERE
def __iter__(self):
# This is wrong, but you should yield such a structure
# >> FILL HERE <<
yield NQueens(self.pos)
class Solitaire(Puzzle):
"""
·
x x
x x x
x x x x
x x x x x
Starting from the following puzzle, jump the tees like checkers,
one at a time, removing each one you jump, until only one remains.
"""
pos = (0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
def isgoal(self) -> bool:
return sum(self.pos) == 1
def __repr__(self):
return "" # <<-- FILL HERE
def __iter__(self):
# This is wrong, but you should yield such a structure
# >> FILL HERE <<
yield Solitaire(self.pos)