17
\$\begingroup\$

The game of chess has moves. Lots of moves. But how many, exactly? In this challenge, you must print all possible chess moves for a single player (black or white — you choose).

Moves are distinguished by the piece, the starting square and the ending square. Also, if the move is a promotion, moves are distinguished by the promotion piece. Consequently:

  • A capture by a pawn is always different from a pawn push
  • An en-passant capture is considered identical to a regular capture
  • A pawn push with promotion yields 4 moves (knight, bishop, rook, queen)
  • A capture by a non-pawn is considered identical to a regular move
  • It doesn't matter if a move is a check or checkmate

Additional rules:

  1. Output moves using long algebraic notation (LAN), as described here. Specifically:

    • First character must specify the piece (N/B/R/Q/K) or nothing for pawn
    • Specify starting and ending square in algebraic notation; case-insensitive
    • Separate by - or x for regular moves and captures correspondingly
    • Append =N, =B, =R, =Q for promotions
    • Use O-O and O-O-O for castling
  2. Pawns can't start their move at rank 1 or 8

  3. Separate moves by any reasonable separator; or make a function returning a list of strings

  4. Print in any order

  5. You must print all possible moves

  6. You must not print any move twice

  7. Chess libraries are allowed, but please include import syntax in your byte count

There are

3876

possible moves that you should print.

Example output (for the white player):

a2xb3
a2-a3
a2-a4
...
a7xb8=Q
a7xb8=R
a7xb8=B
a7xb8=N
a7-a8=Q
a7-a8=R
...
Nb5-d4
Nb5-c3
...
Ba1-h8
...
Ra1-a8
...
Kh8xh7
Kh8xg7
O-O
O-O-O

Here, some of the piece moves are captures and others are not, for no particular reason. I suspect it would be easiest to output only capturing moves or only non-capturing moves.

\$\endgroup\$
0

4 Answers 4

11
\$\begingroup\$

JavaScript (V8), 248 bytes

A full program that prints all possible moves for the white side. For pieces other than pawns, only regular moves are used.

c="abcdefgh"
p="NBRQK"
for(n=4**8;n--;k=h*=h,k+=v=V*V,!n|k*![k-5,b=h-v,v*=h,b*v,k>2,Y**y-3|h,!y|~V|h^i&1|Y>6^i>7][i>6?6:i]&&print(i>7?m+"="+p[i/2&3]:m))m=n?[p[i=n>>12]]+c[V=y=n>>9&7,h=n>>6&7]+-~y+"-x"[i&i>6]+c[V-=Y=n/8&7,h-=X=n&7,X]+-~Y:`O-O
O-O-O`

Try it online!

(the test code redefines the print method in order to count the moves)

Explanation

Encoding

Each move candidate is encoded as a single 16-bit value \$n\$ which is split into 5 variables:

iiiiyyyxxxYYYXXX
\__/\____/\____/
  |    |     |
  |    |     +--> X,Y = coordinates of target square
  |    +--------> x,y = coordinates of source square
  +-------------> i   = move type index

Move conditions

For each source square at \$(x,y)\$ and each target square at \$(X,Y)\$, we define:

$$h=(x-X)^2\\ \:V=y-Y\\ v=V^2\\ k=h+v$$

Global conditions:

  • For all moves, we must have \$k\neq0\$ (the target square is not equal to the source square).
  • For pawn moves, we must have \$y\neq0\$ (pawns are never moving from the first rank).

The other conditions depend on the pieces and move types:

Index Piece Move type Condition
0 knight regular move \$k=5\$
1 bishop regular move \$h=v\$
2 rook regular move \$h=0\$ or \$v=0\$
3 queen regular move \$h=v\$ or \$h=0\$ or \$v=0\$
4 king regular move \$k\le2\$
5 pawn 2-square move \$h=0\$ and \$y=1\$ and \$Y=3\$
\$\Leftrightarrow\$ \$h=0\$ and \$Y^y=3\$
6 pawn 1-square move \$V=-1\$ and \$h=0\$ and \$Y<7\$
7 pawn capture \$V=-1\$ and \$h=1\$ and \$Y<7\$
8,10,12,14 pawn promotion \$V=-1\$ and \$h=0\$ and \$Y=7\$
9,11,13,15 pawn promotion + capture \$V=-1\$ and \$h=1\$ and \$Y=7\$

