import sys

def print_board(board):
    """Prints the board with algebraic notation coordinates."""
    print("  a b c d e f g h")
    for r in range(8):
        row_label = str(8 - r)
        row_str = row_label + " "
        for c in range(8):
            # Only print on dark squares (where checkers are played)
            if (r + c) % 2 == 1:
                piece = board[r][c]
                if piece == 0:
                    row_str += ". "
                else:
                    row_str += piece + " "
            else:
                row_str += "  "
        print(row_str)

def algebraic_to_coord(s):
    """Converts algebraic notation (e.g., 'b6') to (row, col) indices."""
    col = ord(s[0]) - ord('a')
    row = 8 - int(s[1])
    return row, col

def initialize_board():
    """Creates the initial 8x8 board setup."""
    board = [[0 for _ in range(8)] for _ in range(8)]
    for r in range(8):
        for c in range(8):
            if (r + c) % 2 == 1:
                # Black pieces (b) at the bottom (rows 5, 6, 7)
                if r > 4:
                    board[r][c] = 'b'
                # White pieces (w) at the top (rows 0, 1, 2)
                elif r < 3:
                    board[r][c] = 'w'
    return board

def get_valid_moves(board, player):
    """Returns a list of valid (start, end) move tuples for the current player."""
    moves = []
    is_black = player == 'b'
    
    for r in range(8):
        for c in range(8):
            piece = board[r][c]
            if piece == 0: continue
            
            # Check if piece belongs to current player
            if is_black and piece not in ['b', 'B']: continue
            if not is_black and piece not in ['w', 'W']: continue
            
            # Determine movement directions based on piece type
            directions = []
            if piece == 'b': # Black men move up (decreasing row index)
                directions = [(-1, -1), (-1, 1)]
            elif piece == 'w': # White men move down (increasing row index)
                directions = [(1, -1), (1, 1)]
            else: # Kings move in all diagonal directions
                directions = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
            
            for dr, dc in directions:
                # Check simple move (distance 1)
                nr, nc = r + dr, c + dc
                if 0 <= nr < 8 and 0 <= nc < 8:
                    if board[nr][nc] == 0:
                        moves.append(((r, c), (nr, nc)))
                
                # Check jump/capture (distance 2)
                jr, jc = r + 2*dr, c + 2*dc
                mr, mc = r + dr, c + dc # Middle square (the piece being jumped)
                
                if 0 <= jr < 8 and 0 <= jc < 8:
                    if board[jr][jc] == 0 and board[mr][mc] != 0:
                        mid_piece = board[mr][mc]
                        is_enemy = False
                        if is_black and mid_piece in ['w', 'W']:
                            is_enemy = True
                        if not is_black and mid_piece in ['b', 'B']:
                            is_enemy = True
                        
                        if is_enemy:
                            moves.append(((r, c), (jr, jc)))
    return moves

def main():
    board = initialize_board()
    turn = 'b' # Black starts first
    
    while True:
        print_board(board)
        
        # Check win condition: No pieces left
        b_pieces = sum(1 for row in board for p in row if p in ['b', 'B'])
        w_pieces = sum(1 for row in board for p in row if p in ['w', 'W'])
        
        if b_pieces == 0:
            print("White wins!")
            return
        if w_pieces == 0:
            print("Black wins!")
            return
            
        # Check win condition: No legal moves
        valid_moves = get_valid_moves(board, turn)
        if not valid_moves:
            winner = "White" if turn == 'b' else "Black"
            print(f"{winner} wins! (No legal moves)")
            return

        player_name = "Black" if turn == 'b' else "White"
        print(f"{player_name}'s turn.")
        
        try:
            inp = input("Move (e.g. b6 c5): ").strip().lower()
            if not inp: continue
            parts = inp.split()
            if len(parts) != 2:
                print("Invalid format. Use 'from to' (e.g., b6 c5)")
                continue
            
            start_str, end_str = parts
            start = algebraic_to_coord(start_str)
            end = algebraic_to_coord(end_str)
            
            # Validate move against generated legal moves
            if (start, end) not in valid_moves:
                print("Illegal move.")
                continue
            
            # Execute move
            sr, sc = start
            er, ec = end
            piece = board[sr][sc]
            board[sr][sc] = 0
            board[er][ec] = piece
            
            # Handle capture (remove jumped piece)
            if abs(sr - er) == 2:
                mr = (sr + er) // 2
                mc = (sc + ec) // 2
                board[mr][mc] = 0
            
            # Handle promotion (Man reaches opposite end)
            if turn == 'b' and er == 0 and piece == 'b':
                board[er][ec] = 'B'
            elif turn == 'w' and er == 7 and piece == 'w':
                board[er][ec] = 'W'
                
            # Switch turn
            turn = 'w' if turn == 'b' else 'b'
            
        except (ValueError, IndexError):
            print("Invalid input. Please use algebraic notation (e.g., a1, h8).")
        except KeyboardInterrupt:
            print("\nGame exited.")
            return

if __name__ == "__main__":
    main()