Xadrez - Encontre todos os movimentos legais (exceto castling e en passant)

19

Escreva o código mais curto que calcule todos os movimentos (legais) possíveis do jogador atual a partir de uma determinada string FEN. O que é uma string FEN? (Wikipedia)

  • O código mais curto vence, o idioma não importa.
  • Movimentos de saída devem obedecer regras de xadrez de movimento , exceto en passant , roque, e promoção do peão.
  • Ignorar cheque, xeque-mate e impasse, o rei também não pode ser capturado.

Você pode definir saídas de forma diferente como você deseja (por exemplo: A2-A4, A2A4, a2a4, a2->a4...)

Casos de teste:

# ENTRADA 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
# ENTRADA 2

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

# SAÍDA 2

A1-B1, A1-C1, A2-A3, A2-A4, B2-B3, B2-B4, H1-H2, H1-G1, H1-G2
golffzz
fonte
Também aqui é como placas de entrada de caso de teste parecido: i.stack.imgur.com/qlbH4.png
golffzz
11
@ugoren, considerei isso, mas enumerar todos os movimentos possíveis potencialmente elimina alguns atalhos. Não sei, porém, por que en passant não é necessário: parte do ponto do FEN é que ele inclui informações suficientes para torná-lo possível.
Peter Taylor
@ PeterTaylor eu escrevi isso apenas para reduzir o trabalho. Eu me pergunto por que ninguém interessado neste golf :)
golffzz
11
@golffzz, a entrada do seu caso de teste 2 não deve ser 7k / 8/8/8/8/8 / PP6 / Q1q4K w - - 0 1 em vez de 6pk / 6pp / 8/8/8 / p7 / PP4pp / Q2p2pK w - - 0 1 (que, entre outras coisas, parece ter peões nas fileiras finais)?
Penguino

Respostas:

8

Bytes C - 391

Recebe a entrada como argumentos da linha de comando e imprime em stdout com os quadrados rotulados de 0 a 63.

OK, eu tinha alguns minutos, então tentei excluir todos os bits relacionados à detecção do cheque. Eu acho que agora não é muito eficiente ...

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);}

Versão com detecção de verificação de 478 bytes

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;}
feersum
fonte
Isso é incrível, mas não corresponde à pergunta: "Ignorar cheque, xeque-mate e impasse, o rei também não pode ser capturado".
Edc65 13/10
@ edc65 Não concordo com a sua interpretação destas instruções, infelizmente incoerentes. Ele diz que "os movimentos de saída devem obedecer às regras de movimento do xadrez, exceto uma promoção passante, de castelos e de peões". Mover para verificação não aparece na lista de regras em negrito a ser ignorada. Tomo o terceiro ponto como observação: você não precisa detectar essas situações e refleti-las de qualquer forma na saída (por exemplo, a convenção de escrever '+' após uma verificação). Além disso, o segundo caso de teste 2 estava correto como originalmente escrito, dado que um ignora a promoção de peões conforme especificado (mas não fornece informações sobre a verificação).
feersum
O segundo caso de teste (entrada) era inválido com um peão preto na classificação 8 e diferente da imagem postada como um comentário por OP ( also here is how test case input boards look like). Dada a posição na imagem, a saída do caso de teste original estava correta de acordo com as regras.
Edc65 14/10
2
Oh, ótimo, a especificação real está nos comentários? Ugh, que pergunta ruim.
feersum
11
O vencedor claro
edc65
2

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);}
marcações
fonte
2

Python 553 649 678

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)

O recuo de dois espaços é o caractere de tabulação, que economiza 5 bytes.

Ocorre-me que você provavelmente pode fazê-lo avaliar movimentos razoáveis ​​para uma dobra decente e mantê-la abaixo de 1024 bytes :) Comecei a examinar outras questões de , mas não parece haver uma pergunta sobre o mecanismo de xadrez codegolf ...

Vai
fonte
2
Muito bem por ressuscitar esta pergunta! (Acho que posso dar uma recompensa apenas para ver o que acontece.) Sua resposta parece boa, mas falha B1C3e H2H3no primeiro exemplo mostrado na pergunta.
ossifrage escrúpulos
Desculpe, não H2H3, eu quis dizer G1H3- em outras palavras, seus cavaleiros brancos estão apenas virando à esquerda.
Ossifrage squeamish # 10/14
Vai ter que esperar até que eu esteja em um PC, mas esse é um bug fácil e também vejo várias maneiras de encurtá-lo. Espero que haja outras entradas.
Will
@squeamishossifrage fixed :)
Será que
1

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

Nota: depois def O(y): houver uma nova linha e um caractere de tabulação antesif

Nota: usando o módulo zlib, é possível obter um código fonte Python válido de 482 bytes, simplesmente compactando a fonte real:

#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Жхпy`B▌╬ 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╚У")
6502
fonte
1

JavaScript (E6) 481 492 550

Editar Corrigido um bug desagradável no movimento de cavaleiros. Muito trabalho para manter a contagem de bytes igual.

(Sem contar espaços iniciais e novas linhas mantidas para facilitar a leitura)

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

Menos Golfe

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
)

Teste no console do FireFox / FireBug

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

Resultado

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

JAVA 631 599 594

Corrigido um erro na versão de 599 bytes (obrigado Jack por apontar isso!) E reduziu o código para 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);}}}

Compilar: javac F.java
Executar: java F 6pk/6pp/8/8/8/p7/PP4pp/Q2p2pK w - - 0 1
Saída:B2B3 B2B4 B2A3 A1B1 A1C1 A1D1 H1H2 H1G1 H1G2

Bob Genom
fonte
Pois 3Q4/p4r1k/P4pp1/4P3/5n2/3P4/4BbbP/RN3KN1 w - - 0 0não estou vendo movimentos F1F2ou F1G2o rei é capaz de capturar?
Jack
Obrigado por apontar isto. Você está certo. Esta versão publicada está otimizada demais :(
Bob Genom 24/02
Portanto, tenho que voltar à minha solução de 631 bytes.
Bob Genom
573 bytes
ceilingcat