Optimize switching puzzle solution
Overview
This question evaluates the ability to model a Lights Out-style grid puzzle as a linear system over GF(2), linear algebra skills (Gaussian elimination and null-space reasoning), and combinatorial optimization for minimizing toggle moves.
Consider a switching puzzle on an m×n grid of lights where toggling a cell flips its state and that of its orthogonal neighbors (Lights Out variant). Given an initial configuration and a target configuration, compute a sequence of toggles with the minimum number of moves or report that no solution exists. Explain how to model this as a linear system over GF ( 2), choose a variable ordering, perform Gaussian elimination with back-substitution to get one or all solutions, and handle multiple-solution minimization (e.g., via basis enumeration or BFS on the null space). Analyze time complexity and memory trade-offs for m,n ≤ 10.