Mate in one P76591


Statement
 

pdf   zip

html

Given several chess positions, tell if white can checkmate in one movement. The given positions always follow these properties:

  • It is white’s turn.
  • Black has only the king.
  • White does not have any pawns.
  • White cannot castle.

Please remember these rules:

  • A king can never move into an attacked position.
  • In particular, both kings cannot be in adjacent cells.
  • A king can eat an adjacent enemy piece if it is not defended by any other piece.
  • A position is checkmate if the king is threatened and it has no valid movement.
  • A king can checkmate by moving, if by this another piece attacks the enemy king.

Input

Input consists of several cases. Each case begins with the position of the black king, followed by the number n of white pieces (between 2 and 16), followed by the position of the white pieces. Positions are codified with the kind of piece (‘K’ for king, ‘Q’ for queen, ‘B’ for bishop, ‘N’ for knight, ‘R’ for rook), followed by the column (between ‘a’ and ‘h’), followed by the row (between 1 and 8). There are no two pieces on the same cell, and no piece is threatening the black king.

Output

For every case, print the only movement that checkmates the black king: the kind of piece, and the position to move to. If it is impossible to checkmate in one, print “NO”. If there is more than one movement that checkmates in one, print “>1”.

Public test cases
  • Input

    Ka4
    3 Rb7 Rg1 Kh8
    Kg1
    2 Re8 Kg3
    Kg1
    2 Re8 Kf3
    Ka1
    2 Kc1 Rh1
    Ke8
    3 Ra7 Rh7 Ke6
    Kh5
    3 Kg3 Ra4 Rg7
    Ka1
    3 Rh2 Ke1 Rh1
    Ka1
    3 Qf8 Qe7 Kh1
    Ka1
    3 Qg8 Qf7 Kh1
    Kh1
    2 Qf8 Kh3
    Kh1
    2 Qf6 Kh3
    Ka8
    4 Ba7 Bb8 Bf1 Kh1
    Kd4
    5 Bb1 Ba2 Bh6 Bf8 Ka1
    Kd4
    6 Bb1 Ba2 Bh6 Bf8 Ka1 Be1
    Kd4
    6 Bb1 Ba2 Bh6 Bf8 Kb2 Be1
    Ka8
    4 Nc6 Nc5 Ne8 Kh1
    Kb1
    4 Ka3 Na4 Nb3 Nb4
    Kb1
    5 Ka3 Na4 Nb3 Nb4 Nb5
    Ke3
    3 Qd5 Kg3 Ra8
    Ka7
    5 Ng1 Kc4 Bh5 Nc1 Bf6
    Kh3
    7 Bb8 Ne3 Ng7 Qc3 Nb7 Ng2 Kb2
    Kh5
    9 Re8 Ng6 Ng4 Qg1 Kf7 Qc2 Qd1 Bf6 Qg2
    

    Output

    Ra1
    Re1
    NO
    NO
    >1
    Rh4
    NO
    NO
    Qa2
    Qf1
    >1
    Bg2
    NO
    NO
    Bc3
    Nc7
    Nc3
    >1
    Re8
    NO
    Qc8
    >1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Semifinal
    Date
    2012-06-30