15
\$\begingroup\$

Wholly surprised this hasn't been posted already, given the large number of chess puzzles on the site. While I thought of this myself, credit to Anush for posting it to the sandbox back in March. But I figured it's been long enough that I could go ahead and do so myself.

A checkmate in chess is a position in which the king is attacked and there is no move that can defend it. If you aren't familiar with how chess pieces move, you can familiarize yourself on Wikipedia.

The challenge

For this challenge, your input will be the position of a chess board in whatever notation you like. To clarify, your input will describe the pieces on a chess board, with their colors and positions, along with the possible en passant capture square, if any. (Ability to castle is irrelevant as you cannot castle out of check.) You may find FEN notation useful, but any convenient format is fine. For simplicity, you can assume it's Black to play - this means Black will always be the checkmated player. A position where White is in check, checkmate, or stalemate will be considered invalid for this challenge.

You must output a truthy value if the position is checkmate, and a falsey value if it is not. Note that stalemate is not checkmate - the king must be attacked!

Truthy test cases

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

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 (Watch that en passant!)

Code golf - shortest code in bytes wins. Good luck!

\$\endgroup\$
9
  • 2
    \$\begingroup\$ This looks like a great question :) \$\endgroup\$
    – user9207
    Commented Aug 26, 2019 at 15:02
  • 1
    \$\begingroup\$ In the interests of being self-contained - which all challenges here should be - this needs to be fleshed out a good deal more rather than relying on external links and/or assuming an existing knowledge of the rules and notation of chess. I'd suggest taking it back to the Sandbox while it is being worked on. \$\endgroup\$
    – Shaggy
    Commented Aug 26, 2019 at 15:25
  • 3
    \$\begingroup\$ @Shaggy The external links in this challenge serve for convenience only. I'm not going to list all of the rules of chess here, as most other chess challenges presume prior knowledge of them. And the lichess links only serve as a handy visual representation of the test cases; the notation is well-defined outside of lichess. I could add images but I decided not to as it felt like a lot of clutter. \$\endgroup\$ Commented Aug 26, 2019 at 16:33
  • 1
    \$\begingroup\$ Can we assume that the board has been arrived at via a valid game? \$\endgroup\$
    – Wheat Wizard
    Commented Aug 26, 2019 at 20:21
  • 1
    \$\begingroup\$ I've reopened this because while the core task is the same this challenge has a much more lax (and honestly a better) IO scheme and a slightly different (and honestly better) scoring criterion. I think that perhaps the old one should be closed as a dupe of the new one but I am not going to hammer it. \$\endgroup\$
    – Wheat Wizard
    Commented Aug 26, 2019 at 22:41

3 Answers 3

12
+50
\$\begingroup\$

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

Takes input as (b)(X), where \$b\$ is an array of 64 integers describing the squares (from left to right and from top to bottom) and \$X\$ is the 0-based index of the en-passant target square, or \$-1\$ if there's none.

Below are the expected values for each square:

 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

Returns \$64\$ for checkmate, or \$0\$ for not-checkmate.

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

Try it online!

How?

Board representation

We use the classic 0x88 board representation, so that out-of-bounds target squares can be easily detected.

   |  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

Move encoding

Each set of moves is encoded with 5 parameters:

  • the type of piece
  • the maximum number of squares that can be visited in each direction
  • a flag telling if captures are allowed
  • a flag telling if non-captures are allowed
  • a list of directions

All these parameters are packed into a single string. For instance, knight moves are encoded as follows:

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

To decode a direction, we subtract \$66\$ from its ASCII code:

 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

which gives:

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

All sets of moves are summarized in the following table, except en-passant captures which are processed separately.

  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

Commented

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
\$\endgroup\$
5
  • \$\begingroup\$ 8/1ppp4/1pkp4/8/2Q5/8/8/7K b - - \$\endgroup\$
    – tsh
    Commented Aug 28, 2019 at 7:23
  • \$\begingroup\$ @tsh A much more serious bug. Fixed at the cost of 6 bytes for now. \$\endgroup\$
    – Arnauld
    Commented Aug 28, 2019 at 8:01
  • \$\begingroup\$ How does work without a representation telling you if en passant is possible? \$\endgroup\$
    – user9207
    Commented Aug 28, 2019 at 8:31
  • \$\begingroup\$ @Anush The \$X\$ parameter holds this information. \$\endgroup\$
    – Arnauld
    Commented Aug 28, 2019 at 8:38
  • \$\begingroup\$ This is an amazing answer. I hope it was nominated for a prize. \$\endgroup\$
    – user7467
    Commented May 2, 2021 at 10:28
6
\$\begingroup\$

Haskell, 1165 1065 1053 bytes

Bytes saved thanks to 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)

Try it online!

This is not exactly well golfed as of now, but it is a start. With some help along the way I've now golfed this down pretty aggressively (and fixed an error along the way).

The one perhaps questionable thing this does is that it assumes that, other than by a king or a pawn en passant, you can never get out of check by capturing one of your own pieces. In chess you are not allowed to make this move but my program considers these moves to save bytes under the assumption that if you are in check this can never get you out of it.

This assumption is valid because such moves

  1. Cannot capture the piece that is attacking the king, since the piece they capture is black.

  2. Cannot block the path of the piece that is attacking the king, since the captured black piece would have already been doing that.

We also add the additional stipulation that if you have no king you are in check.

This program also makes the assumption that if there is a pawn that can be captured en passant, then the pawn was the last piece to move and that move was a legal move. This is because the program does not check if the square it moves the black pawn to is empty so if there is a piece there things can get a little screwy. However this cannot be obtained if the last move was a legal move and furthermore cannot be represented in FEN. So this assumption seems rather solid.

Here is my "ungolfed" version for reference:

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)

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ 1252 bytes with a bit of golfing (the TIO link was too long to fit in this comment...) \$\endgroup\$
    – pommicket
    Commented Aug 27, 2019 at 0:33
  • \$\begingroup\$ @LeoTenenbaum Thanks a bunch I will incorporate this shortly unfortunately there were two accidental errors in the version you were golfing from which I have now fixed. There is certainly room to improve in a lot of ways with a program this long. \$\endgroup\$
    – Wheat Wizard
    Commented Aug 27, 2019 at 0:40
  • \$\begingroup\$ @tsh yep, I forgot to add the kings location to where it was going. fixed now \$\endgroup\$
    – Wheat Wizard
    Commented Aug 27, 2019 at 13:53
  • \$\begingroup\$ For lists, guard x = [0|x], and you can also use x?y=Just(x,y) to save a few more bytes: 1129 bytes \$\endgroup\$
    – pommicket
    Commented Aug 27, 2019 at 18:14
1
\$\begingroup\$

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ This currently fails for 8/2p5/Q7/Q2k4/Q7/8/8/7K b - - (not checkmate). \$\endgroup\$
    – Arnauld
    Commented Sep 2, 2019 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.