25
\$\begingroup\$

Not a duplicate of the valid move challenge because that asks for specific pieces.

Backstory

The other night I was doing a little trolling with ChatGPT and chess. I was trying to get it to call me out for making illegal moves, as a lot of the time, you can feed it whatever nonsense you want. While doing so, I wondered if it didn't recognise invalid moves because they were technically valid under some board arrangement. I then thought I'd make a code golf challenge.

The Challenge

Given a start and end square on an 8x8 chess board, determine whether the move is possible on any legal chess board.

Alternatively, can any kind of piece make a move from the start square to the end square.

Chess Pieces

For this challenge, you only need to know how the knight and queen move. King and pawn moves can be considered equivalent to a queen moving a single square. A rook move is a queen move restricted to vertical and horizontal movement. A bishop move is a queen move restricted to diagonal movement. Castling and En Passant (holy hell) aren't relevant either.

A valid move from the square highlighted in red is any square marked with a green circle:

This includes the vertical, horizontal and diagonal movement of the queen, as well as the L-shaped movement of the knight.

Rules

  • The positions will be given in algebraic chess notation (letter then number of the square).
  • The start and end squares will never be the same square.
  • The start and end squares will always be valid squares on an 8x8 chess board.
  • Positions can be given in any reasonable and convenient format, including:
    • Strings (e.g. ["f4", "b8"])
    • A list of strings (e.g. [["f", "4"], ["b", "8"]])
    • A list of numbers that represent the character codes of each string item (e.g. [[102, 52], [98, 56]])
    • A string, number pairs (e.g. [["f", 4], ["b", 8]])
    • A list of row/column pairs (e.g [[5, 3], [1, 7]] OR [[6, 4], [2, 8]]). Can be 0-indexed or 1-indexed. Your choice.
  • Output in any reasonable and convenient format.
  • This is , so make sure your answer is as short as possible.

Test Cases

start, end -> plausible?
a1, a4 -> True
b2, d3 -> True
b2, e3 -> False
b2, c3 -> True
a1, h8 -> True
c7, g3 -> True
c7, g2 -> False
\$\endgroup\$
1
  • 8
    \$\begingroup\$ Alternately: Is it a valid move for an amazon? \$\endgroup\$
    – DLosc
    Apr 20, 2023 at 21:34

16 Answers 16

15
\$\begingroup\$

Octave, 24 bytes

@(a,b)imag((a-b)**4)<28i

Try it online!

Takes two complex numbers as inputs.

How?

Port of @xnor's python answer plus a trick or two by myself.

Trick 1:

@xnor's test polynomial a^3b-b^3a times 4i is the imaginary part of (a+ib)^4 = a^4 + 4i a^3b - 6a^2b^2 - 4i ab^3 + b^4

Note: a and b here as defined in @xnor's code; in my code they have a slightly different meaning.

Trick 2:

Octave implicitly takes absolute values before comparing complex numbers. We abuse that by comparing to 28i instead of 28 to save an explicit call to abs.

\$\endgroup\$
15
+300
\$\begingroup\$

Python 2, 29 bytes

lambda a,b:abs((a-b)**4%1)<28

Try it online!

Based on @xnor's answer. Takes two complex numbers as input.

Python 2, 42 bytes

lambda x,y,X,Y:abs((X-x+1j*(Y-y))**4%1)<28

Try it online!

The same with less opportunistic input format (4 integers).

How?

Recall that in polar coordinates complex multiplication adds angles.

Therefore all queen-like moves (and only those) when taken to 4th power will end up on the real axis, i.e. have vanishing imaginary part.

Explicitly, if the difference of source and destination is \$x+yi\$ then the imaginary part of its fourth power is \$4 \times \left( x^3y - x y^3\right)\$ which happens to be @xnor's test polynomial (up to the prefactor 4). As observed by @xnor this has absolute value (4x) 6 at knight's moves and greater for all other (non-queen) moves.

Implementation detail: In Python 2 but not 3 the imaginary part can be isolated by %1.

\$\endgroup\$
0
12
\$\begingroup\$

Python 3, 47 bytes

lambda x,y,X,Y:-7<(a:=X-x)*(b:=Y-y)*(a*a-b*b)<7

Try it online!

Test cases from mousetail.

Python 2, 49 bytes

lambda x,y,X,Y:-7<(X-x)**3*(Y-y)-(X-x)*(Y-y)**3<7

