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