Chess endgame: White to Mate In One

Question

Given an 8x8 grid of letters representing the current state of a game of chess, your program's task is to find a next move for white that results in checkmate (the answer will always be mate in one move).

Input

Input will be on STDIN - 8 lines of 8 characters each. The meanings of each character are as follows:

K/k - king
Q/q - queen
B/b - bishop
N/n - knight
R/r - rook
P/p - pawn
- - empty square

Upper case letters represent white pieces, and lower case represents black. The board will be oriented so that white is playing up from the bottom and black is playing down from the top.

Output

A move for white that results in checkmate, in algebraic notation. You do not need to notate when a piece has been taken, nor do you need to be concerned about disambiguating between two identical pieces which can make the same move.

Sample input

Example 1

Input:

------R-
--p-kp-p
-----n--
--PPK---
p----P-r
B-------
--------
--------

Output:

c6

Example 2

Input:

--b-r--r
ppq-kp-p
-np-pn-B
--------
---N----
--P----P
PP---PP-
R--QRBK-

Output:

Nf5

Example 3

Input:

---r-nr-
-pqb-p-k
pn--p-p-
R-------
--------
-P-B-N-P
-BP--PP-
---QR-K-

Output:

Rh5

You can assume that the solution will not involve castling or en-passant.

This is code-golf - shortest solution wins.

^{(Examples taken from mateinone.com - puzzles 81, 82 and 83)}

Answer 1

Ruby, 589 512 510 499 493 characters

R=0..7
a=->b{o=[];R.map{|r|R.map{|c|v=Hash[?K,[6,7,8,11,13,16,17,18],?R,s=[157,161,163,167],?B,t=[156,158,166,168],?Q,s+t,?N,[1,3,5,9,15,19,21,23],?P,[32,181,183]][z=b[r][c]];v&&v.map{|s|k=2!=l=s/25+1;u=r;v=c;l.times{u+=s/5%5-2;v+=s%5-2;R===u&&R===v||break;t=b[u][v];j=t<?.&&l<8;(j||t=~/[a-z]/&&k)&&o<<=(h=b.map &:swapcase;h[u][v]=h[r][c];h[r][c]=?-;[z+"%c%d"%[97+v,8-u],h.reverse]);j&&(k||r==6)||break}}}};o}
a[$<.map{|l|l}].map{|m,b|a[b].any?{|f,x|a[x].all?{|g,y|y*""=~/K/}}||$><<m[/[^P]+/]}

Input is given via stdin, e.g.:

> ruby mateinone.rb
--------
--------
--------
-k------
b-------
-N-P----
--------
-----K-Q
^Z
Qb7

The output is not just one move that forces a mate in one but every move that does so.

Edit 1: The function e was used only once so I inlined it. Second, the encoding now is based on number 5 instead of 10. And refactoring the cloning of the board saved quite a few chars.

Edit 2: Still not as much improvement as I wanted. Changing the hash from {a=>b,c=>d} to Hash[a,b,c,d]. This costs 4 characters but saves one per key-value pair.

Edit 3: Only minor reductions: inlining M (4 characters), t==?- -> t<?. (2), removing Pawn in algebraic notation at the end (2), replaced puts (3). The program is now less than 500 characters.

Edit 4: It is interesting how much one can still find in such a program. Moved an invariant outside the loop and found another duplicate calculation.