#!/usr/bin/env python3

def clear_screen():
    print("\033[H\033[J", end='')

class Checkers:
    def __init__(self):
        # Board is 8x8 list of lists
        # '.' empty, 'w' white man, 'W' white king, 'b' black man, 'B' black king
        self.board = [['.' for _ in range(8)] for _ in range(8)]
        self.init_board()
        self.turn = 'w'  # 'w' white moves first, 'b' black second

    def init_board(self):
        # Place black pieces on rows 0,1,2 on dark squares
        for r in range(3):
            for c in range(8):
                if (r + c) % 2 == 1:
                    self.board[r][c] = 'b'
        # Place white pieces on rows 5,6,7 on dark squares
        for r in range(5,8):
            for c in range(8):
                if (r + c) % 2 == 1:
                    self.board[r][c] = 'w'

    def print_board(self):
        print("  a b c d e f g h")
        for r in range(8):
            row_str = str(8 - r) + ' '
            for c in range(8):
                row_str += self.board[r][c] + ' '
            print(row_str + str(8 - r))
        print("  a b c d e f g h")

    def algebraic_to_coords(self, s):
        # s like 'b6'
        if len(s) != 2:
            return None
        file = s[0]
        rank = s[1]
        if file < 'a' or file > 'h':
            return None
        if rank < '1' or rank > '8':
            return None
        c = ord(file) - ord('a')
        r = 8 - int(rank)
        return (r, c)

    def coords_to_algebraic(self, r, c):
        return chr(c + ord('a')) + str(8 - r)

    def opponent(self, player):
        return 'b' if player == 'w' else 'w'

    def is_king(self, piece):
        return piece in ('W', 'B')

    def is_man(self, piece):
        return piece in ('w', 'b')

    def piece_color(self, piece):
        if piece in ('w', 'W'):
            return 'w'
        elif piece in ('b', 'B'):
            return 'b'
        else:
            return None

    def directions(self, piece):
        # Returns list of (dr, dc) for moves
        # Men move forward only: white up (-1), black down (+1)
        # Kings move all four diagonals
        if self.is_king(piece):
            return [(-1,-1), (-1,1), (1,-1), (1,1)]
        elif piece == 'w':
            return [(-1,-1), (-1,1)]
        elif piece == 'b':
            return [(1,-1), (1,1)]
        else:
            return []

    def can_capture_from(self, r, c):
        piece = self.board[r][c]
        if piece == '.':
            return False
        player = self.piece_color(piece)
        dirs = self.directions(piece)
        for dr, dc in dirs:
            r1 = r + dr
            c1 = c + dc
            r2 = r + 2*dr
            c2 = c + 2*dc
            if 0 <= r2 < 8 and 0 <= c2 < 8 and 0 <= r1 < 8 and 0 <= c1 < 8:
                mid_piece = self.board[r1][c1]
                dest = self.board[r2][c2]
                if dest == '.' and mid_piece != '.' and self.piece_color(mid_piece) == self.opponent(player):
                    return True
        return False

    def any_capture_available(self, player):
        for r in range(8):
            for c in range(8):
                if self.piece_color(self.board[r][c]) == player:
                    if self.can_capture_from(r,c):
                        return True
        return False

    def legal_moves(self, player):
        moves = []
        must_capture = self.any_capture_available(player)
        for r in range(8):
            for c in range(8):
                piece = self.board[r][c]
                if self.piece_color(piece) != player:
                    continue
                dirs = self.directions(piece)
                if must_capture:
                    # Only captures allowed
                    for dr, dc in dirs:
                        r1 = r + dr
                        c1 = c + dc
                        r2 = r + 2*dr
                        c2 = c + 2*dc
                        if 0 <= r2 < 8 and 0 <= c2 < 8 and 0 <= r1 < 8 and 0 <= c1 < 8:
                            mid_piece = self.board[r1][c1]
                            dest = self.board[r2][c2]
                            if dest == '.' and mid_piece != '.' and self.piece_color(mid_piece) == self.opponent(player):
                                moves.append(((r,c),(r2,c2)))
                else:
                    # Normal moves
                    for dr, dc in dirs:
                        r1 = r + dr
                        c1 = c + dc
                        if 0 <= r1 < 8 and 0 <= c1 < 8:
                            if self.board[r1][c1] == '.':
                                moves.append(((r,c),(r1,c1)))
        return moves

    def move_piece(self, fr, fc, tr, tc):
        piece = self.board[fr][fc]
        self.board[fr][fc] = '.'
        self.board[tr][tc] = piece
        # Check promotion
        if piece == 'w' and tr == 0:
            self.board[tr][tc] = 'W'
        elif piece == 'b' and tr == 7:
            self.board[tr][tc] = 'B'

    def perform_move(self, fr, fc, tr, tc):
        # Check if move is a capture
        if abs(tr - fr) == 2 and abs(tc - fc) == 2:
            # Remove captured piece
            mr = (fr + tr)//2
            mc = (fc + tc)//2
            self.board[mr][mc] = '.'
        self.move_piece(fr, fc, tr, tc)

    def has_pieces(self, player):
        for r in range(8):
            for c in range(8):
                if self.piece_color(self.board[r][c]) == player:
                    return True
        return False

    def game_over(self):
        # Game over if player to move has no pieces or no legal moves
        if not self.has_pieces(self.turn):
            return True
        if len(self.legal_moves(self.turn)) == 0:
            return True
        return False

    def winner(self):
        # Called only if game_over is True
        # If current player has no pieces or no moves, opponent wins
        if not self.has_pieces(self.turn):
            return self.opponent(self.turn)
        if len(self.legal_moves(self.turn)) == 0:
            return self.opponent(self.turn)
        return None

    def input_move(self):
        while True:
            s = input(f"{'White' if self.turn=='w' else 'Black'} to move (from to, e.g. b6 c5): ").strip().lower()
            parts = s.split()
            if len(parts) != 2:
                print("Invalid input format. Enter move as: from to (e.g. b6 c5)")
                continue
            from_sq, to_sq = parts
            from_coords = self.algebraic_to_coords(from_sq)
            to_coords = self.algebraic_to_coords(to_sq)
            if from_coords is None or to_coords is None:
                print("Invalid square(s). Use files a-h and ranks 1-8.")
                continue
            fr, fc = from_coords
            tr, tc = to_coords
            piece = self.board[fr][fc]
            if self.piece_color(piece) != self.turn:
                print("You must move your own piece.")
                continue
            legal = self.legal_moves(self.turn)
            if (fr,fc),(tr,tc) not in legal:
                print("Illegal move.")
                continue
            return fr, fc, tr, tc

    def play(self):
        while True:
            clear_screen()
            self.print_board()
            if self.game_over():
                w = self.winner()
                if w == 'w':
                    print("White wins!")
                elif w == 'b':
                    print("Black wins!")
                else:
                    print("Draw!")
                break
            fr, fc, tr, tc = self.input_move()
            self.perform_move(fr, fc, tr, tc)
            self.turn = self.opponent(self.turn)

def main():
    game = Checkers()
    game.play()

if __name__ == "__main__":
    main()