Solve multiple puzzles that have initial states and final state

readme.md

Rotate puzzle

'''
Init None
swap (('snail', 'boat', 'fish', 'seagull', 'mouse'), ('dove', 'maple', 'pine', 'flower', 'mushroom'))
rotate right (('dove', 'boat', 'fish', 'seagull', 'mouse'), ('snail', 'maple', 'pine', 'flower', 'mushroom'))
rotate right (('dove', 'boat', 'fish', 'seagull', 'mouse'), ('mushroom', 'snail', 'maple', 'pine', 'flower'))
swap (('dove', 'boat', 'fish', 'seagull', 'mouse'), ('flower', 'mushroom', 'snail', 'maple', 'pine'))
rotate right (('flower', 'boat', 'fish', 'seagull', 'mouse'), ('dove', 'mushroom', 'snail', 'maple', 'pine'))
swap (('flower', 'boat', 'fish', 'seagull', 'mouse'), ('pine', 'dove', 'mushroom', 'snail', 'maple'))
rotate left (('pine', 'boat', 'fish', 'seagull', 'mouse'), ('flower', 'dove', 'mushroom', 'snail', 'maple'))
swap (('mouse', 'pine', 'boat', 'fish', 'seagull'), ('flower', 'dove', 'mushroom', 'snail', 'maple'))
rotate left (('flower', 'pine', 'boat', 'fish', 'seagull'), ('mouse', 'dove', 'mushroom', 'snail', 'maple'))
swap (('seagull', 'flower', 'pine', 'boat', 'fish'), ('mouse', 'dove', 'mushroom', 'snail', 'maple'))
rotate right (('mouse', 'flower', 'pine', 'boat', 'fish'), ('seagull', 'dove', 'mushroom', 'snail', 'maple'))
swap (('mouse', 'flower', 'pine', 'boat', 'fish'), ('maple', 'seagull', 'dove', 'mushroom', 'snail'))
rotate right (('maple', 'flower', 'pine', 'boat', 'fish'), ('mouse', 'seagull', 'dove', 'mushroom', 'snail'))
rotate right (('maple', 'flower', 'pine', 'boat', 'fish'), ('snail', 'mouse', 'seagull', 'dove', 'mushroom'))
swap (('maple', 'flower', 'pine', 'boat', 'fish'), ('mushroom', 'snail', 'mouse', 'seagull', 'dove'))
rotate left (('mushroom', 'flower', 'pine', 'boat', 'fish'), ('maple', 'snail', 'mouse', 'seagull', 'dove'))
swap (('fish', 'mushroom', 'flower', 'pine', 'boat'), ('maple', 'snail', 'mouse', 'seagull', 'dove'))
rotate left (('maple', 'mushroom', 'flower', 'pine', 'boat'), ('fish', 'snail', 'mouse', 'seagull', 'dove'))
rotate right (('boat', 'maple', 'mushroom', 'flower', 'pine'), ('fish', 'snail', 'mouse', 'seagull', 'dove'))
swap (('boat', 'maple', 'mushroom', 'flower', 'pine'), ('dove', 'fish', 'snail', 'mouse', 'seagull'))
rotate left (('dove', 'maple', 'mushroom', 'flower', 'pine'), ('boat', 'fish', 'snail', 'mouse', 'seagull'))
Finished (('pine', 'dove', 'maple', 'mushroom', 'flower'), ('boat', 'fish', 'snail', 'mouse', 'seagull'))
Solved in 23 steps
'''


if __name__ == "__main__":
        
    rp = RotaryPuzzle(left_clockwise=True, right_clockwise=True)
    init_left = ('owl', 'moon', 'mushroom', 'snail', 'wolf', 'snake', 'spider', 'mouse')
    init_right = ('pine', 'moose', 'lotus', 'rabit', 'bear', 'frog', 'maple', 'butterfly')
    goal_left = ('rabit', 'butterfly', 'owl', 'maple', 'moose', 'frog', 'lotus', 'bear')
    goal_right = ('snake', 'wolf', 'mushroom', 'mouse', 'spider', 'pine', 'moon', 'snail')
    solved = rp.solve(
        (init_left, init_right),
        (goal_left, goal_right)
    )
    rp.show_steps(solved, (goal_left, goal_right))
    #### Ooops to slow to complete, need optimize
    

