"""
11/24/2018

Dumb backtracking-based solver for the Cracker Barrel Triangle Peg game.
  http://recmath.org/pegsolitaire/CBTips.html

This solution is generic to any N-row triangle.
Doesn't assume any heuristic and also very memory intensive.
"""

def build_moves(n):
    """Returns 1d array of all possible moves for each peg."""
    board = [[True] * i for i in range(1, n+1)]
    ok = lambda cell: cell[0] >= 0 and cell[1] >= 0 and cell[0] < len(board) \
            and cell[1] < len(board[cell[0]])
    convert = lambda cell: ((cell[0] * (cell[0] + 1)) // 2) + cell[1]
    moves = []
    for r in range(len(board)):
        for c in range(len(board[r])):
            steps = [
                ( (r, c+1), (r, c+2) ),
                ( (r, c-1), (r, c-2) ),
                ( (r+1, c), (r+2, c) ),
                ( (r-1, c), (r-2, c) ),
                ( (r+1, c+1), (r+2, c+2) ),
                ( (r-1, c-1), (r-2, c-2) ),
            ]
            steps = [step for step in steps if ok(step[0]) and ok(step[1])]
            moves.append([(convert(step[0]), convert(step[1])) for step in steps])
    return moves


def backtrack(moves, pegs, memo={}, count=0, jumps=[]):
    if len(pegs) == 1:
        return count, jumps
    mn = float('inf'), None
    for peg, steps in enumerate(moves):
        for step in steps:
            edge, dest = step
            if peg not in pegs or edge not in pegs or dest in pegs:
                continue
            pe = set(pegs)
            pe.add(dest)
            pe.remove(edge)
            pe.remove(peg)
            h = str(pe)
            if h in memo:
                continue
            jo = list(jumps)
            jo.append((peg, edge, dest))
            memo[h], jo = backtrack(moves, pe, memo, count+1, jo)
            if memo[h] < mn[0]:
                mn = memo[h], jo
    return mn


def solve(n, empty):
    moves = build_moves(n)
    pegs = set({i for i in range(len(moves))}) - empty
    return backtrack(moves, pegs)


if __name__ == '__main__':
    n = 5
    count, jumps = solve(n, empty={0})
    print('N: {}, Jumps: {}\n{}'.format(n, len(jumps), jumps))