Using backtracking, solve this problem in Python:

Lights Out

Another classic puzzle. You're given a N x N grid of button lights, all of which are initially ON$.$ Pressing a button toggles the state of its four neighbors in the up$,$ down, left and right directions.

Example by K$.$L$.$ deVries on Medium

Your goal is to find the combination of button presses that turns all the lights OFF. Write a program that uses backtracking with iterative deepening to find the solution.

Modify the basic recursive backtracking search to take additional current$\_$depth and max$\_$depth parameters. If the current$\_$depth exceeds the max$\_$depth, treat it as a base case and return immediately.

For a given state, there are N$2$ possible moves to consider, which correspond to each possible button press.

Consider why iterative deepening is a good strategy for this problem. You're allowed to press each button as many times as you want, so there's no limit on the depth of any path. Left unchecked, you would simply descend the search tree, pressing buttons to create an infinitely long path that might never lead to a solution. Iterative deepening ensures that you consider all button combinations up to a certain depth before exploring deeper paths.

A pseudocode version of the solve method is as follows:

def solve$($lights$,$ current$\_$depth, max$\_$depth$)$:

$"""$

Recursive backtracking solution to the lights out puzzle

$"""$

# Depth limit reached

if current$\_$depth $>$ max$\_$depth:

return

# Determine if the current state is a solution

if all$\_$lights$\_$are$\_$off$($lights$)$:

print$($presses$)$ # Print the sequence of button presses that led to the solution

exit$(0)$

# Consider all of the N $*$ N button presses

for row in range$($N$)$:

for col in range$($N$)$:

# Determine the state of pressing button at position $($row$,$ col$)$

lights $=$ flip$($lights$,$ row, col$)$

# Keep track of the sequence of button presses

presses.append$(($row$,$ col$))$

# Recursively search

solve$($lights$,$ current$\_$depth $+1,$ max$\_$depth$)$

# Undo the effect of flipping $($row$,$ col$)$ to prepare for the next option

lights $=$ flip$($lights$,$ row, col$)$

presses.pop$()$

# If you get here, there was no solution on this path: backtrack

You'll need to figure out how to implement the relevant methods $($all$\_$lights$\_$are$\_$off and flip$),$ then write an outer function that runs the search for increasing values of max$\_$depth until it finds a solution.

The pseudocode assumes that you're keeping track of the state of the lights using an N by N list of lists, which is fine. The variables presses is a list that keeps track of the sequence of button presses used to find the solution.

Start with a small grid, say $3$ x $3,$ then try solving for larger grids.