Совершенно удивлен, что это еще не было опубликовано, учитывая большое количество шахматных головоломок на сайте. Пока я сам об этом думал, благодарю Ануш за то, что она отправила его в песочницу в марте . Но я подумал, что прошло достаточно времени, чтобы я мог сделать это сам.

Мат в шахматах является положение , в котором король атакован и нет никаких шагов , которые могут защитить его. Если вы не знакомы с тем, как движутся шахматные фигуры, вы можете ознакомиться в Википедии .

Соревнование

Для этой задачи ваш вклад будет позицией шахматной доски в любой записи. Чтобы уточнить, ваш вклад опишет фигуры на шахматной доске, их цвета и позиции, а также возможный квадрат пассивного захвата, если таковой имеется. (Способность к замку не имеет значения, так как вы не можете замкнуться из-под контроля.) Вы можете найти нотацию FEN полезной , но подойдет любой удобный формат. Для простоты можно предположить, что в игру играют черные - это значит, что черные всегда будут игроком с матом. Позиция, в которой белые находятся в шахе, мате или пате, будет считаться недействительной для этого испытания.

Вы должны вывести истинное значение, если позиция является матом, и ложное значение, если это не так. Обратите внимание, что пат не является матом - король должен быть атакован!

Правдивые тесты

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

Тесты 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 ( следите за этим!)

Код гольфа - выигрывает самый короткий код в байтах. Удачи!

JavaScript (Node.js) ,  499 ... 374  370 байт

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

Ниже приведены ожидаемые значения для каждого квадрата:

 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

Попробуйте онлайн!

Как?

Правление представительства

Мы используем классическое представление доски 0x88 , чтобы можно было легко обнаруживать за пределами целевых квадратов.

   |  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

Переместить кодировку

Каждый набор ходов кодируется с 5 параметрами:

• тип произведения
• максимальное количество квадратов, которые можно посетить в каждом направлении
• флаг, указывающий, разрешены ли захваты
• флаг, указывающий, разрешены ли не-захваты
• список направлений

Все эти параметры упакованы в одну строку. Например, ходы рыцаря кодируются следующим образом:

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

который дает:

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

Все наборы ходов суммированы в следующей таблице, за исключением захватов по отдельности, которые обрабатываются отдельно.

  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

комментарии

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 байта

Байты сохранены благодаря Лео Тененбауму

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)

Попробуйте онлайн!

На данный момент это не совсем хорошо, но это только начало. С некоторой помощью по пути я теперь довольно агрессивно отыграл это (и исправил ошибку по пути).

Это, пожалуй, сомнительная вещь, это то, что она предполагает, что, кроме короля или пешки, вы никогда не сможете выйти из-под контроля, захватив одну из своих фигур. В шахматах вам не разрешено делать этот ход, но моя программа считает, что эти ходы сохраняют байты, при условии, что, если вы проверяете, это никогда не сможет вывести вас из этого.

Это предположение верно, потому что такие шаги

1. Невозможно поймать фигуру, которая атакует короля, так как фигура, которую они захватывают, черная.

2. Невозможно заблокировать путь фигуры, которая атакует короля, так как захваченная черная фигура уже сделала бы это.

Мы также добавляем дополнительное условие, что если у вас нет короля, вы находитесь под контролем.

Эта программа также предполагает, что если есть пешка, которая может быть захвачена пассивно, то пешка была последним ходом, и этот ход был законным ходом. Это связано с тем, что программа не проверяет, является ли квадрат, на который она перемещает черную пешку, пустым, поэтому, если там есть кусок, вещи могут немного запутаться. Однако это не может быть получено, если последний ход был законным ходом и, кроме того, не может быть представлен в FEN . Так что это предположение кажется довольно обоснованным.

Вот моя версия "ungolfed" для справки:

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)

Попробуйте онлайн!

Python 3 (PyPy) , 729 байт

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

Попробуйте онлайн!