Python Script to solve "Lights Out" Game in optimal way using BFS.

lights_out.md

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

lights_out_solver.py

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