# Chess - Find all legal moves (except castling and en passant)

Write the shortest code that calculates all possible (legal) moves of current player from a given FEN string. What is FEN string? (Wikipedia)

• Shortest code wins, language doesn't matter.
• Output moves must obey chess rules of movement except en passant, castling, and pawn promotion.
• Ignore check, checkmate, and stalemate, king cannot be captured situations too.

You can set outputs differently as you want (for example: A2-A4, A2A4, a2a4, a2->a4...)

Test cases:

# INPUT 1:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

# OUTPUT 1

A2-A4, A2-A3, B2-B4, B2-B3, C2-C4, C2-C3, D2-D4, D2-D3, E2-E4, E2-E3,
F2-F4, F2-F3, G2-G4, G2-G3, H2-H4, H2-H3, B1-A3, B1-C3, G1-F3, G1-H3

# INPUT 2

7k/8/8/8/8/8/PP6/Q1q4K w - - 0 1


# OUTPUT 2

A1-B1, A1-C1, A2-A3, A2-A4, B2-B3, B2-B4, H1-H2, H1-G1, H1-G2

• also here is how test case input boards look like: i.sstatic.net/qlbH4.png Mar 7, 2013 at 3:39
• possible duplicate of Play a valid chess move, given a board on stdin Mar 7, 2013 at 13:56
• @ugoren, I considered that, but enumerating all possible moves potentially eliminates some shortcuts. I'm not sure, though, why en passant isn't required: part of the point of FEN is that it includes enough information to make en passant possible. Mar 7, 2013 at 14:09
• @PeterTaylor I wrote that just to reduce the work. I wonder why no one interested in this golf :) Mar 8, 2013 at 21:12
• @golffzz shouldn't your test case input 2 be 7k/8/8/8/8/8/PP6/Q1q4K w - - 0 1 instead of 6pk/6pp/8/8/8/p7/PP4pp/Q2p2pK w - - 0 1 (which among other things, seems to have pawns on the end ranks)? Sep 9, 2014 at 21:38

# C - 391 bytes

Takes input as command line arguments and prints to stdout with the squares labeled from 0 to 63.

OK, I had a few minutes so I tried to delete all the bits relating to the detection of check. I think it is now not very efficient though...

O(x,y){return((x&7)-(y&7))/5;}
B[64],*b=B,J=32,M,L,x,*X,N;
main(int c,char**V){
for(;x=*V[1]++;c=J&2**V[2])
x>56?*b++=x:x>47?b+=x-48:0;
for(;b-->B;)
for(M=-1,N=*b%J^16,*V=strchr("bGInFJOQrAHkAGHIqAGHIpGHIx",*b|J);*b&&*b&J^c&&(M=M<0?*++*V%J:-M,**V<96);)
for(x=b-B,L=N?9^*b&8:1+(x/8==1+c/6);L--*!(O(x,x+M)|O(x>>3,x+M>>3));L=!*X|~*X&J^c&&N|(!*X^M&1&&M<0^!c)?printf("%d-%d ",b-B,x),L*!*X:0)
X=B+(x+=M);}


478 byte check-detecting version

O(x,y){return((x&7)-(y&7))/5;}
B[64],*b=B,c,I,J=32;
main(int C,char**V){
int*D,M,L,t,x,*X,N;
for(;b-B<64;C=c=J&2**V[2])
(t=*V[1]++)>56?*b++=t:t>47?b+=t-48:0;
for(D=b;D-->B;)
for(M=-1,N=*D%J^16,*V=strchr("bGInFJOQrAHkAGHIqAGHIpGHIx",*D|J);*D&&*D&J^C&&(M=M<0?*++*V%J:-M,**V<96);)
for(x=D-B,L=N?9^*D&8:1+(x/8==1+C/6);L--*!(O(x,x+M)|O(x>>3,x+M>>3));L=!*X|~*X&J^C&&N|(!*X^M&1&&M<0^!C)?c^C?I|=*X%J==11:(*X=*D,*D=I=0,main(C^J,V+1),*D=*X,I||printf("%d-%d ",D-B,x)),L*!(*X=t):0)
X=B+(x+=M),t=*X;}

• This is amazing, but does not correspond to the question: "Ignore check, checkmate, and stalemate, king cannot be captured situations too." Oct 13, 2014 at 14:58
• @edc65 I don't agree with your interpretation of these unfortunately incoherent instructions. It says "Output moves must obey chess rules of movement except en passant, castling, and pawn promotion." Moving into check does not appear in the bolded list of rules to ignore. I take the third bullet point as a note that you do not need to detect these situations and reflect them in any way in the output (e.g. the convention of writing '+' after a check). Also, the second test case 2 was correct as originally written, given one ignores pawn promotion as specified (but gives no insight on check). Oct 14, 2014 at 6:07
• The second test case (input) was invalid having a black pawn on rank 8, and different from the image posted as a comment by OP (also here is how test case input boards look like). Given the position in the image, the original test case output was correct according to the rules. Oct 14, 2014 at 6:19
• Oh great, the real spec is in the comments? Ugh, what a poor question. Oct 14, 2014 at 6:41
• The clear winner Oct 16, 2014 at 19:39

## Java 1455

String q(String f){int[][]b=new int[8][8];int i=0,j=0,k,l,m,n,c;HashSet<String>h=new HashSet<String>();while((c=f.charAt(i))>32){if(c>48&c<57)j+=c-49;if(c==47)j--;if(c>56)b[j%8][j/8]=c;i++;j++;}boolean w=f.charAt(++i)>99;for(i=0;i<8;i++)for(j=0;j<8;j++)if((c=b[i][j])<91?w&c>0:!w){switch(c%32){case 14:for(k=0;k<8;k++){l=(k/4+1)*(k%2*2-1)+i;m=(2-k/4)*(k%4/2*2-1)+j;if(b(l,m)&&(w&b[l][m]%91<40|!w&b[l][m]<91))h.add(h(i,j,l,m));}break;case 11:for(k=0;k<8;k++){l=i+(k==4?1:k/3-1);m=j+(k==4?1:k%3-1);if(b(l,m)&&(w&b[l][m]%91<40|!w&b[l][m]<91))h.add(h(i,j,l,m));}break;case 17:for(k=0;k<8;k++){for(n=1;n<9;n++){l=i+n*(k==4?1:k/3-1);m=j+n*(k==4?1:k%3-1);if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;case 2:for(k=0;k<4;k++){for(n=1;n<9;n++){l=i+n*(k/2*2-1);m=j+n*(k%2*2-1);if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;case 18:for(k=0;k<4;k++){for(n=1;n<9;n++){l=i+n*(k/2*(k%2*2-1));m=j+n*((1-k/2)*(k%2*-2+1));if(b(l,m)){c=b[l][m];if(w&c%91<40|!w&c<91)h.add(h(i,j,l,m));if(c>0)break;}else break;}}break;default:m=w?-1:1;if(b[i][j+m]<1){h.add(h(i,j,i,j+m));if(b[i][j+2*m]<1&j==(w?6:1))h.add(h(i,j,i,j+2*m));}for(l=-1;i+l<8&i+l>=0&l<2;l+=2){c=b[i+l][j+m];if(c>0&(c<91?!w:w))h.add(h(i,j,i+l,j+m));}}}return h.toString();}boolean b(int l,int m){return m>=0&m<8&l>=0&l<8;}String h(int i,int j,int l,int m){return""+g(i)+(8-j)+g(l)+(8-m);}char g(int i){return(char)(i+65);}


# Python 553 649678

b,Q=raw_input(),range;R=Q(8);D="w"in b
for i in Q(9):b=b.replace(i,"_"*i)
if D:b=b.swapcase()
def X(h,v,c):
h+=x;v+=y
if c and h|v in R and"a">b[v*9+h]:print chr(65+x)+8-y+chr(65+h)+8-v;return"_"==b[v*9+h]
for y in R:
for x in R:
z=y*9+x;p=b[z];N=p=="n";j=[p in"qrk"]*4+[p in"qbk"]*4
if"p"==p:j[D]=k=(1,-1)[D];X(1,k,b[z+10*k]<"_");X(-1,k,b[z+8*k]<"_")
for i in Q(1,(2,(y==(1,6)[D])+2,8)["kp".find(p)]):
for k in R:j[k]=X((0,0,-i,i,-i,i,-i,i)[k],(i,-i,0,0,-i,-i,i,i)[k],j[k])
for v,h in((2,1),(1,2)):X(v,h,N);X(-v,-h,N);X(-v,h,N);X(v,-h,N)


Two-space indent is tab char, which saves 5 bytes.

It occurs to me that you can likely make it evaluate reasonable moves to a decent ply and keep it under 1024 bytes :) I started looking through other questions, but there doesn't seem to be a codegolf chess engine question...

• Well done for resurrecting this question! (I think I might put a bounty on it just to see what happens.) Your answer is looking good, but it misses B1C3 and H2H3 in the first example shown in the question. Oct 10, 2014 at 15:22
• Sorry,not H2H3, I meant G1H3 — in other words, your white knights are only turning left. Oct 10, 2014 at 15:39
• It'll have to wait until I am on a pc, but this is an easy bug and I can see lots of ways to shorten it too. Hope there are other entries.
– Will
Oct 10, 2014 at 20:38
• @squeamishossifrage fixed :)
– Will
Oct 11, 2014 at 7:12

# Python 638 637 (482?) bytes

exec"""p=raw_input()
for x in"12345678":p=p.replace(x,"~"*int(x))
b=map(ord,"#"*21+p[:71].replace("/","##")+"#"*21)
d,e=-10,126
if not"w"in p:b,d=[x^32*(64<x<e)for x in b],10
B=[-9,9,-11,11]
R=[-1,1,-d,d]
Q=B+R
c=Zx:chr(96+x%10)+chr(58-x/10)
for x,p in enumerate(b):
def O(y):
if 111<b[y]:print c(x)+c(y)
s=ZL:[O(x+X)for X in L];m=ZL,z=x:L&(O(z+L[0]),m(L,z+L[0])if e==b[z+L[0]]else m(L[1:]))
if p==80:e==b[x+d]&(O(x+d)or e==b[x+d*2]&35==b[x-d*2]&O(x+d*2)),111<b[x+d-1]<e&O(x+d-1),111<b[x+d+1]<e&O(x+d+1)
p==75&s(Q),p==78&s([-12,12,-8,8,-21,21,-19,19]),p==82&m(R),p==66&m(B),p==81&m(Q)""".replace("Z","lambda ").replace("&"," and ")


Note: after def O(y): there is a newline and a tab char before if

Note: by using zlib module it's possible to get a valid Python source code of 482 bytes by simply compressing the real source:

#encoding=koi8-r
import zlib
exec zlib.decompress("x°MRKkЦ0>╞~┘Pы Eё╜Е4▌Ц█.9Br*1зБ┤B╠#°■╙=Лoъ╠M⌡│╬г0█\\pcл⌡╝x9╣ЧМф9^:Х╘e:·=м⌠Eй2oЭ╞нЫsQ9─ЩeсS{ЦAR ╕ПЭруюь4жрГыBшОhЖхпyB▌╬ 58ёt:NхИHшк█╫ЁSK}VBmРПgOyР╢\n+'╬Z║╔▒╣иу√═╢╜-ы#G╙├з▓²Yк=╘л!dуkг≈┴?u$dOФ╘\n▐HфАюВ9]Шж╦╝╦9^┼▄пзИ√ Э│mi╜WeЧa3ъА╗╢бae┘.║WsьdЫ√Ы<ТВэГзьъ ЙПiB╤≥П-Ъ■⌡<╡▌Б┬1╚3╕лGjщЫЙ(з╧н,>$Eш⌠FыdmШ<x,Р╔Mc;≥м╒2DLc!Л≥рvЕFCИЪtyв%Н║╞╤≤O╝|'═┤)B|н*┘T╛▐рKпK;╔Я╓АШ&  бУ╗j└;│И╬Ж╝Щ\\4e]P&НРeZ╢5┼ДГt╚У")


# JavaScript (E6) 481 492 550

Edit Fixed a nasty bug in knight moving. A lot of work to keep the byte count the same.

B=f=>
[for(c of(o=b='',f=f.split(w=' '))[0])b+=-c?w.repeat(c):c<'0'?z=10:c]+
[...b].map((c,p)=>
(K=d=>(d=b[p+d])==w?0:d>'a'?m:d>'A'?-m:9)(0)-1||(
t='pPkKnNrRQqBb'.search(c),
O=d=>K(d)<1?o+=w+P(p)+P(p+d):0,
S=(d,s=0)=>O(d*++s)&&!K(d*s)&&S(d,s),
//o+='\n'+P(p)+' '+c, // Uncomment to display pieces list
t<2?[for(i of[~(s=t<1?z:-z),1-s])~K(i)||O(i)]+!K(s)&&O(s)&&(p/z|0)==t*5+1&!K(s+=s)&&O(s)
:t<6?[for(i of t<4?[1,9,z,11]:[12,8,21,19])O(i)+O(-i)]
:[for(i of[t>7&&9,t>7&&11,t<z,t<z&&z])S(i)+S(-i)]
)
,m=f[1]<'w'?1:-1,
//console.log(','+([...b]+',').replace(/1,0/g,'\n')), // Uncomment to display chessboard
P=p=>'ABCDEFGH'[p%z]+(9+~p/z|0))&&o


Less Golfed

B=f=>(
o=b='',[for(c of f)b+=-c?'.'.repeat(c):c],
m=(w=b[72]=='w')?1:2,n=3-m,
t=0,
P=p=>'ABCDEFGH'[p%9]+(9+~p/9|0),
b=b.slice(0,71),
// console.log(b.replace(/\//g,'\n')), // Uncomment to display chessboard

[...b].map((c,p)=>{
r=p/9|0
K=k=>(k=b[k])=='.'?0:k>'a'?m:k>'A'?n:9
J=d=>K(p+d)<2,
O=d=>J(d)?o+=' '+P(p)+P(p+d):0,
S=(s,d)=>O(d*++s)&&!K(p+d*s)?S(s,d):0;

if(K(p)==2){
// o+='\n'+P(p)+ ' '+c; // Uncomment to display pieces list
if (c=='P')
{
(f=!K(p-9))&&O(-9),
f&r==6&&!K(p-18)&&O(-18),
[for(i of[10,8])K(p-i)==1&&O(-i)]
}
else if (c=='p')
{
(f=!K(p+9))&&O(+9),
f&r==1&&!K(p+18)&&O(+18),
[for(i of[10,8])K(p+i)==1&&O(+i)]
}
else if (c=='K' |c=='k')
[for(i of[1,8,9,10])O(i)+O(-i)]
else if (c=='N' | c=='n')
[for(i of[11,7,19,17])O(i)+O(-i)]
else
{
if (c!='r' & c!='R')
[for(i of[10,8])S(0,i)+S(0,-i)]
if (c!='b' & c!='B')
[for(i of[9,1])S(0,i)+S(0,-i)]
}
}
}),
o
)


Test in FireFox/FireBug console

B("7k/8/8/8/8/1P6/P7/Q1q4K w - - 0 1")


Output

B3B4 A2A3 A2A4 A1B2 A1C3 A1D4 A1E5 A1F6 A1G7 A1H8 A1B1 A1C1 H1G1 H1H2 H1G2


## JAVA 631599 594

Fixed a bug in the 599-bytes version (thank you Jack for pointing this out!) and shortened the code to 594-bytes.

class F{
public static void main(String[]A){int p=0,i=8,u,v,d,z[]={0,1,-1,2,1,0,1};String f=A[0],S[]="p,n,rqk,bqk,aA,PNBRQK,aAPNBRQK".split(",");
for(;i>0;)f=f.replace(""+i,"a"+(--i==0?"":i));
for(;p<448;p++)
for(int k=p%7,w=A[1].equals("w")?32:0,c=f.charAt(p/7%8+p/56*9),a=z[k],b=k==4?2:1,q=0;S[(k/2-1|k-1)/2].indexOf(c+w)>=0&&q++<(k<3?1:4);i=a,a=b,b=-i){
for(i=1,d=97;d==97&&((u=p/7%8+i*a)|(v=p/56+i*b*(1-w/16)))>=0&&(u|v)<8&&i<(k>4?(c=='K'||c=='k')?2:9:(k<1&&p/56==w/6+1?3:2))&&S[61/(61^(k*k-2))+5].indexOf((d=f.charAt(u+9*v))-w)>=0;i++)System.out.printf("%c%d%c%d ",65+p/7%8,8-p/56,65+u,8-v);}}}


Compile: javac F.java
Run: java F 6pk/6pp/8/8/8/p7/PP4pp/Q2p2pK w - - 0 1
Output: B2B3 B2B4 B2A3 A1B1 A1C1 A1D1 H1H2 H1G1 H1G2

• For 3Q4/p4r1k/P4pp1/4P3/5n2/3P4/4BbbP/RN3KN1 w - - 0 0 I'm not seeing moves F1F2 or F1G2 is the king able to capture?
– Jack
Feb 3, 2017 at 18:07
• Thank you for pointing this out. You are right. This published version is over optimized :( Feb 24, 2017 at 11:47
• So I have to fall back to my 631 byte long solution. Feb 24, 2017 at 12:13
• 573 bytes Dec 18, 2019 at 19:37