15
\$\begingroup\$

Alternate name: ChessMoveQ

Given a list of up to 32 elements, each consisting of 4 elements, and a second list with 4 elements, determine whether the move detailed in the second input is a valid chess move.

The first list indicates the position of all 32 pieces on the board. Each element will follow the structure <colour>, <piece-name>, <x-coord>, <y-coord>, such as ["W", "K", 5, 1], which indicates that the white king is on 5, 1 (e1 on a normal chess board). All elements of the first input will be unique. <x-coord> and <y-coord> will always be between 1 and 8. One example would be:

[["B", "K", 3, 8], ["B", "Q", 1, 5], ["B", "N", 4, 7], ["B", "N", 7, 8],
 ["B", "B", 2, 4], ["B", "R", 4, 8], ["B", "R", 8, 8], ["B", "P", 1, 7],
 ["B", "P", 2, 7], ["B", "P", 3, 6], ["B", "P", 5, 6], ["B", "P", 6, 7],
 ["B", "P", 7, 7], ["B", "P", 8, 7], ["W", "K", 5, 1], ["W", "Q", 6, 3],
 ["W", "N", 3, 3], ["W", "B", 5, 2], ["W", "B", 6, 4], ["W", "R", 1, 1],
 ["W", "R", 8, 1], ["W", "P", 1, 3], ["W", "P", 2, 2], ["W", "P", 3, 2],
 ["W", "P", 4, 4], ["W", "P", 6, 2], ["W", "P", 7, 2], ["W", "P", 8, 3]]

which would represent the board:

an example chessboard

The second input will consist of the same structures as the sublists of the first one, but rather than the x and y coordinates indicating where the piece is, they are indicating where it is trying to move to.

For the above example, a valid move could be ["W", "B", 4, 3] (bishop moves one square forward and to the left), and an invalid move could be ["B", "R", 4, 1] as the rook would have to move through the knight, and the pawn to get to the square. As the move could refer to multiple pieces at times, you must test whether any of the specified pieces can make the move, not just one of them. For instance, the first example is valid for only one bishop, but it is still a valid move. However, neither black rook can perform the second move, so it is invalid.

Your task is to determine whether the move detailed in the second input is a valid chess move. The validity of a rule varies, depending on the piece trying to move (click on the name of the piece for a diagram of valid moves):

  • Any piece: No pieces can move onto an already occupied square, or off the board, unless that square is occupied by a piece from the other colour. For example, a white piece may move onto a square occupied by a black piece, but not a white piece. Additionally, no pieces, except for Knights, can move to squares which are directly obstructed by another piece.
    • A move by piece B to square C is "directly obstructed" by piece A if A is directly, in a straight (orthogonal or diagonal) line, between B and C.
  • Any piece: The position of the king can also affect the validity of a piece's move. If either of these two conditions are met, the move is invalid:
    • Exposing the king to check, by moving a piece on the same side as the endangered king. This only applies if a non-opposing piece makes the move, rather than an opposing piece moving to place the king into check.
    • Leaving the king in check, in which case it has to move out of check. Therefore, if the king is in check and the move dictates that another piece moves, it is an invalid move, unless the other piece is preventing check. A piece can prevent check in one of two ways: either it takes the piece performing check, or it obstructs the path between the piece performing check and the king.
    • A "check" is a situation in which the king's opponent could (if it was their turn to move) legally move a piece onto that king. This rule does not apply recursively, i.e. a king is in check even if the move by the opponent onto that king would leave their own king in check.
  • Pawns: A pawn can move forwards (i.e. upwards if white, downwards if black) one square to an unoccupied square. There are also three special situations:
    • If the pawn hasn't yet moved (you can determine this using the Y-coordinate; white pawns haven't moved if their Y-coordinate is 2, black pawns haven't moved if their Y-coordinate is 7), the pawn is allowed to move two squares forward to an unoccupied square.
    • If there is an opponent's piece diagonally in front of the pawn (i.e. on the square to the north-west or north-east of the pawn if it is white, or to the south-west or south-east if it is black), the pawn is allowed to move onto the occupied square in question.
    • If a pawn moves to the final Y-coordinate (8 for white, or 1 for black) in normal chess rules it must be promoted to a queen, rook, knight, or bishop of the same color. For the purposes of this question, the choice of promotion is irrelevant to whether the move is valid or not (and cannot be expressed in the input format), but pawn moves that would result in promotion must be allowed.
  • Bishops: Bishops can move between 1 and 8 squares along any continuous non-obstructed intercardinal (i.e. diagonal) path.
  • Knights: Knights can move in an L shape, consisting of either of the following (equivalent) moves:
    • A single square in any cardinal direction, followed by a 90/270° turn, followed by a final move of 2 squares forward.
    • 2 squares in any cardinal direction, followed by a 90/270° turn, followed by a final move of a single square forward.
    (Remember that the path of a knight cannot be blocked by intervening pieces, although its final square must still be legal.)
  • Rooks: Rooks can move between 1 and 8 squares along any continuous non-obstructed cardinal path.
  • Queens: Queens can move between 1 and 8 squares along any continuous cardinal or intercardinal (i.e. diagonal) non-obstructed path.
  • Kings: Kings move like queens, except that they are limited to moving only one square per move (i.e. a king can only move to cardinally or diagonally adjacent squares). As a reminder, you cannot make a move that leaves your king in check; thus you cannot move your king into check, either.