Re arrange puzzle

if __name__ == "__main__":
    rap = RotaryArrangePuzzle()
    init = (
        ('mapple', 'cactus flower'),
        ('pine', 'coconut leaf'),
        ('long cactus', 'mushroom'),
        ('red flower', 'white flower')
    )
    goal = (
        ('mapple', 'pine'),
        ('cactus flower', 'long cactus'),
        ('coconut leaf', 'red flower'),
        ('mushroom', 'white flower')
    )
    solved = rap.solve(init, goal)
    rap.show_steps(solved, goal)
    
'''
Init None
rotate left (anticlockwise) (('mapple', 'cactus flower'), ('pine', 'coconut leaf'), ('long cactus', 'mushroom'), ('red flower', 'white flower'))
swap topleft (('pine', 'cactus flower'), ('long cactus', 'coconut leaf'), ('red flower', 'mushroom'), ('mapple', 'white flower'))
swap topright (('cactus flower', 'pine'), ('long cactus', 'coconut leaf'), ('red flower', 'mushroom'), ('mapple', 'white flower'))
swap lowerright (('cactus flower', 'pine'), ('coconut leaf', 'long cactus'), ('red flower', 'mushroom'), ('mapple', 'white flower'))
rotate right (clockwise) (('cactus flower', 'pine'), ('coconut leaf', 'long cactus'), ('mushroom', 'red flower'), ('mapple', 'white flower'))
Finished (('mapple', 'pine'), ('cactus flower', 'long cactus'), ('coconut leaf', 'red flower'), ('mushroom', 'white flower'))
Solved in 7 steps
'''

Sliding puzzle Goal

if __name__ == "__main__":
        
    sp = SlidingPuzzle('x')
    init = "SPOTxNRQU"
    goal = "NOPQRSTUx"
    solved = sp.solve(init, goal)
    sp.show_steps(solved, goal)

'''
Init None
Down SPOTxNRQU
Right SxOTPNRQU
Up xSOTPNRQU
Left TSOxPNRQU
Left TSOPxNRQU
Down TSOPNxRQU
Right TSxPNORQU
Up TxSPNORQU
Right TNSPxORQU
Down TNSxPORQU
Left xNSTPORQU
Up NxSTPORQU
Left NPSTxORQU
Down NPSTOxRQU
Right NPxTOSRQU
Up NxPTOSRQU
Up NOPTxSRQU
Right NOPTQSRxU
Down NOPTQSxRU
Left NOPxQSTRU
Up NOPQxSTRU
Left NOPQRSTxU
Finished NOPQRSTUx
Solved in 24 steps
'''

if __name__ == "__main__":
    hanoi = TowerOfHanoi()
    initial = (
        (),
        (6, 5, 4, 3, 2, 1),
        ()
    )
    goal = (
        (6, 5, 4, 3, 2, 1),
        (),
        ()
    )
    solved = hanoi.solve(initial, goal)
    hanoi.show_steps(solved, goal)
    
