Created
July 7, 2022 16:14
-
-
Save outofmbufs/444f36eba58dfb59ff9958f37dcdb2c6 to your computer and use it in GitHub Desktop.
Generic breadth-first puzzle solution search. A generic framework from the knightspages.py gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# MIT License | |
# | |
# Copyright (c) 2022 Neil Webber | |
# | |
# Permission is hereby granted, free of charge, to any person obtaining a copy | |
# of this software and associated documentation files (the "Software"), to deal | |
# in the Software without restriction, including without limitation the rights | |
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
# copies of the Software, and to permit persons to whom the Software is | |
# furnished to do so, subject to the following conditions: | |
# | |
# The above copyright notice and this permission notice shall be included | |
# in all copies or substantial portions of the Software. | |
# | |
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
# SOFTWARE. | |
# Generic framework for searching puzzle solution spaces. | |
def solver(puzzle): | |
"""Search algorithm for an arbitrary puzzle object. | |
The puzzle must have the following methods: | |
p2 = puzzle.clone() -- create a new, identical-state puzzle | |
moves = puzzle.legalmoves() -- return a list of all legal 'moves' | |
See discussion below. | |
puzzle.move(m) -- execute a legal move | |
s = puzzle.canonicalstate() -- return a hashable canonical state | |
See discussion below. | |
The puzzle also must implement the following ATTRIBUTE/PROPERTY: | |
puzzle.endstate -- True if the puzzle is 'solved' | |
MOVEs: | |
The puzzle must have a legalmoves() method that returns an | |
iterable of legal moves, each an object which the solver does not | |
examine. The solver will eventually try some (or all) of the moves | |
via the move() method (each move tried on a clone() of the puzzle). | |
CANONICAL STATE: | |
This must be a hashable abstraction representing the current | |
"situation" of the puzzle, which may be more abstracted than | |
the underlying state of the individual puzzle elements. | |
Consider, For example, a tower-of-hanoi puzzle. One possible state | |
representation is just the list of disks that are on each of the three | |
pins. However, some configurations that differ in that description | |
are still the same overall situation. For example, the first move | |
could be to take the smallest disk from pin 1 and put it on pin 2 | |
or pin 3. Those are two different moves but they lead to the same | |
"puzzle situation" and, ideally, they would have the same canonical | |
state. It is not REQUIRED that the canonical state be identical in | |
such situations - but the more the canonical state filters out such | |
identical situations the more efficient the puzzle search will be. | |
The one requirement is that truly identical states have identical | |
canonical state representations even if they arrived at that state | |
by different paths. For example, tower of hanoi again, in | |
a fresh puzzle that has had two moves made: | |
1) move smallest disk from 1 to 2 | |
2) move that same disk back to 1 | |
The resulting canonical state for that puzzle must be identical | |
to the canonical state of a fresh puzzle. If this requirement is | |
not met the solver can potentially loop infinitely over such moves. | |
""" | |
# Breadth-first search. | |
# | |
# Each new proposed state is FIFO queued so that it won't be examined | |
# until all prior proposed states have been tried. Those states, | |
# in turn, may of course also queue more future proposed states. | |
# In this way, the solution with the fewest moves (least "depth") | |
# will be found if any solutions exist at all. | |
# statetrail: INFINITE LOOP DETECTION, PLUS QUEUE OPTIMIZATION | |
# | |
# the statetrail avoids re-examining states that are superficially | |
# different but represent a logical state already examined. | |
statetrail = {puzzle.canonicalstate()} | |
q = [(puzzle, [])] # state queue, starting with initial, and movetrail | |
while q: | |
z, movetrail = q.pop(0) | |
for move in z.legalmoves(): | |
z2 = z.clone() | |
z2.move(move) | |
z2state = z2.canonicalstate() | |
if z2state not in statetrail: | |
if z2.endstate: | |
return movetrail + [move] | |
statetrail.add(z2state) | |
q.append((z2, movetrail + [move])) | |
# no solution was found | |
return None | |
if __name__ == "__main__": | |
import unittest | |
class TowerOfHanoi: | |
def __init__(self, *, ndiscs=5, npins=3): | |
self.ndiscs = ndiscs | |
self.pins = [list() for _ in range(npins)] | |
self.pins[0] = list(range(ndiscs, 0, -1)) | |
def clone(self): | |
c = self.__class__(ndiscs=self.ndiscs, npins=len(self.pins)) | |
c.pins = [[d for d in p] for p in self.pins] | |
return c | |
def legalmoves(self): | |
"""Yield tuples (src, dst) describing a disc move.""" | |
for sn, src in enumerate(self.pins): | |
for dn, dst in enumerate(self.pins): | |
if (sn != dn) and src: | |
if (not dst) or (src[-1] < dst[-1]): | |
yield sn, dn | |
def move(self, sndn): | |
sn, dn = sndn | |
srcdisc = self.pins[sn][-1] | |
dst = self.pins[dn] | |
if dst and dst[-1] < srcdisc: | |
raise ValueError(f"Illegal move {sn}->{dn}") | |
self.pins[sn].pop() | |
dst.append(srcdisc) | |
def canonicalstate(self): | |
# this should be optimized, later... | |
return tuple(tuple(p) for p in self.pins) | |
@property | |
def endstate(self): | |
return len(self.pins[-1]) == self.ndiscs | |
class TestMethods(unittest.TestCase): | |
def test1(self): | |
# this is a weak test but it is what it is. | |
for puzzlesize in range(1, 9): | |
with self.subTest(puzzlesize=puzzlesize): | |
h = TowerOfHanoi(ndiscs=puzzlesize) | |
s = solver(h) | |
self.assertEqual(len(s), (2**puzzlesize)-1) | |
unittest.main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment