Mate in one P76591

Statement

thehtml

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.

• 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