'''
Init None
Move 1 to () ((), (6, 5, 4, 3, 2, 1), ())
Move 1 to () ((), (6, 5, 4, 3, 2), (1,))
Move 2 to (2,) ((2,), (6, 5, 4, 3), (1,))
Move 1 to () ((2, 1), (6, 5, 4, 3), ())
Move 0 to (6, 5, 4) ((2, 1), (6, 5, 4), (3,))
Move 0 to (3,) ((2,), (6, 5, 4, 1), (3,))
Move 1 to (3, 2) ((), (6, 5, 4, 1), (3, 2))
Move 1 to () ((), (6, 5, 4), (3, 2, 1))
Move 2 to (4,) ((4,), (6, 5), (3, 2, 1))
Move 2 to (6, 5) ((4, 1), (6, 5), (3, 2))
Move 0 to (6, 5, 2) ((4, 1), (6, 5, 2), (3,))
Move 2 to (4,) ((4,), (6, 5, 2, 1), (3,))
Move 1 to () ((4, 3), (6, 5, 2, 1), ())
Move 1 to (4, 3) ((4, 3), (6, 5, 2), (1,))
Move 2 to (4, 3, 2) ((4, 3, 2), (6, 5), (1,))
Move 1 to () ((4, 3, 2, 1), (6, 5), ())
Move 0 to (6,) ((4, 3, 2, 1), (6,), (5,))
Move 0 to (5,) ((4, 3, 2), (6, 1), (5,))
Move 1 to (5, 2) ((4, 3), (6, 1), (5, 2))
Move 0 to (6,) ((4, 3), (6,), (5, 2, 1))
Move 2 to (4,) ((4,), (6, 3), (5, 2, 1))
Move 2 to (6, 3) ((4, 1), (6, 3), (5, 2))
Move 0 to (6, 3, 2) ((4, 1), (6, 3, 2), (5,))
Move 0 to (5,) ((4,), (6, 3, 2, 1), (5,))
Move 1 to (5, 4) ((), (6, 3, 2, 1), (5, 4))
Move 1 to () ((), (6, 3, 2), (5, 4, 1))
Move 2 to (2,) ((2,), (6, 3), (5, 4, 1))
Move 1 to (5, 4) ((2, 1), (6, 3), (5, 4))
Move 0 to (6,) ((2, 1), (6,), (5, 4, 3))
Move 0 to (5, 4, 3) ((2,), (6, 1), (5, 4, 3))
Move 1 to (5, 4, 3, 2) ((), (6, 1), (5, 4, 3, 2))
Move 1 to () ((), (6,), (5, 4, 3, 2, 1))
Move 2 to (6,) ((6,), (), (5, 4, 3, 2, 1))
Move 2 to () ((6, 1), (), (5, 4, 3, 2))
Move 0 to (2,) ((6, 1), (2,), (5, 4, 3))
Move 2 to (6,) ((6,), (2, 1), (5, 4, 3))
Move 1 to (5, 4) ((6, 3), (2, 1), (5, 4))
Move 1 to (6, 3) ((6, 3), (2,), (5, 4, 1))
Move 2 to (6, 3, 2) ((6, 3, 2), (), (5, 4, 1))
Move 2 to () ((6, 3, 2, 1), (), (5, 4))
Move 0 to (4,) ((6, 3, 2, 1), (4,), (5,))
Move 0 to (5,) ((6, 3, 2), (4, 1), (5,))
Move 1 to (5, 2) ((6, 3), (4, 1), (5, 2))
Move 0 to (4,) ((6, 3), (4,), (5, 2, 1))
Move 2 to (6,) ((6,), (4, 3), (5, 2, 1))
Move 2 to (4, 3) ((6, 1), (4, 3), (5, 2))
Move 0 to (4, 3, 2) ((6, 1), (4, 3, 2), (5,))
Move 2 to (6,) ((6,), (4, 3, 2, 1), (5,))
Move 1 to () ((6, 5), (4, 3, 2, 1), ())
Move 1 to (6, 5) ((6, 5), (4, 3, 2), (1,))
Move 2 to (6, 5, 2) ((6, 5, 2), (4, 3), (1,))
Move 1 to () ((6, 5, 2, 1), (4, 3), ())
Move 0 to (4,) ((6, 5, 2, 1), (4,), (3,))
Move 0 to (3,) ((6, 5, 2), (4, 1), (3,))
Move 1 to (3, 2) ((6, 5), (4, 1), (3, 2))
Move 1 to (6, 5) ((6, 5), (4,), (3, 2, 1))
Move 2 to (6, 5, 4) ((6, 5, 4), (), (3, 2, 1))
Move 2 to () ((6, 5, 4, 1), (), (3, 2))
Move 0 to (2,) ((6, 5, 4, 1), (2,), (3,))
Move 2 to (6, 5, 4) ((6, 5, 4), (2, 1), (3,))
Move 1 to () ((6, 5, 4, 3), (2, 1), ())
Move 1 to (6, 5, 4, 3) ((6, 5, 4, 3), (2,), (1,))
Move 2 to (6, 5, 4, 3, 2) ((6, 5, 4, 3, 2), (), (1,))
Finished ((6, 5, 4, 3, 2, 1), (), ())
Solved in 65 steps
'''

