Solving Lights Out - Network Theory in Practice!

[@passelcrawfordon2277]

I wrote a program in VB3 a little over 20 years ago to allow playing the game and analyzing the solutions. You said exactly half of the configuration of lights is unsolvable, but I remember it as being 3/4ths of the possible light combinations are unsolvable. A solvable configuration can only lead to other solvable configurations. Likewise, an unsolvable configuration can only lead to other unsolvable configurations. You can quickly reduce any given configuration of lights into a single set of lights along one edge of the game board. Since you can use your program to test if a solution is solvable, you should be able to quickly verify the 31 combinations of possible lit light configurations at the edge of the board to find that there are only 7 out of 31 combinations that are solvable. The 32nd configuration of the row is no lights lit, which is by definition solvable, so you have 8 out of 32 combinations solvable for the row, and that ratio applies to the set of 25 lights by extension. Also, every puzzle has four unique paths to reach Lights Out, but the four paths will most often not be the same length, but in some cases, there are multiple equal short paths (i.e. button sequences), so more than one "least button presses" sequence. I downloaded the python script and ran it. The first game I tried demonstrated the error. I just set the very first checkbox (A1) and hit solve, and the program "solved" it. The fact is setting any single light around the edge of the board is an unsolvable configuration. There is an error at step 9 of the solve. I show step 8 and step 9. Step 8. Button B3 X O X O X Note that A1 is set O X X O X X O O O O O O O O O O O O O O Step 9. Button B1 X O X O X Note that A1 should be not set. X O X O X O O O O O O O O O O O O O O O Pressing Button B1, should have Toggled button A1 off (reference the state at Step 8), but your code leaves it on I'm assuming that first bit, A1, is probably incorrectly processed somehow, so you end up with double the number of actual solutions in your Data file, but I don't understand what your code is doing well enough at this point to be able to figure out the issue. It may be the "B1" mask value is incorrect. *Update* 5 April 2023, I did look at the Mask generation code and the "B1" Mask (masks[5]) was indeed incorrect. It was 1120, but it should have been 1121. That single bit missing in the one mask (out of 25 masks) caused the program to generate 16+ million (2^24) solutions instead of the correct 8+ million (2^23) solutions. Line 168 of the script is if i - 5 > 0: But should be if i - 5 >= 0:

[@dixon1e]

Very nice video, especially how you thought through the problem with different data structures. Never heard of the game. Diabolical way to keep the kids quiet :)

[@LastHeartGames]

Glad you enjoyed it. I hope to be able to do more like these in the future.

[@The-Anathema]

If you only care about the optimal solution you can use some trivial algebra to calculate the optimal solution for any given board (and you obviously also learn if the puzzle is solvable), this solution is very overkill. You can do this in 135MB naive, probably under 40 if you account for non-unique board states (all symmetries and rotations are equivalent so about 3/4 of board states should be duplicates). Add a bit extra overhead if we want to multithread it for speed, this is trivially parallelizable so it's not going to have a lot of overhead. Sorta tempted to do it now.

[@valentinadominguez8659]

Bo loco acabas de salvar a mi grupo de un trabajo nefasto! Te agradezco un monton

[@michaelmcguffin7160]

Wow I forgot all about that game. God the 90s were great

[@discountmorty213]

I got this as a kid and wonder how it being solved lol

[@kevinleesmith]

A) its not a list of lists its a 2 dimensional array. B) you can store 1 board in 1 32 bit long aka 4 bytes, not 1.2kB!! I will look at the python and if I can be bothered re-write it

[@dersportstatistiker]

Nice solutiion, but not everything was right: You explained, that 50% of the possible starts couldn't be solved. That is not correct, 25% are possible to solve. Test this: Find the first row of a solution (always one of four) with the structure 00ABC (A,B,C are 0 or 1). solve this 3 equations: a=1-A, b=1-B, c=1-C the 3 other solutions are always starting with: 01abC, 10aBc, and 11Abc The starting row defines alway the next row and so on. I could say much more and give you all my proofs, just ask ...