18
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ No. I think for the purposes of this question you can assume that the answer will not involve castling or en-passant. I'll update the question. \$\endgroup\$ – Gareth Jul 22 '11 at 10:14
  • \$\begingroup\$ How should we handle positions with more than one mate-in-one? \$\endgroup\$ – Rob Jul 23 '11 at 0:17
  • \$\begingroup\$ @Rob Only one solution is required, so output whichever solution you find first. \$\endgroup\$ – Gareth Jul 23 '11 at 7:00
  • \$\begingroup\$ Is it also safe to assume that the solution doesn't involve promotion? \$\endgroup\$ – Peter Taylor Aug 2 '11 at 9:45
  • \$\begingroup\$ @Peter Yes, I don't want to over-complicate the problem. \$\endgroup\$ – Gareth Aug 2 '11 at 11:58
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ By "not one, but any" do you mean "not necessarily one, but every"? \$\endgroup\$ – Matthew Read Jul 25 '11 at 16:23
  • \$\begingroup\$ @Matthew You're right. I meant "every". \$\endgroup\$ – Howard Jul 25 '11 at 16:47
  • \$\begingroup\$ You can use [*$<] instead of $<.map{|l|l}. \$\endgroup\$ – Lowjacker Aug 7 '11 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.