if __name__ == "__main__":
    star = SevenPointStar()
    init = "3721654"
    goal = "1234567"
    solved = star.solve(init, goal)
    star.show_steps(solved, goal)
    
'''
Init None
Swap 0 3 3721654
Swap 1 5 1723654
Swap 1 4 1523674
Swap 2 5 1623574
Swap 1 5 1673524
Swap 3 6 1273564
Swap 2 6 1274563
Finished 1234567
Solved in 9 steps
'''

if __name__ == "__main__":
    r = RotateRBY()
    init = "YRRBRBRYRRRYRBRRRRB"
    goal = "RRRRBYRRBYBRRYBRRRR"
    solved = r.solve(init, goal)
    r.show_steps(solved, goal)
    
'''
Init None
Click 8 YRRBRBRYRRRYRBRRRRB
Click 4 YRRYBBRRRRRYBRRRRRB
Click 13 YYRRBRRRRBRYBRRRRRB
Click 10 YYRRBRRRBRRYRRBRRRB
Click 14 YYRRBRRRBBRRRRRYRRB
Click 9 YYRRBRRRBRBRRRRRRBY
Click 14 YYRRBBRRRRRRRRBRRBY
Click 4 YYRRBBRRRRRRRBBRRYR
Click 14 RYRRBYRRRBRRRBBRRYR
Click 4 RYRRBYRRRBBRRYBRRRR
Finished RRRRBYRRBYBRRYBRRRR
Solved in 12 steps
'''

if __name__ == '__main__':
    sr = SumRotate()
    init = (
        (4, 1, 1, 1, 3, 1),
        (1, 1, 2, 1, 3, 1),
        (4, 1, 3, 1, 2, 2),
        (1, 2, 3, 1, 3, 2)
    )
    goal = (11, 5, 10, 4, 9, 6)
    solved = sr.solve(init, goal, max_depth=2000)
    goal_state = sr.goal_state
    if goal_state:
        sr.show_steps(solved, goal_state)
    else:
        print("Cannot solve")
        Init None
 
'''
Rotate 1 clockwise ((4, 1, 1, 1, 3, 1), (1, 1, 2, 1, 3, 1), (4, 1, 3, 1, 2, 2), (1, 2, 3, 1, 3, 2))
Rotate 1 clockwise ((4, 1, 1, 1, 3, 1), (1, 2, 1, 3, 1, 1), (4, 1, 3, 1, 2, 2), (1, 2, 3, 1, 3, 2))
Finished ((4, 1, 1, 1, 3, 1), (2, 1, 3, 1, 1, 1), (4, 1, 3, 1, 2, 2), (1, 2, 3, 1, 3, 2))
Solved in 4 steps

'''

if __name__ == '__main__':
    solver = LinkedRotaryPuzzle(
        ((0, 6), (0, 6), (0, 6)),
        {
            0: {
                2: -1
            },
            1: {
                0: -1
            },
            2: {
                1: 1
            }
        }
    )
    visited = solver.solve((1, 0, 0), (0, 0, 0))
    solver.show_steps(visited, (0, 0, 0))

base.py

from typing import *
from abc import ABCMeta, abstractmethod
from collections import deque


class PuzzleSolver(metaclass=ABCMeta):
    """Abstract class for solve puzzle that have initial state and end state
    Simple breath first search
    from any state -> generate next reachable state and eliminated duplicate state
    until reach goal or max depth reached
    """

    @abstractmethod
    def next_state(self, state: Any, depth: int) -> Iterable[Tuple[Any, str]]:
        """Generate next reachable state from current state.
        Function must return iterable of pairs (next_state, explain message)
        """
        pass
    
    def finished(self, state: Any, goal: Any) -> bool:
        """Check if current state is end state"""
        return state == goal

    def solve(
            self,
            init_state: Any,
            goal: Any,
            max_depth: int = 100
        ) -> Dict[Any, Any]:
        """
        Solve using BFS iterate throw every reachable state and record the path
        """
        queue = deque([(init_state, 0)])
        visited = {init_state: (None, 'Init')}
        while queue:
            state, depth = queue.popleft()
            if self.finished(state, goal) or depth > max_depth:
                return visited
            if depth < max_depth:
                for new_state, next_msg in self.next_state(state):
                    if new_state not in visited:
                        visited[new_state] = state, next_msg
                        queue.append((new_state, depth + 1))
            
        return visited

    def show_steps(self, visited: Dict[Any, Any], goal: Any):
        """Construct the path from visited"""
        if not visited or goal not in visited:
            print('Cannot solved')
            return
        steps = [f'Finished {goal}']
        state = goal
        while state in visited:
            state, msg = visited[state]
            steps.append(f'{msg} {state}')
        for msg in reversed(steps):
            print(msg)
        print(f'Solved in {len(steps)} steps')

