def print_board(board):
    print("  a b c d e f g h")
    for i, row in enumerate(board):
        print(f"{8-i} " + " ".join(cell if cell != '.' else '.' for cell in row))
    print()

def parse_square(sq):
    if len(sq) != 2 or not sq[0].isalpha() or not sq[1].isdigit():
        return None
    col = ord(sq[0].lower()) - ord('a')
    row = 8 - int(sq[1])
    if 0 <= col <= 7 and 0 <= row <= 7:
        return row, col
    return None

def get_valid_moves(board, player):
    moves = []
    directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]  # All directions for kings
    man_directions = [-1] if player == 'w' else [1]  # Men move forward only
    
    for r in range(8):
        for c in range(8):
            piece = board[r][c]
            if piece.lower() != player:
                continue
            
            is_king = piece.isupper()
            piece_dir = directions if is_king else man_directions
            
            for dr in piece_dir:
                # Check simple move
                nr, nc = r + dr, c + dr
                if 0 <= nr < 8 and 0 <= nc < 8 and board[nr][nc] == '.':
                    moves.append(((r, c), (nr, nc), False))
                
                # Check capture move
                jr, jc = r + 2*dr, c + 2*dr
                if 0 <= jr < 8 and 0 <= jc < 8 and board[jr][jc] == '.':
                    mid_r, mid_c = r + dr, c + dr
                    mid_piece = board[mid_r][mid_c]
                    if mid_piece.lower() != player and mid_piece != '.':
                        moves.append(((r, c), (jr, jc), True, mid_r, mid_c))
    
    return moves

def make_move(board, from_pos, to_pos, capture_info=None):
    r1, c1 = from_pos
    r2, c2 = to_pos
    piece = board[r1][c1]
    board[r1][c1] = '.'
    board[r2][c2] = piece
    
    if capture_info:
        mid_r, mid_c = capture_info
        board[mid_r][mid_c] = '.'
    
    # Check for promotion
    if piece == 'w' and r2 == 0:
        board[r2][c2] = 'W'
    elif piece == 'b' and r2 == 7:
        board[r2][c2] = 'B'

def count_pieces(board, player):
    count = 0
    for row in board:
        for cell in row:
            if cell.lower() == player:
                count += 1
    return count

def has_legal_moves(board, player):
    return len(get_valid_moves(board, player)) > 0

def main():
    # Initialize board
    board = [['.' for _ in range(8)] for _ in range(8)]
    
    # Place black pieces (top 3 rows)
    for row in range(3):
        for col in range(8):
            if (row + col) % 2 == 1:
                board[row][col] = 'b'
    
    # Place white pieces (bottom 3 rows)
    for row in range(5, 8):
        for col in range(8):
            if (row + col) % 2 == 1:
                board[row][col] = 'w'
    
    current_player = 'w'  # White starts
    print("Welcome to English Draughts!")
    print("Enter moves as 'from to' (e.g., b6 c5)")
    print("White pieces: 'w', Black pieces: 'b'")
    print("Kings: 'W', 'B'")
    print()
    
    while True:
        print_board(board)
        
        # Check if current player has pieces
        if count_pieces(board, current_player) == 0:
            winner = 'b' if current_player == 'w' else 'w'
            print(f"Player {current_player.upper()} has no pieces left. Player {winner.upper()} wins!")
            break
        
        # Check if current player has legal moves
        if not has_legal_moves(board, current_player):
            winner = 'b' if current_player == 'w' else 'w'
            print(f"Player {current_player.upper()} has no legal moves. Player {winner.upper()} wins!")
            break
        
        # Get move from player
        while True:
            try:
                move_input = input(f"Player {current_player.upper()}, enter your move (from to): ").strip()
                if move_input.lower() == 'quit':
                    print("Game aborted.")
                    return
                
                parts = move_input.split()
                if len(parts) != 2:
                    print("Invalid format. Please enter 'from to' (e.g., b6 c5)")
                    continue
                
                from_sq, to_sq = parts
                from_pos = parse_square(from_sq)
                to_pos = parse_square(to_sq)
                
                if from_pos is None or to_pos is None:
                    print("Invalid square. Use algebraic notation (a-h, 1-8)")
                    continue
                
                # Get all valid moves for this player
                valid_moves = get_valid_moves(board, current_player)
                
                # Find if this move is valid
                move_found = False
                capture_info = None
                
                for move in valid_moves:
                    if move[0] == from_pos and move[1] == to_pos:
                        move_found = True
                        if len(move) == 4:  # Capture move
                            capture_info = (move[3], move[4])
                        break
                
                if not move_found:
                    print("Invalid move. Check the rules and try again.")
                    continue
                
                # Make the move
                make_move(board, from_pos, to_pos, capture_info)
                break
                
            except Exception as e:
                print(f"Error: {e}. Please try again.")
        
        # Switch player
        current_player = 'b' if current_player == 'w' else 'w'

if __name__ == "__main__":
    main()