Try it online!

No walrus here.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Python 2 42 without typo \$\endgroup\$
    – loopy walt
    Apr 20, 2023 at 23:39
  • 4
    \$\begingroup\$ 29 if input complex numbers \$\endgroup\$
    – loopy walt
    Apr 21, 2023 at 1:27
  • 2
    \$\begingroup\$ @loopywalt What a clever use of complex numbers! I think you deserve to have your own answer with these. \$\endgroup\$
    – xnor
    Apr 21, 2023 at 6:11
  • \$\begingroup\$ @loopywalt I guess %1 is specific to Python 2's complex numbers? \$\endgroup\$
    – Neil
    Apr 21, 2023 at 7:44
  • \$\begingroup\$ @Neil Yes that's correct. \$\endgroup\$
    – loopy walt
    Apr 21, 2023 at 13:09
8
\$\begingroup\$

05AB1E, 12 8 bytes

αDËsP3‹~

-4 bytes porting AndrovT's Vyxal answer.

Input as two pairs of codepoints.

Try it online or verify all test cases or verify every single pair of chessboard positions.

Original 12 bytes answer:
Port of @Arnauld's JavaScript answer.

αW_snDO5QsËM

Input as two pairs of codepoints.

Try it online or verify all test cases or verify every single pair of chessboard positions.

Explanation:

              #  first input ("f4"): [102,52]; second input ("b8"): [98,56]
α             # Absolute difference of the values in the two (implicit) input-pairs
              #  [abs(98-102),abs(56-52)] → STACK: [4,4]
 D            # Duplicate the pair
              #  STACK: [4,4],[4,4]
  Ë           # Check if the values in the pair are the same
              #  STACK: [4,4],1
   s          # Swap so the pair is at the top of the stack again
              #  STACK: 1,[4,4]
    P         # Take the product of the pair
              #  STACK: 1,16
     3‹       # Check whether this is smaller than 3 (thus 0, 1 or 2)
              #  STACK: 1,0
       ~      # Bitwise-OR to check either of the two is truthy
              #  STACK: 1
              # (after which the top of the stack is output implicitly as result)
              #  first input ("f4"): [102,52]; second input ("b8"): [98,56]
α             # Absolute difference of the values in the two (implicit) input-pairs
              #  [abs(98-102),abs(56-52)] → STACK: [4,4]
 W            # Get the minimum (without popping)
              #  STACK: [4,4],4
  _           # Check if this minimum is 0 (1 if 0; 0 otherwise)
              #  STACK: [4,4],0
   s          # Swap so the earlier pair is at the top again
              #  STACK: 0,[4,4]
    n         # Take the square of both values
              #  STACK: 0,[16,16]
     D        # Duplicate this pair
              #  STACK: 0,[16,16],[16,16]
      O       # Sum the copy
              #  STACK: 0,[16,16],32
       5Q     # Check whether this sum is equal to 5 (1 if 5; 0 otherwise)
              #  STACK: 0,[16,16],0
         s    # Swap so the earlier squared pair is at the top again
              #  STACK: 0,0,[16,16]
          Ë   # Check whether both values in the pair are the same
              #  STACK: 0,0,1
           M  # Push the largest value on the stack, to check if any is truthy
              #  STACK: 0,0,1,1
              # (after which the top of the stack is output implicitly as result)
\$\endgroup\$
8
\$\begingroup\$

JavaScript (ES6), 42 bytes

Expects (x0,y0,x1,y1), where all arguments are integers. They can be 0-indexed coordinates, 1-indexed coordinates or ASCII codes.

Returns a Boolean value.

(x,y,X,Y)=>!((x-=X)*x+(y-=Y)*y-5&&x/y^y/x)

Try it online!

Commented

(                //
  x, y,          // (x, y) = coordinates of source square
  X, Y           // (X, Y) = coordinates of target square
) =>             //
!(               //
  (x -= X) * x + // we compute x = x - X and y = y - Y
  (y -= Y) * y   // if the squared Euclidean distance x² + y²
  - 5            // is not equal to 5, this is not a knight move
  &&             //
  x / y ^ y / x  // we compute x / y and y / x
                 // XOR'ing both terms together gives 0 if:
                 // - either x = 0 or y = 0 (rook move), in which case one
                 //   of the terms is ±infinity and the other one is 0
                 //   (see note below)
                 // - x = ±y (bishop move), in which case both terms are
)                //   equal

