Is it a chess cycle?

Question

Inspired by a discussion from the Esolangs.org unofficial Discord Server.

Instructions

A chess cycle is an arrangement of a chess board where each piece must attack one other piece, and only one other piece, and each piece is attacked exactly once.

The effective idea to to "connect" pieces with each other, forming a single cyclic chain. Here is a board example:

You will only be given boards with Knights, Rooks and Bishops.

Your submission must take a chess board in any valid format(string, list of strings, 2D array, list of piece positions, FEN, ...) and output a truthy or falsy value for whether the board represents a valid cycle or not.

Testcases

To create your own testcases, create your board here, copy the FEN box contents, and use as input here.

FEN: 8/2B5/8/1N6/5N2/3B4/8/8, lichess

Board:

........
..B.....
........
.N......
.....N..
...B....
........
........

Output: True (In the illustration)

---

FEN: 8/8/8/3R4/8/8/8/8, lichess

Board:

........
........
........
...R....
........
........
........
........

Output: False (Rook cannot attack self)

---

FEN: 1R4B1/3N4/3N4/3N1B2/8/2B2N2/4R1BB/R1N5, lichess

Board:

.R....B.
...N....
...N....
...N.B..
........
..B..N..
....R.BB
R.N.....

Output: True

---

FEN: 6B1/4N2N/5B2/8/8/6B1/4N2N/5B2, lichess

Board:

......B.
....N..N
.....B..
........
........
......B.
....N..N
.....B..

Output: False (Multiple Cycles)

---

FEN: 8/6R1/8/5R1N/3N4/8/5BB1/7N, lichess

Board:

........
......R.
........
.....R.N
...N....
........
.....BB.
.......N

Output: False (Rook on f5 attacks two pieces)

---

FEN: 8/8/8/8/8/8/8/8, lichess(tsh)

Board:

........
........
........
........
........
........
........
........

Output: False (No pieces for a cycle)

---

FEN: 8/8/8/2R2R2/8/8/8/8, lichess(tsh)

Board:

........
........
........
..R..R..
........
........
........
........

Output: True (Two connected rooks, single cycle)

---

FEN: 8/8/8/1R3B2/8/3R2N1/8/8, lichess(Robin Ryder)

Board:

........
........
........
.R...B..
........
...R..N.
........
........

Output: False

Other Info

• You may represent the pieces and empty squares as any number or character, as long as it is consistent.
• Given boards will always be 8x8 and valid i.e. not containing any invalid characters.

Answer 1

Wolfram Language, 259 bytes