Notes:

  • In the JS implementation, we test if the moves are invalid by using the opposite conditions which are overall shorter.
  • Castling moves are hard-coded separately and displayed when \$n=0\$.
\$\endgroup\$
4
\$\begingroup\$

Jelly,  140  130 bytes

ạ/ṢµẠ⁻Ẹ;E;Ẹ$;JƑ;ỊẠ$
“ RBQNK”p⁾x-;þṖḊ”=pƲZḢW;mʋ2
7Ḋ;€-µjþØ+Ẏ,j€0ṠḤḢṭƲ$
8p`⁺EÐḟµ_\FḊeⱮ¢+a¥FṪ⁼8Ʋ;ÑḤ2£ḣ€"ẎQ¹Ƈż€ị1¦€Øa$)Ẏ⁾O-ṁⱮ3,5¤;YFḟ⁶

A full program that prints all of white's possible moves separated by newline characters.

Try it online!

How?

For each pair of unequal locations form a list:

[ PawnCanCapture + (PawnCanCapture AND EndsAtEighthRank),
  PawnCanPush + (PawnCanPush AND EndsAtEighthRank),
  RookCanMove,
  BishopCanMove,
  QueenCanMove,
  KnightCanMove,
  KingCanMove,
]

Then format these in the notation, using 2 to identify promotion, and prefix them with the two castle moves.

Note: execution starts at the Main Link, at the bottom.

ạ/ṢµẠ⁻Ẹ;E;Ẹ$;JƑ;ỊẠ$ - Link 1: [[StartFile, StartRank], [EndFile, EndRank]]
ạ/                  - reduce by absolute difference -> [FileDelta, RankDelta]
  Ṣ                 - sort
   µ                - start a new monadic chain - f(X=that)
    Ạ⁻Ẹ             - all(X) not equal any(X)? -> isR = 1 * isRookMove
        E           - all equal(X)? -> isB = 1 * isBishMove
       ;            - concatenate -> [isR, isB]
         ;Ẹ$        - concatenate any {[isR, isB]} -> [isR, isB, isQ]
             JƑ     - is X invariant under get indices? (i.e. ==[1,2])
                        -> isN = isHorseyMove?
            ;       - concatenate -> [isR, isB, isQ, isN]
                ỊẠ$ - all insignificant (abs(x)<=1)? -> isK = isKingMove
               ;    - concatenate -> [isR, isB, isQ, isN, isK]

“ RBQNK”p⁾x-;þṖḊ”=pƲZḢW;mʋ2 - Link 2: no arguments
“ RBQNK”                    - set left argument to " RBQNK"
        p⁾x-                - Cartesian product "x-"
                   Ʋ        - last four links as a monad - f(" RBQNK"):
              ṖḊ            -   pop; dequeue {" RBQNK"} -> "RBQN"
                ”=p         -   '=' Cartesian product {that} -> ["=R","=B","=Q","=N"]
            ;þ              - concatenation table
                    Z       - transpose
                     ḢW;mʋ2 - head, wrap, concatenate with every other
                                ->  [[" x=R"," x=B"," x=Q"," x=N"],
                                     [" -=R"," -=B"," -=Q"," -=N"],
                                     ["R-=R","R-=B","R-=Q","R-=N"],
                                     ["B-=R","B-=B","B-=Q","B-=N"],
                                     ["Q-=R","Q-=B","Q-=Q","Q-=N"],
                                     ["N-=R","N-=B","N-=Q","N-=N"],
                                     ["K-=R","K-=B","K-=Q","K-=N"]] 
    
7Ḋ;€-µjþØ+Ẏ,j€0ṠḤḢṭƲ$ - Link 3: no arguments
7Ḋ                    - seven dequeued -> [2,3,4,5,6,7]
  ;€-                 - concatenate -1 to each -> PawnData = [[2,-1],...,[7,-1]]
     µ                - start a new monadic chain - f(that)
      jþØ+            - table of join with [1, -1]
          Ẏ           - tighten
                    $ - last two links as a monad - f(PawnData):
            j€0       -   join each with zero -> [[2,0,-1],...,[7,0,-1]]
                   Ʋ  -   last four links as a monad - f(that):
               Ṡ      -     signs
                Ḥ     -     double
                 Ḣ    -     head
                  ṭ   -     tack
           ,          - pair
                          -> [PawnCaptures, PawnPushes] each as
                               [StartRank, StartFile-EndFile, StartRank-EndRank]
                           = [[[2,1,-1],...,[7,1,-1],[2,-1,-1],...,[7,-1,-1]],
                             [[2,0,-1],...,[7,0,-1],[2,0,-2]]]

_\FḊeⱮ¢+a¥FṪ⁼8Ʋ;ÑḤ2£ḣ€"ẎQ¹Ƈż€ị1¦€Øa$ - chain: [[StartFile, StartRank], [EndFile, EndRank]]:
_\                                   - cumulative reduce by subtraction -> [[StartFile, StartRank], [StartFile-EndFile, StartRank-EndRank]]
  FḊ                                 - flatten, dequeue -> [StartRank, StartFile-EndFile, StartRank-EndRank]
    eⱮ¢                              - exists in? map across: call Link 3
          FṪ⁼8Ʋ                      - EndRank = 8?
       +a¥                           - add AND -> make 1 a 2 if so 
               ;Ñ                    - concatenate: call Link 1
                 Ḥ                   - double
                  2£ḣ€"              - call Link 2 and zip with head to {those} indices
                       ẎQ¹Ƈ          - tighten, deduplicate, remove empties
                             ị1¦€Øa$ - replace 1-8 with 'a'-'h' for files
                           ż€        - zip with each
         ^ 
8p`⁺EÐḟµ...)Ẏ⁾O-ṁⱮ3,5¤;YFḟ⁶ - Main Link: no arguments
8p`                         - [1..8] Cartesian product [1..8]
   ⁺                        - repeat -> all [[StartFile, StartRank], [EndFile, EndRank]]
    EÐḟ                     - remove if all equal
       µ...)                - monadic chain (see above) for each
                                  -> non-castling moves with ' ' as pawn
            Ẏ               - tighten
             ⁾O-ṁⱮ3,5¤      - "O-" mould like [3,5] = ["O-O", "O-O-O"]
                      ;     - concatenate
                       Y    - join with newline characters
                        F   - flatten
                         ḟ⁶ - filter out space characters
                            - implicit, smashing print
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Why is chess so hard? :D :D \$\endgroup\$ Commented Apr 15 at 16:54
3
\$\begingroup\$

Charcoal, 166 144 139 138 bytes

E35…O-IιF…β⁸F⁸F…β⁸F⁸«≔X⁻℅λ℅ι²θ≔X⁻μκ²η≔⁺θηζ¿ζ«E⎇⁼⁵ζN⁺…K‹ζ³⭆⁺…B⁼θη…R¬∧θη⁺νQ⪫⟦νι⊕κ-λ⊕μ⟧ω¿∧⁼μ⊕κ‹θ²¿κE⎇⁼μ⁷⁺=⪪NBRQ¹⟦ω⟧⪫⟦ι⊕κ§-xθλ⊕μν⟧ω¿¬θ⟦Σ⟦ι2-λ4

Try it online! Link is to verbose version of code. Explanation:

E35…O-Iι

Output O-O and O-O-O.

F…β⁸F⁸F…β⁸F⁸«

Loop over all pairs of starting and destination squares, with the ranks 0-indexed for now.

≔X⁻℅λ℅ι²θ≔X⁻μκ²η≔⁺θηζ¿ζ«

Get the squared differences in the ranks and files, and check that at least one is non-zero.

E⎇⁼⁵ζN⁺…K‹ζ³⭆⁺…B⁼θη…R¬∧θη⁺νQ⪫⟦νι⊕κ-λ⊕μ⟧ω

Check whether the knight, king, bishop, rook or queen can legally make that move, and if so output the move.

¿∧⁼μ⊕κ‹θ²

Check whether this might be a legal pawn move. (At this point we haven't checked for the pawn being on the back rank.)

¿κE⎇⁼μ⁷⁺=⪪NBRQ¹⟦ω⟧⪫⟦ι⊕κ§-xθλ⊕μν⟧ω

If the pawn is not on the back rank then output the pawn move, with any necessary promotion options.

¿¬θ⟦Σ⟦ι2-λ4

Otherwise if this is a plain move then output a doubled pawn move for this file.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 243 240 bytes

A full program, printing to stdout. Moves with an odd number of squares displaced left/right are shown as captures. Those with even (including zero) squares displaced left/right are shown as regular moves. This gives the correct output for pawns, and is allowed for other pieces according to the rules.

l=*?`..?h
[*0..4].product(*[[*1..8]]*4).map{|i|w,u,v,x,y=i
b=y-v;m="NBRQK"[w]
s=l[u]+"#{v}#{"-x"[1&u-=x]+l[x]}#{y}";u*=u
u>1||v<2||y>4-u&&b>1||b<1||w*2^y<8||p(s+"=#{m}"*y/=8)
[5-e=u+b*=b,q=u-b,r=u*b,q*r,e/3][w]**e==0&&p(m+s)}
p"O-O","O-O-O"