Note

According to the ECMAScript specification of NumberBitwiseOp(op, x, y), the arguments of a bitwise operation are first converted with the abstract operation ToInt32(argument) whose first two steps are:

  1. Let number be ? ToNumber(argument).
  2. If number is \$\text{NaN}\$, \$+0_\mathbb{F}\$, \$-0_\mathbb{F}\$, \$+\infty_\mathbb{F}\$, or \$-\infty_\mathbb{F}\$, return \$+0_\mathbb{F}\$.

That's why ±infinity ^ 0 is 0.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ What are the JavaScript semantics for XOR of floats? Convert to int32 like other bitwise ops? How does +-Infinity convert to integer? (I know I could look this up or try it, but it's very hacky and non-obvious (and language-specific) to do Infinity XOR 0, and seems like something that would make sense to include in the explanation. Perhaps as text outside the code block.) \$\endgroup\$ Apr 21, 2023 at 7:07
  • 1
    \$\begingroup\$ @PeterCordes I've added the relevant snippet from the ECMAScript spec. \$\endgroup\$
    – Arnauld
    Apr 21, 2023 at 21:20
7
\$\begingroup\$

Vyxal, 7 6 bytes

εꜝ2v∴≈

Try it Online!

-1 byte by @Johnathan Allan

Takes input as two pairs of numbers.

εꜝ2v∴≈
ε      # absolute difference
 ꜝ     # keep truthy
  2v∴  # vectorized maximum with 2
     ≈ # are all equal?
\$\endgroup\$
1
  • \$\begingroup\$ Porting my Jelly answer gets you a six, same idea with a slightly different implementation - try it \$\endgroup\$ Apr 21, 2023 at 20:58
5
\$\begingroup\$

T-SQL, 63 bytes

input is a table

SELECT 1/~((a-c)*(b-d)/3*(a-c)*(b-d)*(abs(a-c)-abs(b-d)))FROM @

Try it online

\$\endgroup\$
4
\$\begingroup\$

Jelly, 6 bytes

ạḟ0»2E

A dyadic Link that accepts one cell reference on the left and the other on the right, each as a pair of integers* and yields 1 if plausible or 0 if not.

* The indexing of the inputs does not matter so long as it is unscaled and the two pairs use consistent indexing; they could also be the ordinals of the characters (since only files and ranks, individually, need to have equivalent indexing).

Try it online! Or see the test-suite.

How?

ạḟ0»2E - Link: A=[StartRow, StartFile]; B=[EndRow, EndFile]
ạ      - absolute difference (vectorises)
           -> [abs(StartRow-EndRow), abs(StartFile-EndFile)]
 ḟ0    - filter out zeros -- remove the zero from any rook move
   »2  - max with two (vectorises) -- cast king/horsey moves to 2 step queen moves
     E - all equal? -- are we left with a queen move, or < 2 elements (was a rook)?
\$\endgroup\$
3
\$\begingroup\$

Excel, 77 72 bytes

=LET(
    a,INDIRECT(A1&":"&B1),
    b,ROWS(a),
    c,COLUMNS(a),
    OR(b=1,c=1,b=c,b*c=6)
)

Expects strings (e.g. "f4", "b8") in cells A1 and B1. Returns a Boolean.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 23 bytes

F²⊞υNUMυ↔⁻ιN⊞υ↔↨υ±¹‹Πυ³

Try it online! Link is to verbose version of code. Takes input as four integers and outputs a Charcoal boolean, i.e. - for plausible, nothing if not. Explanation: Inspired by @xnor's Python answer.

F²⊞υN

Input the first pair of coordinates.

UMυ↔⁻ιN

Take the absolute difference of them and the second pair of coordinates.

⊞υ↔↨υ±¹

Push the absolute difference of the two absolute differences.

‹Πυ³

Test whether the product is less than 3.

22 bytes with some evaluate hackery to port @loopywalt's Octave answer:

‹↔UV⁺X↨E⁴NUV1j⁴.imag²⁵

Try it online! Link is to verbose version of code. Takes input as four integers and outputs a Charcoal boolean, i.e. - for plausible, nothing if not. Explanation:

        ⁴               Literal integer `4`
       E                Map over implicit range
         N              Next input number
      ↨                  Interpret as base
             1j          Literal string `1j`
           UV            Evaluate as Python
     X                  Raised to power
              ⁴         Literal integer `4`
    ⁺                   Concatenated with
               .imag    Literal string `.imag`
  UV                    Evaluate as Python
 ↔                      Absolute value
