Skip to content

Instantly share code, notes, and snippets.

@theabbie
Last active October 6, 2023 10:49
Show Gist options
  • Save theabbie/6fa2d10cd81b8e30b3f42c3a4c745457 to your computer and use it in GitHub Desktop.
Save theabbie/6fa2d10cd81b8e30b3f42c3a4c745457 to your computer and use it in GitHub Desktop.
Python Script to solve "Lights Out" Game in optimal way using BFS.

Lights Out: https://veerasundar.com/lights-out-online-game/

Run Here: https://ideone.com/a1Go1a

Edit beg variable to set initial state, 1 for lights on and 0 for off.

Program outputs list of (x, y) coordinates you need to press to solve it in optimal moves.

The Algorithm uses Breadth-First-Search by considering state of game as graph node.

Each move is an unweighted edge to another state, and we just need to find shortest path from initial state to final state ie. state with all lights off.

https://en.wikipedia.org/wiki/Breadth-first_search

from collections import deque
M = N = 5
beg = """
00011
00001
10000
11000
10000
""".split("\n")[1:-1]
grid = 0
pos = lambda x, y: N * x + y
for i in range(M):
for j in range(N):
if beg[i][j] == "1":
grid ^= (1 << pos(i, j))
parent = {}
q = deque([(grid, -1, -1)])
v = {grid}
while len(q) > 0:
curr, px, py = q.pop()
if curr == 0:
path = []
while (curr, px, py) != (grid, -1, -1):
path.append((px, py))
curr, px, py = parent[(curr, px, py)]
path.reverse()
print(*path)
exit(0)
for i in range(M):
for j in range(N):
newcurr = curr
for x, y in [(i, j), (i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j)]:
if 0 <= x < M and 0 <= y < N:
newcurr ^= (1 << pos(x, y))
if newcurr not in v:
v.add(newcurr)
parent[(newcurr, i, j)] = (curr, px, py)
q.appendleft((newcurr, i, j))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment