Max estimated number of states of Rubik's Cube after N quarter-turn moves (Czech)

rubiks_cube.py

"""
Horní odhad počtu stavů Rubikovy kostky po N tazích typu čtvrt-obrátka

# https://sciencemag.cz/umela-inteligence-se-sama-naucila-slozit-rubikovu-kostku/#post-3981572954

Počty stavů po daném počtu tahů v jedné ze tří rovin
O: -                  0
1: L l R r            4
2: LL LR Lr lR lr RR  6
3: LLR LLr LRR lRR    4
4: LLRR               1

celkem 4 * 4 - 1 možných nových stavů
"""
# počty stavů při po sobě jdoucích rotacích okolo jedné osy
mul = [0, 4, 6, 4, 1]
N = 20
NN = N + 1

# st[pocet_ruznych_po_sobe_jdoucich_os_rotace][pocet_kroku]
# prázdné pole [0..20][0..20]
st = [[0 for j in range(NN)] for i in range(NN)]

st[0][0] = 1
for i in range(N):
    for j in range(NN):
        for k in range(len(mul)):
            if j + k <= N:
                # na začátku vyberu kteroukoli ze tří os, při změně se volí ze dvou os
                st[i + 1][j + k] += st[i][j] * mul[k] * (2 if i > 0 else 3)
# tisk výsledků
for row in st:
    print(row)
ss = 0
print()
last_s = 1.
for j in range(NN):
    xs = sum(st[i][j] for i in range(NN))
    ss += xs
    print(xs, ss, ss / last_s)
    last_s = ss
print()
print(float(ss))