# How many different kinds of fairy units?

A recent question Is there a Fairy Chess Piece that Combines the Gnurider and Queen? suggested the following:

Assuming we are only operating on a 8x8 board, how many functionally distinct fairy pieces are there that combine any number of leaper & rider movement powers?

Recall that an (x,y)leaper moves in a single leap x squares away horizontally & y squares away vertically (or vice versa). So the knight is the (1,2)leaper. On the other hand a rider combines any number of leaper moves in a single direction. Thus the rook & bishop are the (0,1)rider & (1,1)rider respectively. These powers can be combined as much as desired. So the queen is the rook-bishop.

There are quite a lot of distinct combinations possible but the question is not quite trivial, for example a camelrider (= (1,3)rider) is not the same as a camel-(2,6)leaper. The former can be prevented from moving from a1 to c7 by a blocking unit on b4.

Nevertheless the number of species in the zoo can be counted. So how many?

In order to all be on the same page, let’s say that we DO include zero, the (0,0)leaper (which can’t be distinguished from the (0,0)rider as far as I can see). If you have a zero, you can never be in zugzwang. Zero is not to be confused with dummy, which is simply inert, and is the combination of no leapers or riders, but is still a valid unit. Neither of these pieces should be confused with the dummy pawn, which is not a fairy unit, but is simply a regular pawn that happens to be on the eighth rank.

• Oops I didn't consider (0,0)-leaper/rider. Is it a thing in chess puzzles? I have only heard of variants where you can pass a turn, but not as a piece "move". And would such a piece be blocked by itself and be unable to, um, "move"? And if multiple pieces have this ability added, would they be functionally redundant? Commented Jun 27 at 23:06
• Zero is in the PDB database. It doesn’t self-block any more than a rook on cylindrical board or a rose nightrider. It’s not hard to include - just a factor of two. If multiple pieces have the zero ability then they need to be captured one by one in order to force zz, so not functionally redundant! :-) If K has zero then it is not quite redundant with other pieces having zero because using it with K will cost castling rights! Commented Jun 28 at 3:11

Maximum riders' meaningful vectors: (3,3), (3,2), (3,1), (3,0); others are (2,2), (2,1), (2,0), (1,1), (1,0)

Leapers-only meaningful vectors: (7,7)-(7,0), (6,6)-(6,0), (5,5)-(5,0), (4,4)-(4,0).

Distinct directions (ie. with coprime numbers) where different directions cannot interact in terms of leapers&riders combinations: (1,0),(1,1),(2,1),(3,1),(3,2), and leaper-only ones: (4,1),(4,3),(5,1),(5,2),(5,3),(5,4),(6,1),(6,5),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6)

The leaper-only directions can be freely combined with others, so 2^14 combinations.

For each interacting direction where riders and leapers are both possible, I will consider which combinations of leapers and riders are equivalent.

Now, these combinations are only the same if the reachable squares are the same and for each reachable square, the squares required to be empty (cannot leap over) are also the same. I will call the squares required to be empty "dependence", and denote a leaper or rider that goes n squares in that direction as n-leaper or n-rider. A 1-rider in any direction is not equivalent to a 1~n-leaper in that direction because the former cannot leap across (n-1) points. For a direction with 2 destination possibilities, there are 5 combinations: 4 combinations of leapers (1, 2, 12, nothing) and a rider (goes to 1 and 2 but cannot leap over the square in the middle). For a direction with 3 destinations (123), 3 can depend on leaping over 1 or 2 but not only one of them, and 2 can depend on 1 or not, and if either 3 or 2 is dependent, then there must be a 1-rider. So 1 1-rider-only possibility (2 and 3 are dependent), 1 1-rider+2-leaper possibility (only 3 has dependence), 1 1-rider+3-leaper possibility (only 2 has dependence), 2^3 leaper possibilities with no dependence, in total 11 combinations. Luckily there are no directions with 4-6 possibilities, only with 7 possibilities.

For 7 possible target squares, let's call them 1234567, you can have 1-rider (2-7 all dependent on previous squares), or 2-rider (4,6 dependent), 3-rider (6 dependent) but that's all the meaningful riders. I found it error-prone to count all cases, so here's some code to do it for arbitrary number of target squares in a direction:

``````import math

def getBitVector(x,n):
binary = [int(i) for i in (bin(x)[2:]).zfill(n)]
return binary

def isRiderRelevant(stride,dep_list): # assuming dep_list represents the dependency of a square k*stride (k>1)
ans=True
for x in dep_list:
if x==0:
ans=False
break
if x%stride==0:
#hypothetically the 8-th square can depend on a 2-rider component and a 4-rider component,
#but the 4-rider makes the 2-rider irrelevant for this target square
#in particular, any other rider that goes to a square makes the 1-rider irrelevant for that square
ans=False
break
if x==stride:
ans=False
break # just in case
return ans

def listEqual(l1,l2):
#2-layer list equality check, assuming sub-lists are sorted
if len(l1)!=len(l2):return False
for i,x in enumerate(l1):
y=l2[i]
if len(x)!=len(y):return False
for j,n in enumerate(x):
if n!=y[j]: return False
return True

def pretty_print_possibilities(l):
for x in l:
output=[]
for y in x:
if len(y)==0: output.append("_")
elif len(y)==1: output.append(str(y[0]))
else: output.append(','.join([str(z) for z in y]))
print(*output, sep=' ')