Try it online!

The program iterates through w=0..4 representing NBRQK and through u,v,x,y=1..8 representing the start and finish coordinates.

Each iteration prints the move for the relevant piece and coordinates if legal. 5 separate tests are run and the appropriate result (which must equal 0) is selected from an array indexed by w. This is raised to the power of the square of the euclidean distance e to eliminate cases where e is zero (start and finish coordinates equal) since any number raised to the power 0 is 1.

Before this, a separate line of code prints a pawn move if the coordinates are legal. For NBRQ only moves that result in promotion to that piece are printed. Moves that do not result in promotion are printed while w==4 representing K.

commented code

l=*?`..?h                                             #l=["`","a",..,"h"]
[*0..4].product(*[[*1..8]]*4).map{|i|w,u,v,x,y=i      #iterate w=0..4 and u,v,x,y=1..8  
b=y-v                                                 #b=vertical displacement
m="NBRQK"[w]                                          #select piece m

s=l[u]+"#{v}#{"-x"[1&u-=x]+l[x]}#{y}";u*=u            #s=string in format a1xb2 etc
                                                      #u becomes square of horizontal displacement
u>1||v<2||y>4-u&&b>1||b<1||w*2^y<8||p(s+"=#{m}"*y/=8) #if not disallowed print pawn move:
#u>1 horiontal move too far; v<2 on 1st rank; y>4-u&&b>1 too far forward; b<1 not forward 
#w*2^y<8 on rank 8 & piece=king or on rank 2-7 & not king. Promote "={NBQR}" if required 

[5-e=u+b*=b,q=u-b,r=u*b,q*r,e/3][w]**e==0&&p(m+s)     #if expression=0 print piece move:
#N squared euclidean distance e=5; B squares of horizontal and vertical distance u&b equal
#R a*b=0 implies u=0 or b=0; Q q*r=0 implies move is a valid bishop or rook move
#K e/3=0 implies e<3. Raise to power e to eliminate e=0 (since any number**0 = 1)  

}                                                     #close loop
p"O-O","O-O-O"                                        #print castling moves separately

Ruby, 255 253 251 247 bytes

An older version where pawn moves are shown as captures or regular moves as appropriate, and all other moves are shown as regular moves.

l=*?`..?h
[*0..4].product(*[[*1..8]]*4).map{|i|w,u,v,x,y=i
b=y-v;m="NBRQK"[w]
s="#{l[u]}#{v}%s#{l[x]}#{y}"
x-=u;x*=x
x>1||v<2||y>4-x&&b>1||b<1||w*2^y<8||p(s%"-x"[x]+"=#{m}"*y/=8)
[5-e=x+b*=b,q=x-b,r=x*b,q*r,e/3][w]**e==0&&p(m+s%?-)}
p"O-O","O-O-O"

Try it online!

\$\endgroup\$

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.