Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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

enter image description here

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!

share|improve this question
1  
I believe this would work just fine as a code golf –  Jan Dvorak Mar 29 at 7:04
3  
Code golf is the better choice. The obvious is always forgotten: I understand that we can submit either a function or a program, and that input/output can be either stdin/stout or parameters/return value. I'm thinking recursion might be useful here for the queen: f(x)... case "Q": {f("B");f("R")} If the function requires any #includes these should be part of the byte count. –  steveverrill Mar 29 at 8:38
4  
The font in that graphic. xD –  Trimsty Mar 29 at 9:07
1  
Do the possible moves have to be separated by spaces or are newlines OK as well? –  Dennis Mar 29 at 22:31
1  
the legal moves for a pawn are more convoluted than any other piece (en passant, diagonal capturing, and the 2-square initial move). so i assume jack also has the castling rules memorized? –  ardnew Mar 31 at 17:07

12 Answers 12

up vote 7 down vote accepted

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!

share|improve this answer
    
Awesome! Nice work =). I'll have to look at it more closely later to see how you got 40 chars shorter than mine. Isn't Golfscript fun? –  Claudiu Apr 3 at 16:56

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
share|improve this answer
    
Nice extracting of string chars with this argument tuple. Too bad it doesn't work anymore in Python 3. –  Evpok Mar 30 at 21:18

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.

share|improve this answer
    
Just curious about the input, is it N4d? Shouldn't it be Nd4 instead? –  devnull Mar 29 at 14:41
    
@devnull sure, that's a typo. should be Nd4. –  Martin Büttner Mar 29 at 14:43
    
Learned a knew function today ChessboardDistance –  swish Mar 30 at 7:14
    
Per the Mathematica/Wolfram Language documentation, "ChessboardDistance[u,v] is equivalent to Max[Abs[u-v]]." Perhaps you can save characters by using the latter form, especially if you replace Abs[u-v] with |u-v|. –  Michael Stern Apr 3 at 21:25
    
@MichaelStern that's exactly what I'm doing in the golfed version ;). And unfortunately vertical bars don't work for Abs in Mathematica, because they denote alternatives in a pattern. –  Martin Büttner Apr 3 at 21:46

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.
share|improve this answer
    
Can you post an ungolfed version too? (if you have one of course) –  swish Mar 30 at 7:21
    
@swish I don't but I don't mind writing that up. –  bazzargh Mar 30 at 7:25
    
@swish done. Hope that makes more sense. Ask away if you need something clarified. –  bazzargh Mar 30 at 7:47
    
Great job! Why do you need add piece to the list [piece,newfile, newrank] if you don't use it in pattern matching, can save you some characters? –  swish Mar 30 at 8:09
    
It's there for output. You'll see I don't pattern match on it in '...each possible move...'. Originally I didn't have this - chess moves don't require it - but then I noticed the question wanted it, and everyone else did it, so it's only fair. –  bazzargh Mar 30 at 8:13

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.

share|improve this answer

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).

share|improve this answer
    
Seems to work well! I hope that someone comes up with a brainf*ck solution too. –  devnull Mar 30 at 7:37

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.

share|improve this answer
    
Welcome to Code Golf! To begin with, you could strip the whitespace in your code. Remember this is code golf, which implies that the shortest code wins. So attempt to reduce the size of your program. –  devnull Mar 29 at 14:37
    
Remember to update the character count too! –  devnull Mar 29 at 14:51
    
@devnull are necessary spaces counted? –  calccrypto Mar 29 at 14:56
1  
One more thing: C can be simplified greatly using the ternary operator ?: and by using the return value of printf. (printf returns the number of characters written, so in this case it is always non-zero.) C(P,c,r){return(0<=c)&(c<8)&(0<r)&(r<9)?printf("%c%c%d ",P,c+'a',r):0;}. A minor edit: there is an extra space in M after the if that you can remove. –  ace Mar 29 at 15:56
1  
Right now, you seem not to be counting any newlines. While some of them can be removed, others cannot. Required newlines should definitely contribute to the byte count. –  Dennis Mar 30 at 6:00

Haskell, 300269 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!)

share|improve this answer
    
You can get rid of syntactic whitespace. See my answer here: codegolf.stackexchange.com/questions/19255/… (to be more specific, you want let{h=d(x!!1)(y!!1);...}) –  bazzargh Mar 30 at 6:25

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.

share|improve this answer

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
share|improve this answer

Hypothetical Haskell, 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.

share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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