‹                       Is less than
                    ²⁵  Literal integer `25`
                        Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 67 bytes

(.)(.)(.)(.)
$1$*1-$3$*1,$2$*1-$4$*
(1+)-\1

^1..1$|^(1+),\1$|^,|,$

Try it online! Takes input as a string of four digits but test suite converts from test case format for convenience. Explanation:

(.)(.)(.)(.)
$1$*1-$3$*1,$2$*1-$4$*

Convert to unary, preparing to subtract the x and y coordinates from each other.

(1+)-\1

Take the absolute difference of both the x and y coordinates.

^1..1$|^(1+),\1$|^,|,$

Match either a knight move, a bishop move, or one of two possible rook moves.

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

Python, 78 73 bytes

lambda i,j:((a:=abs(i[0]-j[0]))==(b:=abs(i[1]-j[1])))|(a<1)|(b<1)|(a<3>b)

Attempt This Online!

Python, 65 bytes

Alternate input format, credit to 97.100.97.109

lambda u,v,x,y:((a:=abs(u-x))==(b:=abs(v-y)))|(a<1)|(b<1)|(a<3>b)

Attempt This Online!

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

Thunno 2, 9 bytes

-ADạsp2©|

Port of AndrovT's Vyxal answer.

Explanation

-ADạsp2©|  # Implicit input
-A         # Absolute difference
  D        # Duplicate
   ạ       # All are equal?
    s      # Swap
     p     # Product
      2©   # Less than or equal to 2
        |  # Logical or
           # Implicit output
\$\endgroup\$
2
\$\begingroup\$

Scala, 237 221 bytes

Saved 16 bytes thanks to the comment.

Golfed version. Try it online!

type S=String
type I=Int
def f(a:S,b:S)={def s(s:S)={(s(0).toInt-'a'.toInt,8-s(1).asDigit)};def v(x:I,y:I,c:I,d:I)={val xD=x-c;val yD=y-d;xD*xD+yD*yD==5||xD==0||yD==0||xD*xD==yD*yD};val(x,y)=s(a);val(c,d)=s(b);v(x,y,c,d)}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val testCases = List(
      ("a1", "a4"), // True
      ("b2", "d3"), // True
      ("b2", "e3"), // False
      ("b2", "c3"), // True
      ("a1", "h8"), // True
      ("c7", "g3"), // True
      ("c7", "g2")  // False
    )

    testCases.foreach { case (a, b) =>
      val (x1, y1) = squareCoordinates(a)
      val (x2, y2) = squareCoordinates(b)
      println(s"$a $b ${isValidMove(x1, y1, x2, y2)}")
    }
  }

  def squareCoordinates(s: String): (Int, Int) = {
    (s(0).toInt - 'a'.toInt, 8 - s(1).asDigit)
  }

  def isValidMove(x1: Int, y1: Int, x2: Int, y2: Int): Boolean = {
    val xDiff = x1 - x2
    val yDiff = y1 - y2
    xDiff * xDiff + yDiff * yDiff == 5 || xDiff == 0 || yDiff == 0 || xDiff * xDiff == yDiff * yDiff
  }
}

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You could save bytes by making your variables x1,y1,x2,y2,xD,yD one letter \$\endgroup\$
    – The Thonnu
    Apr 20, 2023 at 16:16
2
\$\begingroup\$

J, 17 15 14 bytes

[:(=+.3>*)/|@-

Try it online!

Port of Neil's Charcoal / xnor's Python answers

Also -1 thanks to an idea from AndrovT's answer

J, original, 21 bytes

1 e.(*:^:4@*,5=|*|)@-

Try it online!

5 idea from Arnauld's answer

For the rest, we take the difference between in the inputs as complex numbers, normalize the vector, then square it 4 times. If the original vector was on one of the compass directions (rook) or one of the diagonals (queen/bishop), it will eventually settle at 1.

We then check if the result is 1 or 5.

\$\endgroup\$
1
\$\begingroup\$

Nekomata + -e, 7 bytes

-AZ‼2M≡

Attempt This Online!

A port of @Jonathan Allan's Jelly answer.

-AZ‼2M≡
-A          Absolute difference
  Z‼        Remove zeros
    2M      Max with 2
      ≡     All equal?
\$\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.