'Peg solitaire' https://www.bilibili.com/video/BV1op4y1S7ZP

Peg solitaire.py

from typing import Tuple, Callable, Dict, Set, List
from functools import reduce, wraps


SIZE = 5

# Triangle shape, central symmetry
# 2 arbitrary axes determin a point
# but we need 3 axes to make it easier to detect boundary conditions
Point = Tuple[int, int, int]  # type

# indicates current state of the game board
Stage = Set[Point]  # type

TransFormFunction = Callable[[Point], Point]  # type
DIRECTIONS: Dict[str, TransFormFunction] = {
    "↗": (lambda p: (p[0]+1, p[1], p[2]-1)),
    "↖": (lambda p: (p[0]+1, p[1]-1, p[2])),
    "→": (lambda p: (p[0], p[1]+1, p[2]-1)),
    "←": (lambda p: (p[0], p[1]-1, p[2]+1)),
    "↘": (lambda p: (p[0]-1, p[1]+1, p[2])),
    "↙": (lambda p: (p[0]-1, p[1], p[2]+1)),
}


def sub(v1: Point, v2: Point) -> Point:
    return tuple(map(lambda a, b: a-b, v1, v2))


def wellformed(p: Point) -> bool:
    return p[0]+p[1]+p[2] == SIZE-1 and reduce(lambda b, w: b and (w >= 0), p, True)


def overflowed(p1: Point, p2: Point) -> bool:
    # point should be in [0,SIZE)
    for w in map(lambda v: v >= SIZE or v <= -SIZE, sub(p1, p2)):
        if w:  # overflowed
            return True
    return False


def neighbor(p1: Point, p2: Point) -> bool:
    for d in sub(p1, p2):
        if d > 1 or d < -1:
            return False
    return True


def transform(p0: Point, direction: str, times: int = 1) -> Point:
    return reduce((lambda p, f: f(p)), [DIRECTIONS[direction]]*times, p0)


# calculate possible next states refers to the point
def calc1(ref_pt: Point, stage: Stage) -> List[Stage]:

    if ref_pt not in stage:
        return []

    if not wellformed(ref_pt):
        return []

    next_stages: List[Stage] = []
    for direction in DIRECTIONS:
        # ●○○ is caused by ○●●  with 6 possible directions
        adding = (transform(ref_pt, direction, 1),
                  transform(ref_pt, direction, 2))
        if (not wellformed(adding[0])) or (not wellformed(adding[1])) or (adding[0] in stage or adding[1] in stage):
            continue  # conflict!

        trying = stage.copy()
        trying.remove(ref_pt)

        def test_stage() -> bool:
            for p in trying:
                if overflowed(p, adding[1]) or overflowed(p, adding[0]):
                    return False
            return True

        if test_stage():  # passed
            trying.update(adding)
            next_stages.append(trying)

    return next_stages


def calc(init: Point) -> List[Dict[str, Point]]:
    Stack = Tuple[Stage, List[Dict[str, Point]]]

    tried_stages = set()
    max_depth = 0

    def recurse(pt: Point, stack: Stack) -> Stack:
        nonlocal tried_stages
        nonlocal max_depth
        if stack[0] in tried_stages:
            return (set(), list())
        next_stages = calc1(pt, stack[0].copy())
        for stage in next_stages:
            pt_to = pt
            pt_via = None
            pt_from = None
            added = stage.difference(stack[0])
            first = added.pop()
            if neighbor(first, pt_to):
                pt_via = first
                pt_from = added.pop()
            else:
                pt_from = first
                pt_via = added.pop()
            next_stack = (
                stage, stack[1]+[{"from": pt_from, "to": pt_to, "via": pt_via}])
            if len(stage) == (SIZE+1)*SIZE/2 - 1:  # full filled, found solution
                yield next_stack
            for p in stage:
                yield from recurse(p, next_stack)
            tried_stages.add(frozenset(next_stack[0]))

    for solution_stage, steps in recurse(init, ({init}, [])):
        # print(solution_stage)
        yield steps


possible_begins = ((i, j, k) for i in range(SIZE) for j in range(SIZE)
                   for k in range(SIZE) if wellformed((i, j, k)))


def solve():
    for p in possible_begins:
        print("start at:", p)
        for solution in calc(p):
            solution.reverse()
            yield solution


#print(len([s for s in solve()]))

for solution in solve():
    print("+"*20, "SOLVED", "+"*20)
    print(">> STEPS >>")
    print("> remove", solution[0]["to"])
    for step in solution:
        print("> move from", step["from"], "to",
              step["to"], "via", step["via"])
    print("THAT'S IT!")