Generic breadth-first puzzle solution search. A generic framework from the knightspages.py gist

puzzlesolver.py

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