Is it a chess cycle?

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.
• Suggested testcases: 8/8/8/8/8/8/8/8; 8/8/8/2R2R2/8/8/8/8. – tsh May 3 at 5:50
• How do you feel about taking input as a list of pairs with (piece type, a value representing the position)? – dingledooper May 3 at 6:10
• @dingledooper perfectly fine. – Razetime May 3 at 6:16
• Suggested test case: 8/8/8/1R3B2/8/3R2N1/8/8 is falsey. (Each piece attacks exactly one other piece, but one piece is not under attack.) – Robin Ryder May 3 at 7:48
• oh, I see it now. wow how obvious. :) – cnamejj May 3 at 9:22

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*)
]&


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

• Oh, that's right! I'm quite new to golfing and overlooked the precedence of the inside stuff... – FZs 2 days ago

Python 3, 343335334 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

• f([],[]) (no pieces) should return False. – Razetime May 3 at 9:53
• @Razetime Fixed. Thanks – EnderShadow8 May 3 at 10:36
• Didn't really test, but this should work for 325 bytes. (a+={*c}&{z} only appends z to a if it is a member of c.) – ovs May 3 at 11:51
• The & is set intersection here. This takes two sets and returns a new set which only contains items which were in both of the original sets. {*c} is c converted to set and {z} is the set containing only z. – ovs May 3 at 11:54
• @ovs Ah, I see. It seems solid enough so I'll include it. – EnderShadow8 May 3 at 11:55