Tell me the moves

Question

Jack and Jane decided to play a game of chess to while away time. Unfortunately, Jack is rather bad at visualizing. He finds it tough to figure the moves possible for a given piece other than a pawn, of course!

Your challenge is to help find Jack the possible options for a given piece (other than a pawn).

In case one has forgotten, the various pieces are denoted by:

• K: King
• Q: Queen
• N: Knight
• B: Bishop
• R: Rook

As an example, in the following image the Knight is located at d4 and can move to c2, b3, b5, c6, e6, f5, f3, e2. For a given input:

Nd4

you would produce:

Nc2 Nb3 Nb5 Nc6 Ne6 Nf5 Nf3 Ne2

Rules:

• The order of the output doesn't matter as long as all the possible moves are listed
• The possible moves can be separated by whitespaces, newlines or any other delimiter
• The input can be passed to the program as a parameter or via STDIN
• Whitespace in the program shall be counted, so make optimum use of it

This is code golf. (Please avoid making use of any tools/utilities specifically designed for the purpose.) The shortest answer wins!

Answer 1

GolfScript, 94 93 characters

My first ever GolfScript program! This took me many an hour of fumbling around not really knowing what I was doing, but I persisted and I think I managed to learn the language basics and golf it fairly well.

Fully golfed:

{}/8,{97+.3$-.*:>8,{49+.4$-.*:^2$+.[3<>^*4=>^=>^*!.2$|]"KNBRQ"8$?=*{[5$3$@]""+p}{;}if}/;;}/];

Commented and nicer source:

{}/              # tIn fIn rIn
8,{97+           #             fTst
  .3$-.*:>       #                  fDif^2 : >
  8,{49+         #                         rTst 
    .4$-.*:^     #                              rDif^2 : ^
    2$+.         #                                     ^>+
    [3<          # These    #                              [validK
     >^*4=       # checks   #                                      validN
     >^=         # do not   #                                             validB
     >^*!        # account  #                                                    validR
     .2$|]       # for null #                                                           validQ]
    "KNBRQ"8$?=  # move;    #                          valid
    *            # * does.  #                          validNotNull
    {[5$3$@]""+p}{;}if  # print? #  fDif^2
  }/;;           #        rIn
}/];

It may look like Claudiu's answer, which is because I referenced his answer, as well as my (unsubmitted) C solution, while making mine. He provided a good specimen of a (relatively) complex, working GolfScript program, and it helped me learn a lot about the language. So thanks, Claudiu!

Being new to GolfScript still, if you guys have any feedback, I'd appreciate hearing it!

Answer 2

Python, 217 212 220 217 213 characters

Tied the 213-byte Mathematica solution

R=range(8)
def f((p,x,y)):
 for a in R:
    for b in R:
     A,B=abs(a-ord(x)+97),abs(b-ord(y)+49);C=max(A,B);r=(A+B==3and C<3,C<2,A*B<1,A==B,0)
     if(r['NKRBQ'.index(p)],any(r[1:]))[p=='Q']*C:print p+chr(a+97)+chr(b+49)

I started off by generating all valid moves but that grew too large so the approach is quite similar to the Mathematica one.

>>> f("Nd4")
Nb3
Nb5
Nc2
Nc6
Ne2
Ne6
Nf3
Nf5
>>> f("Qa1")
Qa2
Qa3
Qa4
Qa5
Qa6
Qa7
Qa8
Qb1
Qb2
Qc1
Qc3
Qd1
Qd4
Qe1
Qe5
Qf1
Qf6
Qg1
Qg7
Qh1
Qh8

Answer 3

Mathematica, 278 272 264 260 215 213 characters