The rules of chess also contain special moves called "castling" and "en passant". However, because the legality of these moves depend on the history of the game, not just the current position (and because castling requires moving two pieces at once, which doesn't fit with the input format), you should consider neither of these moves to exist (i.e. a move that would be castling or en passant should be considered illegal).

You may output any two distinct results to indicate the validity of a move, and you may take input in a method you want. You may also choose 0-indexing rather than 1-indexing for the positions if you prefer. This is a , so shortest code wins!

Test cases

Board
Move => Output (Reason)

[["B", "K", 3, 8], ["B", "Q", 1, 5], ["B", "N", 4, 7], ["B", "N", 7, 8], ["B", "B", 2, 4], ["B", "R", 4, 8], ["B", "R", 8, 8], ["B", "P", 1, 7], ["B", "P", 2, 7], ["B", "P", 3, 6], ["B", "P", 5, 6], ["B", "P", 6, 7], ["B", "P", 7, 7], ["B", "P", 8, 7], ["W", "K", 5, 1], ["W", "Q", 6, 3], ["W", "N", 3, 3], ["W", "B", 5, 2], ["W", "B", 6, 4], ["W", "R", 1, 1], ["W", "R", 8, 1], ["W", "P", 1, 3], ["W", "P", 2, 2], ["W", "P", 3, 2], ["W", "P", 4, 4], ["W", "P", 6, 2], ["W", "P", 7, 2], ["W", "P", 8, 3]]
["W", "R", 8, 2] => True (The rook on h1 can move forward one)

[['B', 'K', 6, 8], ['B', 'Q', 1, 7], ['B', 'N', 1, 3], ['B', 'N', 7, 1], ['B', 'B', 8, 8], ['B', 'B', 2, 5], ['B', 'R', 4, 3], ['B', 'R', 1, 5], ['B', 'P', 5, 5], ['B', 'P', 7, 2], ['B', 'P', 5, 7], ['B', 'P', 5, 6], ['B', 'P', 4, 4], ['W', 'K', 7, 3], ['W', 'Q', 3, 2], ['W', 'N', 4, 8], ['W', 'N', 7, 5], ['W', 'B', 1, 1], ['W', 'B', 8, 1], ['W', 'R', 1, 8], ['W', 'R', 3, 7], ['W', 'P', 8, 2], ['W', 'P', 6, 3], ['W', 'P', 4, 2], ['W', 'P', 1, 4], ['W', 'P', 8, 7]]
['W', 'N', 1, 5] => False (Neither knight to move to a5 from where they are)

[['B', 'K', 7, 3], ['B', 'Q', 2, 4], ['B', 'N', 5, 2], ['B', 'N', 1, 6], ['B', 'B', 7, 7], ['B', 'B', 1, 8], ['W', 'K', 7, 1], ['W', 'Q', 6, 1], ['W', 'N', 5, 6], ['W', 'N', 3, 3], ['W', 'B', 2, 2], ['W', 'B', 6, 5]]
['B', 'K', 8, 3] => False (The white bishop would put the king in check)

[['B', 'K', 7, 6], ['B', 'Q', 8, 3], ['B', 'N', 7, 7], ['B', 'N', 8, 7], ['B', 'B', 2, 2], ['B', 'B', 3, 8], ['B', 'R', 1, 1], ['B', 'R', 1, 6], ['B', 'P', 8, 5], ['B', 'P', 4, 3], ['B', 'P', 8, 6], ['W', 'K', 7, 8], ['W', 'Q', 7, 2], ['W', 'N', 5, 1], ['W', 'N', 4, 6], ['W', 'B', 1, 2], ['W', 'B', 2, 6], ['W', 'R', 4, 4], ['W', 'R', 3, 6], ['W', 'P', 5, 2], ['W', 'P', 6, 2]]
['B', 'N', 5, 8] => False (The white queen currently has the king in check, and this move doesn't prevent that)

[['B', 'K', 7, 6], ['B', 'Q', 8, 3], ['B', 'N', 7, 7], ['B', 'N', 8, 7], ['B', 'B', 2, 2], ['B', 'B', 3, 8], ['B', 'R', 1, 1], ['B', 'R', 1, 6], ['B', 'P', 8, 5], ['B', 'P', 4, 3], ['B', 'P', 8, 6], ['W', 'K', 7, 8], ['W', 'Q', 7, 2], ['W', 'N', 5, 1], ['W', 'N', 4, 6], ['W', 'B', 1, 2], ['W', 'B', 2, 6], ['W', 'R', 4, 4], ['W', 'R', 3, 6], ['W', 'P', 5, 2], ['W', 'P', 6, 2]]
['B', 'N', 7, 5] => True (The king is in check, and the knight blocks that)

[['B', 'K', 8, 3], ['B', 'Q', 6, 5], ['B', 'N', 7, 8], ['B', 'N', 3, 7], ['B', 'B', 4, 1], ['B', 'B', 1, 1], ['W', 'K', 7, 7], ['W', 'Q', 7, 1], ['W', 'N', 2, 2], ['W', 'N', 1, 3], ['W', 'B', 3, 5]]
['B', 'B', 2, 2] => True (takes the white knight)

[['B', 'K', 6, 1], ['B', 'Q', 6, 2], ['W', 'K', 8, 1]]
['B', 'Q', 7, 1] => True (Smallest checkmate possible, in terms of bounding box)

This challenge was sandboxed. It received downvotes, without any explanation, so I decided to post it anyway

\$\endgroup\$
  • \$\begingroup\$ "A piece on the same side moves, exposing the king to check." - this wording doesn't seem to fit now that you've moved the heading it goes under. I'd change it to something such as "Moving this piece will expose the king to check" \$\endgroup\$ – FlipTack Nov 19 '17 at 18:49
  • \$\begingroup\$ This question was downvoted in the Sandbox, and now here without a single explanation. There is nothing I can do to make you tell me why you downvoted, but at least have the decency to explain your actions, rather than standing silent in the shadows. If you think this post can be improved, please suggest how, rather than taking a pot shot without explaining yourself. \$\endgroup\$ – caird coinheringaahing Nov 19 '17 at 18:50
  • 2
    \$\begingroup\$ Nobody's downvoted it...? \$\endgroup\$ – FlipTack Nov 19 '17 at 18:50
  • 1
    \$\begingroup\$ Can we get a 2d array of pieces as input? \$\endgroup\$ – ovs Nov 21 '17 at 18:36
  • 1
    \$\begingroup\$ @ovs Yes, that seems to be acceptable \$\endgroup\$ – caird coinheringaahing Nov 21 '17 at 18:43
3
\$\begingroup\$

Python 2 (with python-chess),  141 138 134 133  132 bytes

Without doing any of the really interesting code - but maybe this can compete with golfing languages or (dare I mention it) Mathematica?

Note: python-chess is a Pypi package install it on Python 2.7.9+ with:
python -m pip install python-chess)

import chess
a,p,n=input()
S=chess.Board(a+' - - 0 1')
for m in S.legal_moves:1/(m.to_square!=n)**(`p`in`S.piece_at(m.from_square)`)

A full-program accepting input of three items:

  1. the beginning of a FEN record - the string containing the first two fields. This is to define the board state AND which colour is moving (since this is the information in the input in the OP, whereas fields three through six are "fixed" by the OP hence should not be a part of the input)
  2. the piece-name attempting to move (as given in the OP -- one of PRNBQK)
  3. the square to which the named piece is attempting to move where a1 is 0, b1 is 1, ... a2 is 8, ..., h8 is 63,

The program outputs via its exit-code given valid input:

  • 1 if the move is a valid one (the program raised an error - due to division by zero);
  • 0 it it is not (the program exited normally)

(Don't) Try it online! (because the python-chess package is not installed there and TIO does not allow internet connectivity so the pip-install code in the header wont work).

Note that the power operator in Python makes 1**1 == 1**0 == 0**0 == 1 but 0**1 == 0
...hence 1/0**1 raises a division by zero error while 1/1**1, 1/1**0, and 1/0**0 all succeed
(...and that in Python False and True equate to 0 and 1 respectively).

\$\endgroup\$
  • 2
    \$\begingroup\$ It's a perfectly valid answer, but it feels a little like cheating, similar to a builtin-only Mathematica answer. \$\endgroup\$ – caird coinheringaahing Nov 19 '17 at 22:13
  • \$\begingroup\$ Yes, hence the comment I put at the top "Without doing any of the really interesting code..." maybe when I have some more time I'll do a Jelly one (which cannot import this module :)) \$\endgroup\$ – Jonathan Allan Nov 19 '17 at 22:14
  • 1
    \$\begingroup\$ ...mind you it still took some effort. \$\endgroup\$ – Jonathan Allan Nov 19 '17 at 22:15
  • \$\begingroup\$ Rearrange str(S.piece_at(m.from_square))==p for to p==str(S.piece_at(m.from_square))for, that should save one byte. \$\endgroup\$ – Zacharý Nov 19 '17 at 22:19
  • \$\begingroup\$ Ah, yes - thanks @Zacharý I was just looking to see if I could parse from the repr using backticks to replace str to save... \$\endgroup\$ – Jonathan Allan Nov 19 '17 at 22:21
3
\$\begingroup\$

Regex (PCRE2), 931 925 837 bytes

This solution departs from the problem statement in that two board states are passed to the regex, instead of one board state and a move. The move is inferred from the difference between the two board states. So I made it the job of the TIO program to take the test cases in the format provided by this question, find all instances of the described piece on the board, and with each one, try moving it to the destination position and evaluating the regex with that possibility, finding if any are reported by the regex as valid. If this is not okay, let me know; it's possible to implement a regex as position + move, but would be much less elegant and require serious refactoring.

The board is represented in 8×8 ASCII where white pieces are uppercase and black are lowercase: Pawn, kNight, Bishop, Rook, Queen, King. Black's side (the 8th rank) is on the top and white's side (the 1st rank) is on the bottom. Each rank is separated by a newline, and empty squares are marked as -. The two board positions are separated by an extra newline.

The actual aim of this project is to validate entire games, not just single moves. See below for the current state of progress.

()?(?>|((.|
(?=.)){2})((?=(\X{72})-))((?=(?(1)[-a-z]|[-A-Z])))((?5)(?(?=(.*
)
)[qnrb]|p))((?5)(?(?=(?8){8}
)[QNRB]|P)))(?>((.)(?=(?5)\11)|(?(m)$)((?(1)(-(?=(?9))(?=(?3){8}((?3){9})?P(?4))(?(-1)(?=(?8){4}
))|[a-z](?=(?9))(?=(?3){7}(?2)?P(?4)))|(p(?4)((?=(?3){8}((?3){9})?-(?7))(?(-1)(?=(?8){7}
))|(?=(?3){7}(?2)?[A-Z](?7)))))|(?<e>(?6).)?(?=(?i:(?|(?(e)|(B|Q))(?27)(?(e)(B|Q))|(?(e)|(R|Q))(?31)(?(e)(R|Q))|(?(e)|(N))(?34)(?(e)(N))|(?(e)|(K))(?35)?(?(e)(K))))(?(e)(?<=(?!(?6)).)(?4)|(?6).(?5)\19))(?(e)(?=(?5)\20)|(?!(?6)).(?4)))(?<m>)|(?(+1)$)(.))+
)+\k<m>
(?!\X{0,70}((?(1)p|k)(?=(?3){7}(?2)?(?(1)K|P))|(?i:(?<E>(?!(?6))K)?((?(E)|((?6)[BQ]))(()?((?(-1)-)(?3){7}(?(-2)(?2)))+)(?(E)(?-4))|(?(E)|((?6)[RQ]))(-*|((?(-1)-)(?3){8})+)(?(E)(?-3))|(?(E)|((?6)N))((?<=..)(?2){3}|(?=.)(?2){5}|(?2){8}(?2)?)(?(E)(?-2)))(?(E)|(?&E))|K((?3){7,9})?K)))

Try it online!

Pretty-printed, and partially ungolfed (absolute backrefs changed to relative, and capturing groups changed to non-capturing, or in some cases atomic for speed):

# Chess move validation regex (PCRE)
()?                 # decide whether to evaluate this as white's or black's move; \1 set = white, \1 unset (NPCG) = black
(?>|                # subroutines:
  ((.|\n(?=.)){2})                  # (?3) = for moving within the board, without wrapping to the next board, (?2) = (?3){2}
  ((?=                              # (?4) = assert that position of just-consumed piece is vacated on the next turn
    (\X{72})                        # (?5) = skip to the position of the just-consumed piece on the next turn
  -))
  ((?=(?(1)[-a-z]|[-A-Z])))         # (?6) = assert that the piece at the current position belongs to the current player's opponent or is empty
  ((?5)(?(?=(.*\n)\n)[qnrb]|p))     # (?7) = black pawn that might be promoted, (?8) = .*\n
  ((?5)(?(?=(?8){8}\n)[QNRB]|P))    # (?9) = white pawn that might be promoted
)
(?>
  (?>
    # Handle squares that don't change (empty->empty or pieces that doesn't move)
    (.)(?=(?5)\g{-1}) |
    # Handle a piece that moves (and optionally captures an enemy piece)
    (?(m)$)  # allow only one move to be made per turn
    (?>
      (?(1)
        (?:                                                         # white pawn
            -  (?=(?9))(?=(?3){8}((?3){9})?P(?4))(?(-1)(?=(?8){4}\n)) |   # move 1 or 2 spaces forward
          [a-z](?=(?9))(?=(?3){7}(?2)?     P(?4))                     )   # capture diagonally
      |
        (?:p(?4)(?:                                                 # black pawn
          (?=(?3){8}((?3){9})?  -  (?7))(?(-1)(?=(?8){7}\n)) |            # move 1 or 2 spaces forward
          (?=(?3){7}(?2)?     [A-Z](?7)) )                   )            # capture diagonally
      ) |
      # bishops, rooks, queens, knights, or kings
      (?<e>(?6).)?   # decide between scanning forward (<e> is unset) or backwards (<e> is captured)
      (?=
        (?i:
          (?|
            (?(e)|(B|Q)) (?&B)  (?(e)(B|Q)) | # bishops or queens
            (?(e)|(R|Q)) (?&R)  (?(e)(R|Q)) | # rooks or queens
            (?(e)|(N  )) (?&N)  (?(e)(N  )) | # knights
            (?(e)|(K  )) (?&K)? (?(e)(K  ))   # kings
          )
        )
        (?(e)(?<=(?!(?6)).)(?4)|(?6).(?5)\g{-2})   # verify that the piece moved, and optionally captured piece, are of the correct color
      )
      (?(e)(?=(?5)\g{-1})|(?!(?6)).(?4))   # verify that the piece moved is the same type and color at its destination in the next turn's board position
    )(?<m>) |
    (?(+1)$)(.)  # handle the destination/source square that a piece moved to/from (only allow matching one of these per turn)
  )+\n
)+
\k<m>         # assert that a move has taken place
\n
# don't allow moving into check  
(?!
  \X{0,70}
  (?:
    # pawns (capture diagonally)
    (?(1)p|k)(?=(?3){7}(?2)?(?(1)K|P)) |
    # bishops, rooks, queens, knights, or kings
    (?i:
      (?<E>(?!(?6))K)?   # decide between scanning forward (<E> is unset) or backwards (<E> is captured)
      (?:
        (?(E)|((?6)[BQ])) (?<B>()?((?(-1)-)(?3){7}(?(-2)(?2)))+)         (?(E)(?-4)) | # bishops or queens
        (?(E)|((?6)[RQ])) (?<R>-*|((?(-1)-)(?3){8})+)                    (?(E)(?-3)) | # rooks or queens
        (?(E)|((?6) N  )) (?<N>(?<=..)(?2){3}|(?=.)(?2){5}|(?2){8}(?2)?) (?(E)(?-2))   # knights
      )
      (?(E)|(?&E)) |
      K(?<K>(?3){7,9})?K   # kings
    )
  )
)

-88 bytes by using non-atomic subroutine calls, thus retargeting from PCRE1 to PCRE2

The version above has been modified not to allow en passant or castling, but the full project is currently at a state where it validates every type of move, starting at the initial board state (which must be the standard chess starting position – Chess960 is not supported, yet at least). The full rules of en passant and castling are enforced.

Here is a sample game validated by the full regex (PCRE1 – not yet retargeted) [regex101.com].

An invalid move will result in every subsequent board position not being matched/highlighted. Checkmate/stalemate detection, and thus detection of who the winner is (or if it's a draw), is not yet implemented; that's why the final board state in this example is not highlighted.

Here is a C/C++ program that converts algebraic notation into the format recognized by this regex. The algebraic notation currently must be put in the form of an array inline in the source code, with separate strings for each move, but reading it as single string from stdin or a command-line argument, with the entire sequence of moves separated by spaces and dot-terminated move numbers, is planned.

I also started on a regex that validates a full game purely in algebraic chess notation, with the standard initial position being implied. All it needs is an empty "scratch board" appended at the end of the input (after the list of moves). I'm pretty sure it's possible to implement this in full, and plan on finishing it sometime.

\$\endgroup\$
  • \$\begingroup\$ I haven't been filled with this much dread since the time I coughed up a 3000-byte regex monstrosity for a Sudoku validation question (a massive mistake, considering the winning answer got it in less than 75). Truly proves the point that sometimes when you use regex to solve a problem, you end up with two problems \$\endgroup\$ – Value Ink Dec 25 '19 at 2:31
  • \$\begingroup\$ @ValueInk Heh, maybe you're right, but I enjoy it regardless of (or maybe because of) its utter impracticality. Your comment inspired me to attempt answering that Sudoku question, but I only managed 200 bytes. Oh well. \$\endgroup\$ – Deadcode Dec 25 '19 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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