solitaire_chess.py

import typing
from collections import namedtuple
from string import ascii_lowercase

Moves = namedtuple('Moves', 'dxs, dys, free')

Pos = typing.Tuple[int, int]
Board = typing.Dict[Pos, str]

BOARD_SIZE = 4

KING_MOVES = [-1, -1, 0, 1, 1, 1, 0, -1], [0, 1, 1, 1, 0, -1, -1, -1]

MOVE_MAP = {
    'p': Moves([-1, 1], [1, 1], False),
    'N': Moves([-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1], False),
    'B': Moves([-1, 1, 1, -1], [1, 1, -1, -1], True),
    'R': Moves([-1, 0, 1, 0], [0, 1, 0, -1], True),
    'Q': Moves(*KING_MOVES, True),
    'K': Moves(*KING_MOVES, False),
}


def init_board(str_board: typing.List[str]) -> Board:
    """A convenience function to convert a multiline board into a dict.

    Args:
        str_board: A multiline board.

    Returns:
        A dict-based board.

    """
    return {(x, y): piece for y, line in enumerate(reversed(str_board)) for x, piece in enumerate(line) if piece in MOVE_MAP}


def is_good_coordinate(value: int) -> bool:
    """A helper function to return True if the coordinate value is valid.

    Args:
        value: A coordinate value.

    Returns:
        True if the coordinate value is valid.
    """
    return 0 <= value < BOARD_SIZE


def strikes(board: Board, piece: str, pos: Pos) -> typing.Generator[Pos, None, None]:
    """Yield all possible strikes for a given piece and a given board set up.

    We supply piece information as it's more convenient to remove it by now from the board (touch-move).

    Args:
        board: A board.
        piece: A piece.
        pos: Position of the piece.

    Yields:
        Positions for valid strikes.

    """
    x, y = pos
    moves = MOVE_MAP[piece]
    for dx, dy in zip(moves.dxs, moves.dys):
        mult = 1
        while True:
            candidate_pos = (x + dx * mult, y + dy * mult)
            if all(map(is_good_coordinate, candidate_pos)):
                if candidate_pos in board:
                    yield candidate_pos
                # Free-moving pieces can't move beyond another piece in the path:
                if moves.free and candidate_pos not in board:
                    mult += 1
                    continue
            break


def to_notation(piece: str, target_pos: Pos) -> str:
    """A convenience function to return (nearly) algebraic notation.

    Args:
        piece: A piece
        target_pos: Target position

    Returns:
        Notation as a string.

    """
    return f'{piece}x{ascii_lowercase[target_pos[0]]}{target_pos[1] + 1}'


def recursive_solve(board: Board, moves: typing.List[str]) -> typing.List[typing.List[str]]:
    """Recursively solve the board. A slightly shorter solution compared to stack-based
    due to the need to undo each move.

    Args:
        board: A board.
        moves: Current stack of moves.

    Returns:

    """
    if len(board) == 1:
        return [moves]

    solutions = []
    for striker_pos in sorted(board):
        # Blank out the striker piece as we are going to be moving it
        striker_piece = board.pop(striker_pos)
        for target_pos in strikes(board, striker_piece, striker_pos):
            # Overwrite the new piece
            target_piece = board[target_pos]
            board[target_pos] = striker_piece
            solutions.extend(recursive_solve(board, moves + [to_notation(striker_piece, target_pos)]))
            # Restore the target piece
            board[target_pos] = target_piece

        # Restore the striker piece
        board[striker_pos] = striker_piece

    return solutions


if __name__ == '__main__':
    board = [
        '   N',
        '  N ',
        ' RRp',
        'pB  ',
    ]
    solutions = recursive_solve(init_board(board), [])
    print(f'{len(solutions) or "No"} solutions found')
    print('\n'.join([', '.join(s) for s in sorted(solutions)]))