#dependency entries:
#[] means not accessible, [0] means no dependencies (from leaper or the first step of a rider),
#[1] means depends on 1,2,3..., [2] means 2,4...etc, [2,3] means both 2,4... and 3,6,... would be OK
def counts(n):
riders=[x+1 for x in range (math.floor(n/2))]
leapers=[x+1 for x in range (n)]
rider_count=len(riders)
leaper_count=len(leapers)
print(f'riders is {riders}')
print(f'leapers is {leapers}')
possibilities=[]
for r_indices in range (2**rider_count): # iterate over all combinations
r_entries=getBitVector(r_indices,rider_count)
for l_indices in range (2**leaper_count):
l_entries=getBitVector(l_indices,leaper_count)
dependency=[([]) for x in range (n+1)]
for i,r_value in enumerate(r_entries):
if r_value==0: continue
stride=riders[i]
dependency[stride]=[0] # other entries don't matter for the first step
current=stride*2
while current<=n:
if isRiderRelevant(stride,dependency[current]):
dependency[current]=[x for x in dependency[current] if stride%x!=0]
dependency[current].append(stride)
dependency[current].sort()#keep it sorted
# if stride is included in this list or any entry is divided by it (makes it obsolete)
# or any entry is 0 (leaper), skip it; otherwise add stride to the list,
# and remove any entry that is made obsolete by it (divides stride)
current=current+stride
for i,l_value in enumerate(l_entries):
if l_value==0: continue
stride=leapers[i]
dependency[stride]=[0] # other entries don't matter for the leaper
isNew=True
for p in possibilities:
if listEqual(dependency,p)==True:
isNew=False
break
if isNew==True:
possibilities.append(dependency)
return possibilities

result=counts(7)
pretty_print_possibilities(result)
print(f'count is {len(result)}')

``````

According to the code, the number of ways to combine leapers and riders in a direction with 7 possible target squares is 329 (and for 2 and 3 it agrees with manual analysis too).

So the total number of combinations is

2^14 (leapers-only directions) * 329 ( 1,0 direction) * 329 (1,1 direction) * 11 (2,1 direction) * 5 (3,1 direction) * 5 (3,2 direction) = 487690649600

or 487690649599 (minus 1) if you exclude the possibility of having no movement at all. If (0,0) is considered a valid vector (a move that passes the turn/does nothing) then it's like another "direction" and the total number is doubled :

487690649600 * 2 = 975381299200

Or 975381299199 if you exclude the possibility of having no abilities at all.

I hope I didn't make more mistakes, but please let me know if you found any errors.

• Final point is that (due to 329=7*47) the final result is made up from all small factors: 2^14 * 5^2 * 7^2 * 11 * 47^2 Commented Jul 6 at 5:07

Just want to put in a partial solution to provide an independent count to validate other solutions.

Note that I take both zero & dummy to be legal units.

A couple of general points:

• Take 0 =< p =< q

• If a (p,q)rider is present, then (p,q)leaper would be redundant.

• If q > 3, then a (p,q)rider could never do more than 1 leap, instead use (p,q)leaper.

Just going to look at the hardest case where 7 leaps are possible, e.g. the (0,1) direction.

• With no riders, there are 2^7 = 128 possible sets of leapers. The empty set doesn’t allow movement at all in this axis: that’s ok. Maybe the movement is in other directions or if not we have the immobile dummy.

• If (0,1)rider is the only rider. There are apparently 2^6 = 64 choices of leaper but if all 6 leaper powers are present then (0,1)rider can never be blocked. So 63.

Note that the only value of adding a (0,1)rider is to reach those locations that other riders and leapers cannot reach. We can apply this pattern to other cases. Instead of a * 2^b combinations we have when we add the (0,1)rider: a * (2^(b-1)-1).

• (0,2)rider and no other riders. Can’t have both (0,4)leaper & (0,6)leaper else (0,2)rider power is never needed, and might as well have (0,2)leaper. So there are 3*2^4 = 48 choices of leapers.

• Hence (0,1)rider & (0,2)rider gives 3*7 = 21.

• (0,3)rider only is even simpler. Can’t have (0,6)leaper else (0,3)rider can never be blocked. So 2^5 = 32 choice of leaper.

• Hence (0,1)rider & (0,3)rider gives 15 choices of leaper.

• This leaves the corner case where (0,2)rider & (0,3)rider are combined. This offers unique feature of two routes from e.g. a1 to b7, so (0,6)leaper cannot be present. So 2^4 = 16 choices of leaper.

• Hence (0,1)rider, (0,2)rider & (0,3) rider gives 2*3 = 6.

So I make it 128 + 63 + 48 + 21 + 32 + 15 + 16 + 6 = 329 possible combinations for the (0,1) direction. Please confirm.

• I think (0,1) rider +(0,2) rider is not the same as (0,1) rider alone, or even (0,1) rider+(0,2) leaper, because (0,1) rider +(0,2) rider can not only leap over a piece at (0,1) but also changes the dependence squares of (0,4) from (0,1/2/3) to (0,2). I believe it's very tricky to calculate without counting all cases explicitly that's why I did that, but it would be great if there's a way to calculate more easily or even get a recurrence relation or something. It's one of the more stupid things I've counted by hand lately :) Commented Jun 27 at 23:36
• It's impressive you got the right answer (hopefully ;) by analyzing. I first used a semi-automated list, but apparently missed a few repeated cases somewhere. I counted it again using a script and it also gives 329 unique lines but because of the poor formatting I'm not sure where's my mistake. Do you know any better explanation of these numbers? 5, 11, 28, 58, 161, 329 Commented Jun 28 at 3:33
• Thanks: good coding sir. I think the series begins 1, 2, before the 5. Worth sticking it into OEIS for the grins. Now maybe Mr Gilman who likes naming fairy pieces can come up with a trillion names for this lot! Commented Jun 28 at 3:43
• Thanks for the suggestion! I looked it up in OEIS and it doesn't seem to match anything. You are welcome to submit it there, it's your question after all and you got the correct answer first. Maybe you can also work out the number of distinct units for nxn chessboard that might be interesting too. Commented Jun 30 at 1:29