Tout à fait surpris que cela n'ait pas déjà été publié, compte tenu du grand nombre de puzzles d'échecs sur le site. Pendant que j'y pensais moi-même, merci à Anush de l'avoir posté dans le bac à sable en mars . Mais je me suis dit que ça faisait assez longtemps que je pouvais aller de l'avant et le faire moi-même.

Un échec et mat dans les échecs est une position dans laquelle le roi est attaqué et aucun mouvement ne peut le défendre. Si vous n'êtes pas familier avec le mouvement des pièces d'échecs, vous pouvez vous familiariser avec Wikipedia .

Le défi

Pour ce défi, votre entrée sera la position d'un échiquier dans la notation que vous souhaitez. Pour clarifier, votre entrée décrira les pièces sur un échiquier, avec leurs couleurs et positions, ainsi que le carré de capture en passant éventuel , le cas échéant. (La capacité à roquer n'est pas pertinente car vous ne pouvez pas roquer hors de contrôle.) Vous pouvez trouver la notation FEN utile , mais tout format pratique convient. Pour simplifier, vous pouvez supposer que c'est du noir à jouer - cela signifie que le noir sera toujours le joueur mat. Une position où Blanc est en échec, échec ou échec sera considérée comme invalide pour ce défi.

Vous devez sortir une valeur véridique si la position est échec et mat et une valeur falsey si ce n'est pas le cas. Notez que l' impasse n'est pas échec et mat et - le roi doit être attaqué!

Cas de test authentiques

1k5R / 6R1 / 8/8/8/8/8 / 6K1 b - -

rn2r1k1 / pp1p1pQp / 3p4 / 1b1n4 / 1P2P3 / 2B5 / P5PP / R3K2R b - -

kr5R / rB6 / 8/8/8 / 5Q2 / 6K1 / R7 b - -

2K5 / 1B6 / 8/8/8 / 7N / R7 / R3r2k b - - 0 1

8 / 4Q1R1 / R7 / 5k2 / 3pP3 / 5K2 / 8/8 b - -

2K5 / 1B6 / 8/8/8 / 4b2N / R7 / 4r2k b - -

Cas de test Falsey

rnbqkbnr / pppppppp / 8/8 / 4P3 / 8 / PPPP1PPP / RNBQKBNR b KQkq -

8/8/8/8/8 / 1KQ5 / 4N3 / 1k6 b - -

2K5 / 1B6 / 8/8/8 / 7N / R7 / 4r2k b - -

8/8 / 2Q5 / 3k4 / 3Q5 / 8/8 / 7K b - -

8 / 4Q1R1 / R7 / 5k2 / 3pP3 / 5K2 / 8/8 b - e3 (Regardez ça en passant!)

Golf de code - le code le plus court en octets gagne. Bonne chance!

JavaScript (Node.js) ,  499 ... 374  370 octets

(b)(X)$b$$X$$-1$

Voici les valeurs attendues pour chaque carré:

 0: empty square

 5: white pawn      6: black pawn
 9: white king     10: black king
17: white bishop   18: black bishop
33: white rook     34: black rook
49: white queen    50: black queen
65: white knight   66: black knight

$64$$0$

b=>e=>(g=(c,k)=>b.map((v,p,h,s=p+(p&~7),M=t=>v&-~c?c?(B=[...b],K&=g(b[t?b[T]=b[p]:b[b[e-8]=0,e]=6,p]=0),b=B):k|=V&8:0,m=([a],[x,t,...d]=Buffer(a))=>d.map(c=>(h=n=>(V=(a+=c-66)&136?3:b[T=a+a%8>>1])&v&3||t>>!V&v>>x&n>31&&h(n-4/!V,M``))(t,a=s)))=>(v=b[p],m`##123ACQRS`,m`$?13QS`,m`%?2ACR`,m`&#!#04PTac`,c?(p-e+8.5&~1||M(),m`"!QS`,p<16?m`"&R`:m`""R`):m`"!13`))|k)(1,K=g())*K

Essayez-le en ligne!

Comment?

Représentation au conseil

Nous utilisons la représentation classique de la carte 0x88 , afin que les carrés cibles hors limites puissent être facilement détectés.

   |  a    b    c    d    e    f    g    h
---+----------------------------------------
 8 | 0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07 
 7 | 0x10 0x11 0x12 0x13 0x14 0x15 0x16 0x17 
 6 | 0x20 0x21 0x22 0x23 0x24 0x25 0x26 0x27 
 5 | 0x30 0x31 0x32 0x33 0x34 0x35 0x36 0x37 
 4 | 0x40 0x41 0x42 0x43 0x44 0x45 0x46 0x47 
 3 | 0x50 0x51 0x52 0x53 0x54 0x55 0x56 0x57 
 2 | 0x60 0x61 0x62 0x63 0x64 0x65 0x66 0x67 
 1 | 0x70 0x71 0x72 0x73 0x74 0x75 0x76 0x77