f=(FromCharacterCode@Flatten[Table[c=Abs[#2-x];d=Abs[#3-y];b=c==d;r=#2==x||#3==y;If[Switch[#-75,0,c~Max~d<2,-9,b,7,r,6,b||r,3,!r&&c+d==3],{p,x,y},##&[]],{x,97,104},{y,49,56}]&@@ToCharacterCode@#,1]~DeleteCases~#)&

Ungolfed version:

f[pos_] := (
  {piece, u, v} = ToCharacterCode@pos;
  board = Flatten[Table[{piece, i + 96, j + 48}, {i, 8}, {j, 8}], 1];
  DeleteCases[
    FromCharacterCode[
      Cases[board, {_, x_, y_} /; Switch[p,
        75, (* K *)
        ChessboardDistance[{x, y}, {u, v}] < 2,
        66, (* B *)
        Abs[u - x] == Abs[v - y],
        82, (* R *)
        u == x || v == y,
        81, (* Q *)
        Abs[u - x] == Abs[v - y] || u == x || v == y,
        78, (* N *)
        u != x && v != y && ManhattanDistance[{x, y}, {u, v}] == 3
        ]
      ]
    ], 
    pos (* remove the input position *)
  ]
)&

Example usage:

f["Nd4"]
> {"Nb3", "Nb5", "Nc2", "Nc6", "Ne2", "Ne6", "Nf3", "Nf5"}

The ungolfed version creates a full board, and then selects correct positions with Cases, whereas the golfed version drops invalid moves immediately in the Table command by issuing ##&[], which simply vanishes.

Answer 4

Haskell 225 220 208 205 200 182

f=fromEnum
m[p,a,b]=[[p,c,r]|c<-"abcdefgh",r<-"12345678",let{s=abs$f a-f c;t=abs$f b-f r;g"K"=s<2&&t<2;g"Q"=g"B"||g"R";g"N"=s+t==3&&(s-t)^2<2;g"B"=s==t;g"R"=s<1||t<1}in s+t>0&&g[p]]

It's going to be difficult to touch Mathematica when that has chess moves built in :rollseyes: (well played m.buettner) I take it all back. Beating Mathematica by 31!

Latest edit: replaced case with a function, inlined filter into comprehension, to beat the entry in R ;)

usage:

ghci> m "Nd4"
["Nb3","Nb5","Nc2","Nc6","Ne2","Ne6","Nf3","Nf5"]

Ungolfed (corresponds to 208 char version before 'u' was inlined):

f=fromEnum -- fromEnum is 'ord' but for all enum types,
           -- and it's in the prelude, so you don't need an extra import.
u piece dx dy= -- piece is the character eg 'K', dx/dy are absolute so >=0.
  dx+dy > 0 && -- the piece must move.
  case piece of
    'K'->dx<2&&dy<2         -- '<2' works because we already checked dx+dy>0
    'Q'->dx<1||dy<1||dx==dy -- rook or bishop move. see below.
    'N'->dx+dy == 3 &&      -- either 2+1 or 3+0. Exclude the other...
         (dx-dy)^2 < 2      -- 1^2 or 3^2, so valid move is '<2', ie '==1'
    'B'->dx==dy             -- if dx==dy, dx/=0 - we checked that. 
                            -- other moves with dx==dy are along diagonal
    _->dx<1||dy<1           -- use _ not 'R' to save space, default case is
                            -- the rook. '<1' saves chars over '==0'.
                            -- Again, dx==dy==0 edge case is excluded.
m[piece,file,rank]=       -- the move for a piece. 'parse' by pattern match.
 filter(                    -- filter...
  \[_,newfile,newrank]->    -- ...each possible move...
    u piece                 -- ...by, as everyone noticed, converting char..
      (abs$f file-f newfile) -- differences to absolute dx, dy differences,..
      (abs$f rank-f newrank)) -- and then using special routines per piece.
    [[piece,newfile, newrank] -- the output format requires these 3 things.
      |newfile<-"abcdefgh",newrank<-"12345678"] -- and this just generates moves.

Answer 5

Bash, 238

B={19..133..19}\ {21..147..21};K=1\ {19..21};N='18 22 39 41';R={1..7}\ {2..14..2}0;Q=$B\ $R
a=${1%??};b=$[20#${1:1}-200];c=`eval{,} echo '$'$a`;d=({a..h})
for i in $c -${c// / -};do echo $a${d[$[(i+=b)/20]]}$[i%20];done|grep '[a-h][1-8]$'

How it works

• The idea is to represent every field on the board by a numeric value, taking its coordinates as a base-20 number and subtracting 200. This way, a1 becomes 20 * 10 + 1 - 200 = 1, h8 becomes 20 * 17 + 8 - 200 = 148, etc.

  Now, the possible moves of the Bishop can be represented by (positive or negative) multiples of 19 – same amount of steps up (+20) and to the left (-1) – or 21 – same amount of steps up (+20) and to the right (+1).

  The figure's placement after the move is simply the sum of its original position and the movement. After adding those numbers, we have to check if their sum corresponds to a valid field on the board.

  Since the base (20) is more than twice as big as the highest possible number (8), the sum cannot wrap around the board, e.g., moving Bh1 seven steps to the right and up will result in an invalid board position.

• The line

  B={19..133..19}\ {21..147..21};K=1\ {19..21};N='18 22 39 41';R={1..7}\ {2..14..2}0;Q=$B\ $R
  

  enumerates all possible moves of the pieces that are represented by positive numbers.

• The commands

  a=${1%??};b=$[20#${1:1}-200];c=`eval{,} echo '$'$a`;d=({a..h})
  

  stores the piece's identifier in variable a, the original position's numeric representation in b and the letters a to h in the array d.

  After brace expansion, eval{,} echo '$'$a becomes eval eval echo '$'$a (doubly evil), which evaluates to, e.g., eval echo $K, which evaluates to echo 1 19 20 21.

• for i in $c -${c// / -};do …; done loops over all possible movements and their negative counterparts.

• echo $a${d[$[(i+=b)/20]]}$[i%20] gives the final position after the movement.

• grep '[a-h][1-8]$' makes sure that we have a valid board position.

Answer 6

Golfscript, 144 135 characters

Instead of continuing to try golfing my Python solution, I translated it into Golfscript:

{}/49-:y;97-:x;:N;8,{.x-abs:A
8,{.y-abs:B@[\]$1=:C[B
A+3=\3<&2C>B
A*1<B
A=]81N={(;{|}*}{"NKRB"N?=}if
C*{[N
2$97+@49+]''+p}{;}if
A}/;;}/

Straightforward translation without much golfing so it can most likely be whittled away further. Takes input from stdin without a newline, try it here (1st two lines are to mimic stdin).

Answer 7

C 634 632 629 625 600 chars

#define F for(;i<4;i++){
#define B ;}break;
#define O x=X,y=Y,
P,X,Y,c,r,x,y,i=0, N[8][2]={{-2,1},{-1,2},{1,2},{2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}},S[4][2]={{1,0},{0,1},{-1,0},{0,-1}},D[4][2]={{-1,1},{-1,-1},{1,1},{1,-1}};
C(){return((0<=c)&(c<8)&(0<r)&(r<9))?printf("%c%c%d ",P,c+'a',r):0;}
M(int*m){c=m[0]+x,r=m[1]+y;C()?x=c,y=r,M(m):0;}
main(int a,char**v){char*p=v[1];P=*p,X=p[1]-97,Y=p[2]-48; switch(P){case 75:F c=S[i][1]+X,r=S[i][0]+Y,C(),c=D[i][1]+X,r=D[i][0]+Y,C()B case 81:F O M(D[i]),O M(S[i])B case 78:for(;i<8;i++){c=N[i][1]+X,r=N[i][0]+Y,C()B case 66:F O M(D[i])B case 82:F O M(S[i])B}}

Any suggestions on how to improve this? This is my first time submitting an answer.

Answer 8

Haskell, 300 269 chars

Thanks to bazzargh for help with losing 31 characters...

import Data.Char
f x=filter(x#)[x!!0:y|y<-[v:[w]|v<-"abcdefgh",w<-"12345678"],y/=tail x]
a%b=abs(ord a-ord b)
x#y=let{h=(x!!1)%(y!!1);v=(x!!2)%(y!!2);m=max h v;n=min h v}in case(x!!0)of{'N'->m==2&&n==1;'K'->m==1;'B'->h==v;'R'->n==0;'Q'->('R':tail x)#y||('B':tail x)#y}

Same algorithm as the Mathematica version. Sample output from ghci:

*Main> f "Nd4"
["Nb3","Nb5","Nc2","Nc6","Ne2","Ne6","Nf3","Nf5"]
*Main> f "Ni9"
["Ng8","Nh7"]

(You didn't ask for sanity checking!)

Answer 9

Haskell , 446 chars

import Data.Char
a=[-2,-1,1,2]
b=[-1,1]
d=[1..8]
e=[-8..8]
g=[-1..1]
h 'N' c r=[(c+x,r+y)|x<-a,y<-a,3==(sum$map abs[x, y])]
h 'B' c r=[(c+x*z,r+y*z)|x<-b,y<-b,z<-d]
h 'R' c r=[(c+x,r)|x<-e]++[(c,r+y)|y<-e]
h 'Q' c r=h 'B' c r++h 'R' c r
h 'K' c r=[(c+x,r+y)|x<-g,y<-g]
l s=ord s-96
m n=chr$n+96
k ch (c,r)=ch:m c:[intToDigit r]
f (x,y)=all(`elem`[1..8])[x, y]
i n c r=map(k n).filter(/=(c,r)).filter f$h n c r
j s=i(s!!0)(l$s!!1)(digitToInt$s!!2)

Called using the j function

j "Nd4"

I haven't worked with Haskell in a few months, so it didn't end up being as short as most of the other solutions, but I'm sure there are some optimizations to made, mainly with h. I might shorten it in a bit.

Answer 10

q & k [311 262 chars]

There is a potential of reducing some more characters. I will be reducing it in next iteration.

k)o:{n:#m:&(#x)##y;((),x)[m],'n#y}

k)a:`$"c"$(o/)c:+(97;49)+/:!8

k)r:{{|x@<x}'?,/{o[x]y}'[x](|"c"$c)}
k)k:{"c"$(6h$x)+/:(o/)2 3#-1 0 1}
k)n:{"c"$(6h$x)+/:(|:'t),t:o[-1 1;2 2]}
k)b:{"c"$(6h$x)+/:(n,'n),n,'|n:-8+!17}
k)q:{,/(r;b)@\:x}

d:{(`$("rknbq"!(r;k;n;b;q))[x]y)except`$y}
g:{a inter d[x 0]@1_x}

Usage

Rook

g"ra1"
`a2`a3`a4`a5`a6`a7`a8`b1`c1`d1`e1`f1`g1`h1

King

g"ka1"
`a2`b1`b2

Knight

g"na1"
`b3`c2

Bishop

g"ba1"
`b2`c3`d4`e5`f6`g7`h8

Queen

g"qa1"
`a2`a3`a4`a5`a6`a7`a8`b1`b2`c1`c3`d1`d4`e1`e5`f1`f6`g1`g7`h1`h8

Answer 11

Haskell (hypothetical), 248 chars

import Data.Char
f x=filter(o x)[x!!0:y|y<-[v:[w]|v<-"abcdefgh",w<-"12345678"],y/=tail x]
d a b=abs(ord a-ord b)
h x y=(c*(d(x!!1)(y!!1))-(d(x!!2)(y!!2)))+200*c
 where c=d (x!!0)'A'
o x y=elem(chr(h x y))"ਲ਼ੁߏߚߙÈേെ൅ൄൃ൙൪ൻඌඝථ඿౿౾౽౼౻౺౹ಐಏಠಞರಭೀ಼೐ೋೠ೚೰೩"

Unfortunately, every Haskell compiler I can get my hands on right now has problems with Unicode string literals. Here's the (longer) version that actually works:

import Data.Char
f x=filter(o x)[x!!0:y|y<-[v:[w]|v<-"abcdefgh",w<-"12345678"],y/=tail x]
d a b=abs(ord a-ord b)
h x y=(c*(d(x!!1)(y!!1))-(d(x!!2)(y!!2)))+200*c
 where c=d (x!!0)'A'
o x y=elem(chr(h x y))"\2611\2625\1999\2010\2009\200\3399\3398\3397\3396\3395\3394\3393\3417\3434\3451\3468\3485\3502\3519\3199\3198\3197\3196\3195\3194\3193\3216\3215\3232\3230\3248\3245\3264\3260\3280\3275\3296\3290\3312\3305"

The definition h x y=... is a hash function; valid moves will hash to character numbers that are in the 41-character string. This gets rid of the need for a "case" statement or equivalent.

I'm not planning to work further on this right now. It would be fun to see if someone can use a hash function in a more concise language to make a shorter solution.

Answer 12

R, 203 chars

f=function(p,x,y){x=which((l=letters)==x);X=rep(1:8,8);Y=rep(1:8,rep(8,8));A=abs(X-x);L=abs(Y-y);B=A==L;R=!A|!L;i=switch(p,N=A+L==3&A&L,R=R,B=B,Q=R|B,K=(R|B)&A<2&L<2)&A+L>0;paste(p,l[X[i]],Y[i],sep="")}

Ungolfed version:

f = function(p,x,y) {
  x = which(letters == x)  # Gives index between 1 and 8.
  X = rep(1:8, 8)          # 1,2,...,7,8,1,2,.... (8x8).
  Y = rep(1:8, rep(8,8))   # 1,1,...2,2,.....,8,8 (8x8).
  dx = abs(X-x)
  dy = abs(Y-y)
  B = (dx == dy)           # Bishop solutions
  R = (!dx | !dy)          # Rock solutions
  i = switch(p,
             N=dx+dy==3 & dx & dx,  # Sum of dist. is 3, dx and dy must be <> 0.
             R=R, 
             B=B, 
             Q=R|B,                 # Queen is merge of rock and bishop.
             K=(R|B) & dx<2 & dy<2  # King's distance is < 2.
             ) & (dx+dy > 0)        # Exclude start field.

  paste(p, letters[X[i]], Y[i], sep="")
}

Usage:

> f('N', 'a', 3)
[1] "Nb1" "Nc2" "Nc4" "Nb5"

The solution is even good readable. However I added some parentheses and comments for readers unfamiliar with R code (on the ungolfed version).