james4388 · December 31, 2020 18:45
diff --git a/readme.md b/readme.md
diff --git a/base.py b/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')
diff --git a/rotary_arrange.py b/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)'
diff --git a/rotary_puzzle.py b/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'
diff --git a/rotate_linked_wheels_offset.py b/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}'
diff --git a/rotate_rby.py b/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}"
diff --git a/seven_star.py b/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}"
diff --git a/sliding.py b/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
diff --git a/sum_rotate.py b/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'
diff --git a/tower_hanoi.py b/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}'
	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')
	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)'
	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'
	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}'
	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}"
	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}"
	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
	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'
	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}'