Totalmente sorprendido de que esto no se haya publicado ya, dada la gran cantidad de rompecabezas de ajedrez en el sitio. Mientras pensaba en esto, agradezco a Anush por publicarlo en la caja de arena en marzo . Pero pensé que había pasado el tiempo suficiente para poder seguir adelante y hacerlo yo mismo.

Un jaque mate en ajedrez es una posición en la que el rey es atacado y no hay movimiento que pueda defenderlo. Si no está familiarizado con cómo se mueven las piezas de ajedrez, puede familiarizarse con Wikipedia .

El reto

Para este desafío, su entrada será la posición de un tablero de ajedrez en la notación que desee. Para aclarar, su entrada describirá las piezas en un tablero de ajedrez, con sus colores y posiciones, junto con el posible cuadro de captura pasajero , si lo hay. (La capacidad de castillo es irrelevante, ya que no puede hacerlo fuera de control). Puede encontrar útil la notación FEN , pero cualquier formato conveniente está bien. Por simplicidad, puedes asumir que es negro para jugar , esto significa que el negro siempre será el jugador de jaque mate. Una posición en la que las blancas estén en jaque, jaque mate o estancadas se considerará inválida para este desafío.

Debe generar un valor verdadero si la posición es jaque mate, y un valor falso si no lo es. Tenga en cuenta que el punto muerto no es jaque mate : ¡el rey debe ser atacado!

Casos de prueba de verdad

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

Casos de prueba de 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 (¡Cuidado con eso!)

Código de golf: el código más corto en bytes gana. ¡Buena suerte!

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

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

A continuación se muestran los valores esperados para cada cuadrado:

 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

Pruébalo en línea!

¿Cómo?

Representación de la junta

Utilizamos la representación clásica de tablero 0x88 , para que los cuadrados objetivo fuera de los límites se puedan detectar fácilmente.

   |  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

Mover codificación

Cada conjunto de movimientos está codificado con 5 parámetros:

• el tipo de pieza
• El número máximo de cuadrados que se pueden visitar en cada dirección.
• una bandera que indica si se permiten capturas
• una bandera que indica si se permiten no capturas
• una lista de direcciones

Todos estos parámetros están empaquetados en una sola cadena. Por ejemplo, los movimientos de caballeros se codifican de la siguiente manera:

`&#!#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

lo que da:

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

Todos los conjuntos de movimientos se resumen en la siguiente tabla, excepto las capturas pasantes que se procesan por separado.

  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

Comentado

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 bytes

Bytes guardados gracias a 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)

Pruébalo en línea!

Por el momento, esto no está exactamente bien, pero es un comienzo. Con algo de ayuda en el camino, ahora he jugado golf de manera bastante agresiva (y solucioné un error en el camino).

Lo más cuestionable que esto hace es que supone que, aparte de un rey o un peón al paso, nunca puedes salir de control capturando una de tus propias piezas. En el ajedrez no tienes permitido hacer este movimiento, pero mi programa considera estos movimientos para guardar bytes bajo el supuesto de que si estás en control, esto nunca podrá sacarte de allí.

Esta suposición es válida porque tales movimientos

1. No se puede capturar la pieza que está atacando al rey, ya que la pieza que capturan es negra.

2. No se puede bloquear el camino de la pieza que está atacando al rey, ya que la pieza negra capturada ya habría estado haciendo eso.

También agregamos la estipulación adicional de que si no tienes un rey estás bajo control.

Este programa también supone que si hay un peón que se puede capturar de pasada, entonces el peón fue la última pieza en moverse y ese movimiento fue legal. Esto se debe a que el programa no comprueba si el cuadrado al que mueve el peón negro está vacío, por lo que si hay una pieza, las cosas pueden ponerse un poco complicadas. Sin embargo, esto no se puede obtener si el último movimiento fue legal y, además, no se puede representar en FEN . Entonces esta suposición parece bastante sólida.

Aquí está mi versión "sin golf" para referencia:

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)

Pruébalo en línea!

Python 3 (PyPy) , 729 bytes

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

Pruébalo en línea!