rotary_arrange.py

class RotaryArrangePuzzle(PuzzleSolver):
    """
        4 corners (topleft, topright, lowerright, lowerleft) 
            of tuple (inner, outer)
        transforms: 
            swap_inner (4)
            rotate left
            rotate right
    """
    def rotate(self, state: Tuple, clockwise=False) -> Tuple:
        """Perform rotation on inner disk"""
        (topleft, topright, lowerright, lowerleft) = state
        tails = (topleft[1], topright[1], lowerright[1], lowerleft[1])
        if clockwise:
            heads = (lowerleft[0], topleft[0], topright[0], lowerright[0]) 
        else:
            heads = (topright[0], lowerright[0], lowerleft[0], topleft[0]) 
        return tuple(zip(heads, tails))

    def swap_inner(self, state: Tuple, position: int) -> Tuple:
        """Swap items of pos state"""
        item = state[position]
        swapped = ((item[1], item[0]), )
        return state[:position] + swapped + state[position + 1:]

    def swapped(self, pair: Tuple) -> Tuple:
        return pair[1], pair[0]

    def next_state(self, state: Tuple) -> Iterable[Tuple[Tuple, str]]:
        """At any state we have 6 choices
        swap item on four corners (4)
        rotate left
        rotate right
        """
        (topleft, topright, lowerright, lowerleft) = state
        yield (self.swapped(topleft), topright, lowerright, lowerleft), 'swap topleft'
        yield (topleft, self.swapped(topright), lowerright, lowerleft), 'swap topright'
        yield (topleft, topright, self.swapped(lowerright), lowerleft), 'swap lowerright'
        yield (topleft, topright, lowerright, self.swapped(lowerleft)), 'swap lowerleft'
        yield self.rotate(state, clockwise=True), 'rotate right (clockwise)'
        yield self.rotate(state, clockwise=False), 'rotate left (anticlockwise)'

rotary_puzzle.py

class RotaryPuzzle(PuzzleSolver):
    def __init__(self, left_clockwise=False, right_clockwise=False):
        self.left_clockwise = left_clockwise
        self.right_clockwise = right_clockwise

    def rotate(self, state: Tuple, clockwise=False) -> Tuple:
        """Perform rotation on single disk"""
        if not clockwise:
            return (state[-1], ) + state[:-1]
        else:
            return state[1:] + (state[0], )

    def swap(self, left: Tuple, right: Tuple) -> Tuple[Tuple, Tuple]:
        """Swap first item of each state"""
        return (right[0], ) + left[1:], (left[0], ) + right[1:]

    def next_state(
        self, 
        state: Tuple[Tuple, Tuple]
    ) -> Iterable[Tuple[Tuple[Tuple, Tuple], str]]:
        """At any state we have three choices
        rotate left disk
        rotate right disk
        swap item
        """
        left, right = state
        yield (self.rotate(left, clockwise=self.left_clockwise), right), 'rotate left'
        yield (left, self.rotate(right, clockwise=self.right_clockwise)), 'rotate right'
        yield self.swap(left, right), 'swap'

rotate_linked_wheels_offset.py

