Skip to content

Instantly share code, notes, and snippets.

@rs2
Last active January 5, 2021 21:31
Show Gist options
  • Save rs2/f8b4a0e6680fb6f102b99b74e9ec78fb to your computer and use it in GitHub Desktop.
Save rs2/f8b4a0e6680fb6f102b99b74e9ec78fb to your computer and use it in GitHub Desktop.
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)]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment