login
A079873
Number of positions that are exactly n moves from the starting position in the Classic Lights Out puzzle.
2
1, 25, 300, 2300, 12650, 53130, 176176, 476104, 982335, 1596279, 1935294, 1684446, 1004934, 383670, 82614, 7350
OFFSET
0,2
COMMENTS
This is the number of positions that can be reached in n moves from the start, but which cannot be reached in fewer than n moves.
A puzzle in the Rubik cube family. The total number of distinct positions is 8388608.
PROG
(Python) # alst(), moves() useful for other puzzle problems
def moves(p, shape, states):
nxt, (n, m), k = set(), shape, states
for r in range(n):
for c in range(m):
new = list(p[:])
for ro, co in [(r, c), (r+1, c), (r, c+1), (r-1, c), (r, c-1)]:
if 0 <= ro < n and 0 <= co < m:
new[ro*m + co] = (new[ro*m + co]+1)%k
nxt.add(tuple(new))
return nxt
def alst(start, shape, states, v=False, maxd=float('inf')):
alst, d, expanded, frontier = [], 0, set(), {start}
alst.append(len(frontier))
if v: print(len(frontier), end=", ")
while len(frontier) > 0 and d < maxd:
reach1 = set(m for p in frontier for m in moves(p, shape, states) if m not in expanded)
expanded |= frontier
if len(reach1):
alst.append(len(reach1))
if v: print(len(reach1), end=", ")
frontier = reach1
d += 1
return alst
shape, states = (5, 5), 2 # 5x5 with on-off states
start = tuple([0 for i in range(shape[0]*shape[1])])
print(alst(start, shape, states, v=True)) # Michael S. Branicky, Jan 25 2021
CROSSREFS
Cf. A079874.
Sequence in context: A335598 A210430 A158990 * A078488 A010941 A022620
KEYWORD
nonn,fini,full
AUTHOR
N. J. A. Sloane, Feb 21 2003
STATUS
approved