class LinkedRotaryPuzzle(PuzzleSolver):
    """
        Some knob linked in certain ways that need to all set to same state
        wheels = ((min1, max1), (min2, max2), ...)
        linked = {
          0: {
            1: 1
            2: -1
          },
          2: {
            2: 3,
            4: 1
          }
        }
        when 0 turn 1, 1 will turn 1, 2 will turn 1 backward
        when 2 click, 2 will turn 3, 4 will turn 1
    """
    def __init__(self, wheels: List[Tuple[int, int]], linked: Dict[int, Dict[int, int]]):
        self.wheels = wheels
        self.linked = linked

    def action(self, oldstate, index):
        wheels = self.wheels
        linked = self.linked
        opts = linked.get(index, {})
        times = opts.get(index, 1)
        clockwise = times > 0
        state = list(oldstate)
        state[index] = (state[index] + times) % (wheels[index][1] - wheels[index][0] + 1)
        for other, othertimes in opts.items():
            if other != index:
                state[other] = (state[other] + othertimes) % (wheels[other][1] - wheels[other][0] + 1)
                    
        return tuple(state)

    def next_state(self, state: Tuple) -> Iterable[Tuple[Tuple, str]]:
        """At any state, a knob can be rotate and it will affect others
        """
        n = len(state)
        for i in range(n):
            next_state = self.action(state, i)
            print(f'{state} ({i}) -> {next_state}')
            yield next_state, f'Click {i}'

rotate_rby.py

class RotateRBY(PuzzleSolver):
    """ I ran out of name so rotate red blue yellow
        click inside spot will rotate it 6 surrounding tile
        init
            Y   R   R               0   1   2
          B   R   B   R           3   4   5   6
        Y   R   R   R   Y       7   8   9   10  11
          R   B   R   R          12  13  14   15
            R   R   B               16  17  18
        goal
            R   R   R            click 4 rotate: 0,1,5,9,8,3
          R   B   Y   R          click 5 rotate: 1,2,6,10,9,4
        R   B   Y   B   R        click 9 rotate: 4,5,10,14,13,8
          R   Y   B   R
            R   R   R
    """
    ROTATION = {
        4: (0, 1, 5, 9, 8, 3),
        5: (1, 2, 6, 10, 9, 4),
        8: (3, 4, 9, 13, 12, 7),
        9: (4, 5, 10, 14, 13, 8),
        10: (5, 6, 11, 15, 14, 9),
        13: (8, 9, 14, 17, 16, 12),
        14: (9, 10, 15, 18, 17, 13)
    }

    def __init__(self, clockwise=True):
        self.clockwise = clockwise

    def rotate(self, state, center) -> str:
        if center not in self.ROTATION:
            return state
        state = list(state)
        r = self.ROTATION[center]
        tmp = [state[i] for i in r]
        if self.clockwise:
            tmp = tmp[-1:] + tmp[:-1]
        else:
            tmp = tmp[1:] + tmp[:1]
        j = 0
        for i in r:
            state[i] = tmp[j]
            j += 1
        return ''.join(state)

    def next_state(self, state: str) -> Iterable[Tuple[str, str]]:
        for center in self.ROTATION:
            yield self.rotate(state, center), f"Click {center}"

seven_star.py

class SevenPointStar(PuzzleSolver):
    """
        Restore the star by swaping its points.
        Point can only move if they have line between them
        Init    v
                3       7
        4                       2
            5               1
                    6
        Goal    v
                1       2
        7                        3
            6               4
                    5
        3 (index 0) can only swap with 1 or 6 (index 3, 4)
        7 (index 1) can only swap with 6 or 5 (index 4, 5)
        1 (index 3) can only swap with 4 or 3 (index 6, 0)
        6 (index 4) can only swap with 3 or 7 (index 0, 1)
        -> index can post with its index + 3 % 7, index + 4 % 7
    """
    def swap(self, state: str, x: int, y: int) -> str:
        if x > y:
            x, y = y, x
        return ''.join((state[:x], state[y], state[x+1:y], state[x], state[y+1:]))
    
    def next_state(self, state: str) -> Iterable[Tuple[str, str]]:
        for i in range(7):
            yield self.swap(state, i, (i + 3) % 7), f"Swap {i} {(i + 3) % 7}"
            yield self.swap(state, i, (i + 4) % 7), f"Swap {i} {(i + 4) % 7}"

sliding.py

