knight-moves-solver.py

# Minimum moves solver for https://www.funnyhowtheknightmoves.com/

from collections import deque

import chess


def main():
    destinations = [chess.F8, chess.E8, chess.C8, chess.B8,
                    chess.H7, chess.G7, chess.E7, chess.C7, chess.A7,
                    chess.H6, chess.G6, chess.F6, chess.B6, chess.A6,
                    chess.H4, chess.G4, chess.F4, chess.B4, chess.A4,
                    chess.H3, chess.G3, chess.E3, chess.C3, chess.A3,
                    chess.H2, chess.F2, chess.E2, chess.C2, chess.B2,
                    chess.G1, chess.F1, chess.E1, chess.C1, chess.B1, chess.A1]
    knight_square = chess.H8

    board = chess.Board()
    board.clear_board()
    board.set_piece_at(knight_square, chess.Piece(chess.KNIGHT, chess.WHITE))
    board.set_piece_at(chess.D5, chess.Piece(chess.QUEEN, chess.BLACK))

    for destination_square in destinations:
        board.clear_board()
        board.set_piece_at(knight_square, chess.Piece(chess.KNIGHT, chess.WHITE))
        board.set_piece_at(chess.D5, chess.Piece(chess.QUEEN, chess.BLACK))
        shortest_path = breadth_first_search(board, knight_square, destination_square,
                                             {knight_square}, [])
        print(f'{chess.square_name(destination_square)} -> {", ".join([chess.square_name(move.to_square) for move in shortest_path])}')
        knight_square = destination_square


def breadth_first_search(board, from_square, to_square, visited, path):
    queue = deque()
    queue.append((board.copy(stack=False), [], {from_square}))

    while queue:
        board, path, visited = queue.popleft()
        for legal_move in board.legal_moves:
            if legal_move.to_square in visited:
                continue

            if legal_move.to_square == chess.D5:
                # Cannot take queen.
                continue

            if board.is_attacked_by(chess.BLACK, legal_move.to_square):
                # Cannot go to a square attacked by the queen.
                continue

            new_board = board.copy(stack=False)
            new_board.push(legal_move)
            new_board.turn = chess.WHITE

            new_square = legal_move.to_square
            new_visited = set(visited)
            new_visited.add(new_square)

            if new_square == to_square:
                return path + [legal_move]
            queue.append((new_board, path + [legal_move], new_visited))


if __name__ == '__main__':
    main()