Solver for "Jumping Checkers" puzzle.

jumping_checkers.py

"""Solver for "Jumping Checkers" problem.

Place 3 white checkers in squares 1, 2, and 3 of the figure, and 3 black ones
on swuares 5, 6, 7. Shift the white checkers to the squares occupied by the
black ones, and vice versa.

    Board       |0|0|0| |1|1|1|
    Square #     1 2 3 4 5 6 7

You may move a checker forward to an adjacent unoccupied square, if any.
You may jump a checker forward over an adjacent checker into the vacant square.

The solution requires 15 moves.

from Boris A Kordemksy, The Moscow Puzzles: 359 Mathematical Recreations, p35.
"""

from collections import deque

def show(board):
    """Return string representation of board."""
    return '|'.join([str(item) if item != '' else ' ' for item in board])

def print_solutions(solutions):
    """Print solutions."""
    by_length = sorted(solutions, key=lambda x: len(x))
    for ind, history in enumerate(by_length):
        print '\nSolution #', ind + 1, 'of', len(solutions)
        print len(history) - 1, 'steps'
        print '\n'.join(show(board) for board in history)

def swap_checkers(board, pair):
    """Return copy of board with pair of indices swapped."""
    fst, snd = pair
    new_board = board[:]
    new_board[fst], new_board[snd] = new_board[snd], new_board[fst]
    return new_board

def gen_next_boards(board):
    """Return list of all possible next boards."""
    i = board.index('')
    left, right = 0, len(board) - 1
    swaps = [(i, max(left, i - 1)), (i, min(right, i + 1)),
             (i, max(left, i - 2)), (i, min(right, i + 2))]
    return [swap_checkers(board, pair) for pair in swaps]

def gen_next(board, visited, goal):
    """Generate list of valid next boards and update list of visited states."""

    next_boards = []
    for board in gen_next_boards(board):
        if board == goal:
            next_boards.append(board)
        elif board not in visited:
            next_boards.append(board)
            visited.append(board)

    return next_boards, visited

def find_solutions(start, goal):
    """Main solver. Return list of all solutions (list of list of states)."""

    completed = []
    visited = [start]
    histories = deque([([start], visited)])

    while histories:
        history, visited = histories.popleft()
        next_boards, visited = gen_next(history[-1], visited, goal)

        for board in next_boards:
            if board == goal:
                completed.append(history + [board])
            else:
                histories.append((history + [board], visited))

    return completed

def main():
    """Call solver, print solutions."""
    start = [0, 0, 0, '', 1, 1, 1]
    goal = [1, 1, 1, '', 0, 0, 0]

    solutions = find_solutions(start, goal)
    print_solutions(solutions)
    return solutions

if __name__ == '__main__':
    main()