Déplacer l'encodage

Chaque ensemble de mouvements est codé avec 5 paramètres:

• le type de pièce
• le nombre maximum de carrés pouvant être visités dans chaque direction
• un drapeau indiquant si les captures sont autorisées
• un drapeau indiquant si les non-captures sont autorisées
• une liste de directions

Tous ces paramètres sont regroupés dans une seule chaîne. Par exemple, les mouvements de chevalier sont codés comme suit:

`&#!#04PTac`
 ||\______/
 ||    |                            +------> 0 + 1 = 1 square in each direction
 ||    |                            | +----> standard moves allowed
 ||    +---> 8 directions           | |+---> captures allowed
 ||                                / \||
 |+--------> ASCII code = 35 = 0b0100011
 |
 +---------> 1 << (ASCII code MOD 32) = 1 << 6 = 64

$66$

 char. | ASCII code | -66
-------+------------+-----
  '!'  |     33     | -33
  '#'  |     35     | -31
  '0'  |     48     | -18
  '4'  |     52     | -14
  'P'  |     80     | +14
  'T'  |     84     | +18
  'a'  |     97     | +31
  'c'  |     99     | +33

qui donne:

 [ - ] [-33] [ - ] [-31] [ - ]
 [-18] [ - ] [ - ] [ - ] [-14]
 [ - ] [ - ] [ N ] [ - ] [ - ]
 [+14] [ - ] [ - ] [ - ] [+18]
 [ - ] [+31] [ - ] [+33] [ - ]

Tous les ensembles de mouvements sont résumés dans le tableau suivant, à l'exception des captures en passant qui sont traitées séparément.

  string    | description             | N | S | C | directions
------------+-------------------------+---+---+---+----------------------------------------
 &#!#04PTac | knight                  | 1 | Y | Y | -33, -31, -18, -14, +14, +18, +31, +33
 ##123ACQRS | king                    | 1 | Y | Y | -17, -16, -15, -1, +1, +15, +16, +17
 "!13       | white pawn / captures   | 1 | N | Y | -17, -15
 "!QS       | black pawn / captures   | 1 | N | Y | +15, +17
 "&R        | black pawn / advance x2 | 2 | Y | N | +16
 ""R        | black pawn / advance x1 | 1 | Y | N | +16
 $?13QS     | bishop or queen         | 8 | Y | Y | -17, -15, +15, +17
 %?2ACR     | rook or queen           | 8 | Y | Y | -16, -1, +1, +16

Commenté

b => e => (
  // generate all moves for a given side
  g = (c, k) =>
    b.map((
      v, p, h,
      // s = square index in 0x88 format
      s = p + (p & ~7),
      // process a move
      M = t =>
        // make sure that the current piece is of the expected color
        v & -~c ?
          c ?
            // Black's turn: play the move
            ( // board backup
              B = [...b],
              // generate all White moves ...
              K &= g(
                // ... after the board has been updated
                b[
                  t ?
                    // standard move
                    b[T] = b[p]
                  :
                    // en-passant capture
                    b[b[e - 8] = 0, e] = 6,
                  p
                ] = 0
              ),
              // restore the board
              b = B
            )
          :
            // White's turn: just update the king's capture flag
            k |= V & 8
        :
          0,
      // generate all moves of a given type for a given piece
      m = ([a], [x, t, ...d] = Buffer(a)) =>
        d.map(c =>
          ( h = n =>
            ( // advance to the next target square
              V = (a += c - 66) & 136 ? 3 : b[T = a + a % 8 >> 1]
            )
            // abort if it's a border or a friendly piece
            & v & 3 ||
            // otherwise: if this kind of move is allowed
            t >> !V &
            // and the current piece is of the expected type
            v >> x &
            // and we haven't reached the maximum number of squares,
            n > 31 &&
            // process this move (if it's a capture, force n to
            // -Infinity so that the recursion stops)
            h(n - 4 / !V, M``)
          )(t, a = s)
        )
    ) =>
      (
        v = b[p],
        // king
        m`##123ACQRS`,
        // bishop or queen
        m`$?13QS`,
        // rook or queen
        m`%?2ACR`,
        // knight
        m`&#!#04PTac`,
        c ?
          // black pawn
          ( // en-passant capture
            p - e + 8.5 & ~1 || M(),
            // standard captures
            m`"!QS`,
            // standard moves
            p < 16 ? m`"&R` : m`""R`
          )
        :
          // white pawn (standard captures only)
          m`"!13`
      )
    ) | k
// is the black king in check if the Black don't move?
// is it still in check after each possible move?
)(1, K = g()) * K