o=DirectedEdges->True
i|->RelationGraph[(d=Abs[#1[[2]]-#2[[2]]];#1!=#2&&NoneTrue[i,RegionMember[Line[p={#1[[2]],#2[[2]]}]~RegionDifference~Point@p]@*Last]&&Switch[#1[[1]],r,Times@@d==0,b,Equal@@d,n,Sort@d=={1,2}])&,i,o]~IsomorphicGraphQ~CycleGraph[Length@i,o]

Try it online!

(uses \[Function] rather than |->, as TIO doesn't have the most recent version of the language)

Defines a function that takes in a list of piece positions as input, each in the form {piece, {row, column}} where piece is one of r, b, or n.

Un-golfed explanation:

i|->
IsomorphicGraphQ[                (*check if the following graphs are equivalent*)
  CycleGraph[Length[i], DirectedEdges -> True],
                                 (*cyclic graph with length of input*)
  RelationGraph[                 (*graph defined by a functional relation*)
    (d = Abs[#1[[2]] - #2[[2]]]; (*set `d` to absolute difference in coordinates*)
    #1 != #2 &&                  (*no pieces attack themselves*)
    NoneTrue[i,                  (*no other pieces are...*)
      RegionMember[RegionDifference[Line[p = {#1[[2]], #2[[2]]}], Point[p]]] @* Last
    ] &&                         (*between these two pieces*)
    Switch[First @ #1,           (*switch by attacking piece*)
      r, Times @@ d == 0,        (*rooks attack when one coordinate offset is zero*)
      b, Equal @@ d,             (*bishops attack when both offsets are equal*)
      n, Sort[d] == {1, 2}]      (*knights attack when one offset is 1 and the other is 2*)
    )&, i, DirectedEdges->True], (*apply to list of pieces*)
]&

Answer 2

JavaScript (ES6), 241 bytes

Expects a list of triplets (x,y,p), where \$(x,y)\$ are the coordinates of the piece and \$p\$ is its type (\$0\$, \$1\$ or \$2\$ for bishop, knight or rook respectively).

Returns \$0\$ or \$1\$.

a=>(g=(i,n,k)=>i>=0?m^(m|=1<<i)?a.map(([X,Y],j)=>(h=([x,y,t]=a[i],X-=x)*X)|(v=(Y-=y)*Y)&&![h-v,h+v-5,h*v][t]&a.every(([p,q])=>(S=Math.sign)(p-=x)-S(X)|S(q-=y)-S(Y)|(p*=p)+(q*=q)<1|[p-q,1][t]|p>=h&q>=v)?k=1/k?-1:j:0)|g(k,-~n):!i&!a[n]:0)(m=0)

Try it online!

How?

Algorithm

We recursively walk through the input list of \$N\$ entries by going from a piece \$A\$ to a piece \$B\$ attacked by \$A\$. We test whether we eventually go back to the starting piece in \$N\$ iterations.

Furthermore, we force the search to stop and the test to fail if:

• we reach a piece that was already visited and is not the starting one (e.g. a mutual attack between 2 rooks which would result in an infinite loop)
• we detect than any piece attacks more than one piece

Attacks

Given two pieces \$A\$ and \$B\$ at positions \$(x_A,y_A)\$ and \$(x_B,y_B)\$, we compute \$dx=x_A-x_B\$ and \$dy=y_A-y_B\$.

As illustrated below, the piece \$A\$ attacks \$B\$ if:

• \$A\$ is a rook and we have either \$dx^2=0,\:dy^2>0\$ or \$dx^2>0,\:dy^2=0\$
• \$A\$ is a bishop and \$dx^2=dy^2\$
• \$A\$ is a knight and \$dx^2+dy^2=5\$

For rooks and bishops, we also have to make sure that there is no piece in between on the same ray. This is the weak point in this piece-oriented approach, as the corresponding code (the a.every()) is pretty long.

Commented

a => (                         // a[] = list of pieces
  g = (i, n, k) =>             // g is a recursive function taking an index i and
                               // a number of moves n
  i >= 0 ?                     // if i is a non-negative number:
    m ^ (m |= 1 << i) ?        //   set the i-th bit in m; if it was not already set:
      a.map(([X, Y], j) =>     //     for each piece (X, Y) at position j in a[]:
        ( h = (                //       load the position (x, y) and the type t
            [x, y, t] = a[i],  //       of the i-th piece
            X -= x             //       set: X = X - x, h = X²
          ) * X                //            Y = Y - y, v = Y²
        ) | (v = (Y -= y) * Y) //       abort if both h and v are equal to 0
        && ![ h - v,           //       bishop: we must have h = v
              h + v - 5,       //       knight: we must have h + v = 5
              h * v            //       rook  : we must have either h = 0 or v = 0
        ][t] &                 //
        a.every(([p, q]) =>    //       make sure that there is no closer piece (p, q)
          (S = Math.sign)      //       that blocks the capture, which is not the case:
          (p -= x) - S(X)      //         if it's not in the same direction
          | S(q -= y) - S(Y)   //         
          | (p *= p) +         //         or it's the capturing piece itself
            (q *= q) < 1       //         
          | [p - q, 1][t]      //         or the capture types do not match
          | p >= h & q >= v    //         or it's not blocking because it's further
        ) ?                    //       end of every(); if all tests pass:
          k = 1 / k ? -1 : j   //         update k to j, or -1 if it's already set
        :                      //       else:
          0                    //         do nothing
      ) |                      //     end of map()
      g(k, -~n)                //     do a recursive call with i = k and n + 1
    :                          //   else:
      !i & !a[n]               //     this is a full cycle if i = 0 and n = a.length
  :                            // else:
    0                          //   abort
)(m = 0)                       // initial call to g with i = m = 0

Answer 3

Python 3, 343 335 334 327 bytes

-8 thanks to @ovs

A function that takes two inputs: a list of piece types and a list of piece coordinates.

Piece types:

• Rook: 1
• Bishop: 2
• Knight: 3

Coordinates are given in the format:

21 + y * 10 + x

Coordinate format inspired by sunfish.

Returns True for true and None or False for false.

I haven't heavily tested it yet, please let me know if it fails on a test case.

m={1:[1,10],2:[11,9],3:[19,21,12,8]}
def f(p,c):
 x=0
 for y in c:
  q=p[x];w=m[q]+[-i for i in m[q]];a=[]
  for d in w:
   for i in range(1,9):
    z=c[x]+i*d
    if z<20|z>99|z%10%9<1|z in c:a+={*c}&{z};break
  if q>2:a=[x+i for i in w if x+i in c]
  if len(a)-1|0**x&y-c[0]:return
  x=c.index(a[0])
 return len(p)>x<1

Try it online!

Explanation

A crucial observation is that if each piece attacks one other and after n moves we are back on the original piece, then there exists a cycle.

# A list of move directions for each piece. +-10 is vertical and +-1 is horizontal
# Only positive numbers, to save bytes
m={1:[1,10],2:[11,9],3:[19,21,12,8]}

def f(p,c):
    # A variable representing the current piece index
    x=0

    # It is a cycle if and only if after n moves, we arrive back at the original piece. (n is number of pieces)
    for y in c:
        # Values used multiple times
        q=p[x]
        w=m[q]+[-i for i in m[q]]

        # List of attacks of current piece
        a=[]

        # Movement of bishops and rooks: keep going in each direction
        for d in w:
            for i in range(1,9):
                z=c[x]+i*d
                # Check for out of bounds or landing on another piece
                if any([z<20,z>99,z%10%9<1,z in c]):a+={*c}&{z};break

        # Knight moves
        if q>2:a=[x+i in c for i in w if x+i in c]

        # Does it only attack one piece? Does it end up at the start too early?
        if len(a)-1|0**x&y-c[0]:return

        # Move to next piece
        x=c.index(a[0])
    return len(p)>x<1

Answer 4

Jelly, 55 54 bytes

_þ`;"JṖẸ$ƇAṖṢJƑƲƇṭ¬Ẹ$Ƈ,ṖAEƊƇƊƊƲ€ị@"ṠAṂṪƊƙ$€µF0ịƬL’=L×Ẹ

Try it online!

A dyadic link taking two arguments. The left argument is a list of co-ordinates of the pieces. The right argument is a list of the piece types corresponding to those co-ordinates, with 1=rook, 2=bishop, 3=knight. The result is 1 for true and 0 for false.

The TIO link includes a footer that starts with newline-separated FEN notation and for each one, converts them to the desired input format and then calls the main program.

Rewritten to work using co-ordinate arithmetic for bishops and rooks rather than splitting rows, columns and diagonals, and saving 11 bytes in the process.

---

Original version:

Jelly, 75 66 bytes

fƇ⁹ḟ0ṣṪḢƭ€ʋ€Fḟ0
ŒṬFÄṁ×Ʋ;Z,ŒD;ŒdƊƲçþJ
ạṢ⁼ؽʋþ`T€ṭ"Ç0F?Ʋị@"µF0ịƬL’=L

Try it online!

Explanation

Link 1

• takes a list of lists as its left argument x

• takes an integer as its right argument y

• returns a list of the integers found to the left and right of y in members of x containing y, filtering out zeros

   Ƈ              | Keep those lists which:
  f ⁹             | - contain y
            ʋ€    | For each of these:
     ḟ0           | - Exclude zeros
       ṣ          | - Split at y
        ṪḢƭ€      | - Take the tail of the first part and head of the second (note will return 0 if nothing there)
              F   | Flatten
               ḟ0 | Exclude zeros
  

Link 2

• takes a list of lists of co-ordinates as its only argument

• returns a list of lists of the attacked pieces for each, first assuming each piece is a rook and then assuming each is a bishop

  ŒṬ                   | Multidimensional untruthy (recreate the board as 1s and 0s)
        Ʋ              | Following as a monad with argument z:
    F                  | - Flatten
     Ä                 | - Cumulative sum
      ṁ                | - Mould like z
       ×               | - Multiply by z (restoring zeros)
                  Ʋ    | Following as a monad with argument w:
         ;             |   - w concatenated to:
          Z            |   - Transpose of w
           ,     Ɗ     | - Paired with following as a monad:
            ŒD         |   - Diagonals of w
              ;        |   - Concatenated to
               Œd      |   - Antidiagonals of w
                   çþJ | Call link 1 for each member of this list using each of a sequence of integers from 1 to the length of the original argument of link 2
  

Main link

• takes a list of the coordinates of pieces on the board as its left argument x

• takes a list of piece types as its right argument y

• returns 1 if there is a chess cycle and 0 if not

                  Ʋ             | Following as a monad:
       ʋþ`                      | - Following as a dyad for each possible pairing of co-ordinates:
  ạ                             |   - Absolute difference
   Ṣ                            |   - Sort
    ⁼ؽ                         |   - Equals [1,2] (i.e. a knight’s move)
          T€                    | - Truthy indices of each
            ṭ"                  | - Tag each onto the corresponding list in the following:
                F?              |   - If the original list of coordinates is not empty when flattened:
              Ç                 |     - Then call link 2 using the original co-ordinate list as its argument
               0                |     - Else a literal 0
                                | By this point we have a list of length-3 lists, one for each original set of co-ordinates. The first member corresponds to attacked pieces as a bishop, the second as a rook and the third as a knight
                   ị@"          | Index into each list using the type of piece
                      µ         | Start a new link as a monad
                       F        |   - Flatten
                        0ịƬ     |   - Starting with the last member, index into the list of attacks until we reach a piece we’ve seen before, preserving all of the intermediate steps
                           L    |   - Length of this
                            ’   | Subtract 1
                             =L | Is equal to the number of pieces