Chess 960 and retroanalysis

Question

How many Chess 960 starting positions have no retrograde past (which I mean as: can't be played from a different Chess 960 starting position)?

Example: If you look at the standard chess starting position, it might be possible that it wasn't the starting position at all, but the game started with RNBQKBRN and the previous moves were 1.Ng3 Ng6 2.Nf5 Nf4 3.Nh4 Nh5 4.Nf3 Nf6 5.Rh1 Rh8 6.Ng1 Ng8.

Please note that this would NOT lead to the "standard" position since by retro convention you may assume all castling rights that apparently exist really exist, and in this sequence the right to castling short is lost. You are thus free to interpret my question by "including" or "excluding" the issue of castling rights.

Answer 1

Let me solve the problem by considering that the retrograde history need not preserve castling rights. I believe there are

48 such positions.

Recall that a Chess960 position is restricted by the following rules:

1. The K is between the two R's
2. The two B's are on opposite-coloured squares

We notice that

N's are very useful for shuffling pieces around, so they must be blocked off from the K, R's, and Q by the B's.

To shorten my explanation, we use the observation that

if there are 4 blank spaces with KRRQ yet to be placed, then there are 4 ways to do it (because if you place the Q then the rest are fixed by rule (1). (This assumes the B's already satisfy rule (2).)

There are a few cases:

1. N's are separated: NBXXXXBN, 4 ways by the observation

2. NN are next to the edge: assume first that NNBXXXXX (multiply by 2 for the mirror image), place the B (3 ways), then 4 ways by the observation, giving 2 x 3 x 4 = 24 ways

3. BNNB occurs: there are 5 ways to place this chunk, then 4 ways by the observation, giving 5 x 4 = 20 ways

Finally

4 + 24 + 20 = 48.

Commentary about the problem if we want to preserve castling rights in the retrograde history:

Then KRRBB cannot move, and we can only shuffle among QNN. Thus we have to count the number of positions where the Q is not next to any N. This can be a bit tricky to count. (EDIT H.R.: Resorting to a brute force but straightforward Python code again, we get 492 solutions. The complement - Q with at least 1 N at her side - is 960-492 = 2^2 x 3^2 x 13.)

Answer 2

Benjamin's answer agrees with a brute (and by brute I mean brute) force calculation using Python. The following code was already used in parts for this question and recycled (see also there for code hints). For the variant with castling rights, just delete ])# to check your result. (Edited code tip: The inner if checks whether all neighbors of knights are border or bishop or another knight...or rook if castling counts.)

def nextperm(permo):
    n = len(permo)
    y = n - 1
    while permo[y - 1] > permo[y]:
        y -= 1
    yy = n - 1
    while permo[y - 1] > permo[yy]:
        yy -= 1
    permn = permo[0:y - 1] + [permo[yy]] + sorted(permo[y - 1:yy] + permo[yy + 1:n])
    return permn

def perminv(perm):
    
    num_sqsize = len(perm)
    perm_inv = [0 for _ in range(num_sqsize)]
    for y in range(num_sqsize):
        x = perm[y]
        perm_inv[x] = y
    return perm_inv

ch = ['K','Q','R','R','B','B','N','N']
#01234567 = kqrrbbnn
perm = [_ for _ in range(8)]
ct = 0
ca = [0]*7
for i in range(40320):
    ki = perm[0]
    qu = perm[1]
    lr = perm[2]
    rr = perm[3]
    lb = perm[4]
    rb = perm[5]
    ln = perm[6]
    rn = perm[7]
    if lr < ki < rr and ln < rn and lb < rb and (lb+rb)%2 == 1:
        out = ''
        permi = perminv(perm)
        for j in range(8):
            out += ch[permi[j]]
        set1=set([ln+1,ln-1,rn+1,rn-1])
        set2=set([-1,8,lb,rb,ln,rn])#,lr,rr,ki])
        if set1.issubset(set2):
            ct += 1
            print(ct,out)
    perm = nextperm(perm)