A079873 - OEIS

%I #10 Jan 25 2021 14:40:50

%S 1,25,300,2300,12650,53130,176176,476104,982335,1596279,1935294,

%T 1684446,1004934,383670,82614,7350

%N Number of positions that are exactly n moves from the starting position in the Classic Lights Out puzzle.

%C 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.

%C A puzzle in the Rubik cube family. The total number of distinct positions is 8388608.

%H Jaap Scherphuis, <a href="http://www.jaapsch.net/puzzles/">Puzzle Pages</a>

%o (Python) # alst(), moves() useful for other puzzle problems

%o def moves(p, shape, states):

%o   nxt, (n, m), k = set(), shape, states

%o   for r in range(n):

%o     for c in range(m):

%o       new = list(p[:])

%o       for ro, co in [(r,c), (r+1, c), (r, c+1), (r-1, c), (r, c-1)]:

%o         if 0 <= ro < n and 0 <= co < m:

%o           new[ro*m + co] = (new[ro*m + co]+1)%k

%o       nxt.add(tuple(new))

%o   return nxt

%o def alst(start, shape, states, v=False, maxd=float('inf')):

%o   alst, d, expanded, frontier = [], 0, set(), {start}

%o   alst.append(len(frontier))

%o   if v: print(len(frontier), end=", ")

%o   while len(frontier) > 0 and d < maxd:

%o     reach1 = set(m for p in frontier for m in moves(p, shape, states) if m not in expanded)

%o     expanded |= frontier

%o     if len(reach1):

%o       alst.append(len(reach1))

%o       if v: print(len(reach1), end=", ")

%o     frontier = reach1

%o     d += 1

%o   return alst

%o shape, states = (5, 5), 2  # 5x5 with on-off states

%o start = tuple([0 for i in range(shape[0]*shape[1])])

%o print(alst(start, shape, states, v=True)) # _Michael S. Branicky_, Jan 25 2021

%Y Cf. A079874.

%K nonn,fini,full

%O 0,2

%A _N. J. A. Sloane_, Feb 21 2003