class SlidingPuzzle(PuzzleSolver):
    """9x9 puzzle with a missing piece, other piece can slide into the missing one
        encode the grid
        1-1-2
        3-4-5
        6-7-x
        like this
        (123), (456), (78x)
        or simply flat
        "12345678x"
    """

    """Missing at 0 
            x12    0x2    012
            345 -> 345 -> x45   swap 0 1 or 0 3
            678    678    678
        Missing at 4
            012    0x2    012    012    012
            3x5 -> 345 -> x45 -> 345 -> 34x   swap 4 with 1, 3, 5, 7
            678    678    678    6x8    678
    """
    MOVES_SWAP = {
        0: (1, 3),
        1: (0, 2, 4),
        2: (1, 5),
        3: (0, 4, 6),
        4: (1, 3, 5, 7),
        5: (2, 4, 8),
        6: (3, 7),
        7: (4, 6, 8),
        8: (5, 7)
    }

    def __init__(self, missing_char="x"):
        self.missing_char = missing_char

    def swap(self, state: str, x: int, y: int) -> str:
        if x > y:
            x, y = y, x
        return ''.join((state[:x], state[y], state[x+1:y], state[x], state[y+1:]))
    
    def next_state(self, state: str) -> Iterable[Tuple[str, str]]:
        missing_pos = state.index(self.missing_char)
        for move in self.MOVES_SWAP[missing_pos]:
            if move > missing_pos:
                if move == missing_pos + 1:
                    msg = "Left"
                else:
                    msg = "Up"
            else:
                if move == missing_pos - 1:
                    msg = "Right"
                else:
                    msg = "Down"
            yield self.swap(state, missing_pos, move), msg

sum_rotate.py

class SumRotate(PuzzleSolver):
    """
        Stacked of 4 hexagon (or more) disk, rotate it to match the target sum
        state is a list of each hexagon (rotation make easier)
    """
    goal_state = None   # Cache last state that make up the goal

    def finished(self, state: Any, goal: Any) -> bool:
        """Check if each sum = goal"""
        for col, target in enumerate(goal):
            total = 0
            for rows in state:
                total += rows[col]
            if total != target:
                return False
        self.goal_state = state
        return True

    def rotate(self, row: Tuple, clockwise=False) -> Tuple:
        """Perform rotation on single disk"""
        if not clockwise:
            return (row[-1], ) + row[:-1]
        else:
            return row[1:] + (row[0], )

    def next_state(self, state: tuple) -> Iterable[Tuple[tuple, str]]:
        for idx, row in enumerate(state):
            next_row = self.rotate(row, clockwise=True)
            yield state[:idx] + (next_row, ) + state[idx + 1:], f'Rotate {idx} clockwise'
            next_row = self.rotate(row, clockwise=False)
            yield state[:idx] + (next_row, ) + state[idx + 1:], f'Rotate {idx} counter clockwise'

tower_hanoi.py

class TowerOfHanoi(PuzzleSolver):
    """
        Three columns, and some disks largest to smalest.
        You have to move from one column to another one disk at a time
        You cannot put the larger disk on top smaller one
        state can be 3 tuple (stacks)
        |             [|]             |
        |            [ | ]            |
        |           [  |  ]           |
        |          [   |   ]          |
        |         [    |    ]         |
        |        [     |     ]        |
    """
    def next_state(self, state: str) -> Iterable[Tuple[str, str]]:
        """ Try to move to next column. column ^ 2?
        """
        columns = len(state)
        for isrc in range(columns):
            src = state[isrc]
            if len(src) == 0:
                continue
            for idsc in range(columns):
                if isrc == idsc:
                    continue
                dsc = state[idsc]
                if len(dsc) == 0 or src[-1] < dsc[-1]:
                    disk = src[-1]
                    new_src = src[:-1]
                    new_dsc = dsc + (disk, )
                    if isrc < idsc:
                        yield state[:isrc] + (new_src, ) + state[isrc + 1: idsc] + \
                            (new_dsc, ) + state[idsc + 1:], f'Move {isrc} to {idsc}'
                    else:
                        yield state[:idsc] + (new_dsc, ) + state[idsc + 1: isrc] + \
                            (new_src, ) + state[isrc + 1:], f'Move {isrc} to {idsc}'