Haskell , 1165 1065 1053 octets

Octets économisés grâce à Leo Tenenbaum

n=Nothing
x?y=Just(x,y)
o(x,y)=x<0||y<0||x>7||y>7
m#k@(x,y)|o k=n|1>0=m!!x!!y
z(x,y)m p(a,b)|o(x+a,y+b)=1<0|Just g<-m#(x+a,y+b)=elem g[(p,0),(5,0)]|1>0=z(x+a,y+b)m p(a,b)
t(x,y)p(a,b)m|o(x+a,y+b)=[]|g<-(x+a,y+b)=(g%p)m++do[0|m#g==n];t g p(a,b)m
c m|(x,y):_<-[(a,b)|a<-u,b<-u,m#(a,b)==6?1],k<-z(x,y)m=or$[m#(x+a,y+b)==6?0|a<-0:s,b<-0:s]++do a<-s;[k 3(a,b)|b<-s]++(k 2<$>[(a,0),(0,a)])++[m#l==4?0|b<-[2,-2],l<-[(x+a,y+b),(x+b,y+a)]]++[m#(x-1,y+a)==p?0|p<-[0,1]]
c m=1>0
(k%p)m=[[[([p|a==k]++[m#a])!!0|a<-(,)b<$>u]|b<-u]|not$o k]
w(Just(_,1))=1<0
w x=1>0
m!u@(x,y)|g<-m#u,Just(q,1)<-g,v<-((u%n)m>>=),r<-v.t u g,k<-(do[0|n==m#(x+1,y)];(u%n)m>>=(x+1,y)%g)++(do a<-s;[0|n<m#(x+1,y+a)];v$(x+1,y+a)%g)++(do[0|(x,n,n)==(1,m#(x+1,y),m#(x+2,y))];v$(x+2,y)%g)++(do a<-s;[0|1?0==m#(x,y+a)];v((x,y+a)%n)>>=(x+1,y+a)%g)=[k,k,do a<-s;[(a,0),(0,a)]>>=r,do a<-s;b<-s;r(a,b),do a<-s;b<-[2,-2];l<-[(x+a,y+b),(x+b,y+a)];v$l%g,do a<-0:s;b<-[0|a/=0]++s;r(a,b),do a<-[x-1..x+1];b<-[y-1..y+1];[0|w$m#(a,b)];v$(a,b)%g]!!q
m!u=[]
u=[0..7]
s=[1,-1]
q m=all c$m:do a<-u;b<-u;m!(a,b)

Essayez-le en ligne!

Ce n'est pas vraiment bien joué pour l'instant, mais c'est un début. Avec un peu d'aide en cours de route, j'ai maintenant résolu ce problème de manière assez agressive (et corrigé une erreur en cours de route).

La seule chose peut-être discutable, c'est que cela suppose que, sauf par un roi ou un pion en passant, vous ne pouvez jamais vous soustraire en capturant l'une de vos propres pièces. Aux échecs, vous n'êtes pas autorisé à effectuer ce mouvement, mais mon programme considère ces mouvements pour économiser des octets en supposant que si vous êtes en contrôle, cela ne peut jamais vous en sortir.

Cette hypothèse est valable car de tels mouvements

1. Impossible de capturer la pièce qui attaque le roi, car la pièce capturée est noire.

2. Impossible de bloquer le chemin de la pièce qui attaque le roi, car la pièce noire capturée aurait déjà fait cela.

Nous ajoutons également la stipulation supplémentaire que si vous n'avez pas de roi, vous êtes en échec.

Ce programme fait également l'hypothèse que s'il y a un pion qui peut être capturé en passant, alors le pion était la dernière pièce à se déplacer et ce mouvement était légal. C'est parce que le programme ne vérifie pas si le carré vers lequel se déplace le pion noir est vide, donc s'il y a un morceau, les choses peuvent devenir un peu vissées. Cependant, cela ne peut pas être obtenu si le dernier coup était légal et ne peut pas non plus être représenté dans la FEN . Cette hypothèse semble donc assez solide.

Voici ma version "non golfée" pour référence:

import Control.Monad
out(x,y)=x<0||y<0||x>7||y>7
at b (x,y)
  |out(x,y)=Nothing
  |otherwise=(b!!x)!!y
inLine (x,y) ps m (a,b) 
  | out (x+a,y+b) = False
  | elem (m `at` (x+a,y+b)) $ Just <$> ps = True
  | m `at` (x+a,y+b) == Nothing = inLine (x+a,y+b) ps m (a,b) 
  | otherwise = False
goLine (x,y) p (a,b)m
  | out (x+a,y+b) = []
  | otherwise = case m `at` (x+a,y+b) of
--    Just (n,1) -> []
    Just (n,_) -> set(x+a,y+b)p m
    Nothing    -> set(x+a,y+b)p m ++ goLine(x+a,y+b)p(a,b)m
checkBishop (x,y) m=or[inLine(x,y)[(3,0),(5,0)]m(a,b)|a<-[1,-1],b<-[1,-1]]
checkRook   (x,y) m=or$do
  a<-[1,-1]
  inLine(x,y)[(2,0),(5,0)]m<$>[(a,0),(0,a)]
checkKnight (x,y) m=any((==Just(4,0)).(at m))$do
  a<-[1,-1]
  b<-[2,-2]
  [(x+a,y+b),(x+b,y+a)]
checkPawn (x,y) m=or[at m a==Just(p,0)|a<-[(x-1,y+1),(x-1,y-1)],p<-[0,1]]
checkKing (x,y) m=or[at m(a,b)==Just(6,0)|a<-[x-1..x+1],b<-[y-1..y+1]]
check m
  | u:_<-[(a,b)|a<-[0..7],b<-[0..7],(m!!a)!!b==Just(6,1)] =
    checkBishop u m ||
    checkRook   u m ||
    checkKnight u m ||
    checkPawn   u m ||
    checkKing   u m
  | otherwise = True
set (x,y) p m=[[[head$[p|(a,b)==(y,x)]++[(m!!b)!!a]|a<-[0..7]]|b<-[0..7]]|not$out(x,y)]
white(Just(n,0))=True
white x=False
moves m (x,y)
 |g<-m `at` (x,y)=case g of
  Just(2,1) -> do
    a<-[1,-1]
    b<-[(a,0),(0,a)]
    set(x,y)Nothing m>>=goLine (x,y) g b
  Just(3,1) -> do
    a<-[1,-1]
    b<-[1,-1]
    set(x,y)Nothing m>>=goLine (x,y) g(a,b)
  Just(4,1) -> do
    n<-set(x,y)Nothing m
    a<-[1,-1]
    b<-[2,-2]
    l<-[(x+a,y+b),(x+b,y+a)]
    -- guard$white$n `at` l
    set l g n
  Just(5,1) -> do
    a<-[1,-1]
    c<-[(a,0),(0,a),(a,1),(a,-1)]
    set(x,y)Nothing m>>=goLine (x,y) g c
  Just(6,1) -> do
    a<-[x-1..y+1]
    b<-[x-1..y+1]
    guard$white(m `at`(a,b))||Nothing==m`at`(a,b)
    set(x,y)Nothing m>>=set(a,b)g
  Just(n,1) -> (do
    guard$Nothing==m `at` (x+1,y)
    set(x,y)Nothing m>>=set(x+1,y)g) ++ (do
      a<-[1,-1]
      guard$white$m`at`(x+1,y+a)
      set(x,y)Nothing m>>=set(x+1,y+a)g) ++ (do
        guard$(x,Nothing,Nothing)==(1,m`at`(x+1,y),m`at`(x+1,y))
        set(x,y)Nothing m>>=set(x+2,y)g) ++ (do
          a<-[1,-1]
          guard$Just(1,0)==m`at`(x,y+a)
          set(x,y)Nothing m>>=set(x,y+a)Nothing>>=set(x+1,y+a)g)
  _ -> []
checkmate m=all check$m:do
  a<-[0..7]
  b<-[0..7]
  moves m(a,b)

Essayez-le en ligne!

Python 3 (PyPy) , 729 octets

F=lambda a,b:a<'^'<=b or a>'^'>=b
def m(b,P,A=0):
 yield b
 for(r,f),p in b.items(): 
  if F(P,p):continue
  *d,n,k={'R':[(0,1),8,4],'N':[(1,2),(2,1),2,4],'B':[(1,1),8,4],'Q':[(0,1),(1,1),8,4],'K':[(0,1),(1,1),2,4],'P':[(2,0),(1,0),(1,1),(1,-1),2,1],'p':[(-2,0),(-1,0),(-1,1),(-1,-1),2,1]}[p if p=='p'else p.upper()]
  if p in'pP':d=d[d!=[2,7][p=='p']+A:]
  for u,v in d:
   for j in range(k):
    for i in range(1,n):
     U=r+u*i;V=f+v*i;t=b.get((U,V),'^')
     if U<1or U>8or V<1 or V>8:break
     if F(p,t):
      B=dict(b);B[(U,V)]=B.pop((r,f))
      if t in'eE':B.pop(([U+1,U-1][t=='e'],V))
      yield B
     if t not in'^eE':break
    u,v=v,-u
M=lambda b:all(any('k'not in C.values()for C in m(B,'W',1))for B in m(b,'b'))

Essayez-le en ligne!