Sometimes you just have to throw math at it. Understanding the video fully requires knowledge of linear algebra, but those who don't know linear algebra can still enjoy the video.
I literally had a cs class where we had to code a this "lights out" game last Friday and I said to my teacher there must be some way to use linear algebra to solve this and he was like ahh, I doubt it, maybe ¯\_(ツ)_/¯, I'ma send him this lmfao
Speaking of finding the linear combination being easier for a computer, this problem is suited to addition of binary numbers, rather than linear algebra. Adding the vectors mod 2 is equivalent to addition without carrying. 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 So we're using an XOR operation, meaning we return 1 when the two numbers are different.
This video reminded me how much I loved Linear Algebra at university before I dropped out and that at some point I knew the method that loved this problem. I need to revisit that and remind myself how to do it because on top of being a powerful tool seeing matrices of that size and knowing i could methodically crunch them just excited that mathematics part of my brain
I'm not big on subscribing but I made an exception for you. I had to pause the video 2 minutes in because I want my wife to watch this with me because of how well done the storytelling is. Thank you for all your effort with this.
This video kinda felt like one of these interactive childrens shows to me, but in a really good way. Like I was actively trying to solve it with you and I actually progressed with you
Reminds me of a puzzle in Myst i encountered a few years ago, but I don't remember if I solved it or not. Also, the mod 2 would mean that you never have to flip a number more than once, meaning the upper bound on the number of moves is the number of vectors. Fun stuff!
@@sebastianjost i would guess that n moves is an upper bound for n lamps (but prove still needed) What i am interested in, how are the "states" connected? Like what would the graph look like representimg the states and their connection
@@sebastianjost I imagine that the only way you could have a tighter upper bound is if the set of moves were overpopulated - that is if, for one of the moves, there were some linear combination of the rest of the moves that could perform the same result. In that case, since no final state requires more than 1 use of any specific move, any move combination that included the 'redundant' move could be made smaller by replacing it with its equivalent combination and 'cancelling out' the duplicated moves to leave a combination of at most one of each remaining move; while any combination that doesn't include the redundant move already naturally contains less than the previous upper bound. This would show up in your linear algebra as one of those rows 'zeroing out' [0, 0, 0, ..., 0 | 0] in the reduction I believe. Likewise, if the available moves can't make the solution at all, then we'd likely see a 'half zeroed out' row show up [0, 0, 0, ..., 0 | 1] in the reduction
@@sebastianjost Depends on your lamp array. Short answer is yes, there are light configurations on arrays of n lamps that require n moves to solve. Apart from the most trivial case (1 lamp by itself, turned on to start), a 2-by-2 grid with all lamps on at the start will require 4 moves to turn off.
i did this by "accident" during one of my first programming projects (zanzarah's box locks work this way and i always found them fascinating): a lock generator for a pen and paper rpg project you could play it by typing in the coordinates (linear cell number or coordinates separated by space), or you could type in "hack" and it would start figuring out the difference from current state to optimal state and then build a catalogue (could have been hardcoded but eh, technically it could have supported any size field and any solvable ruleset that way :D) of moves to flip a tile exactly. it then added all the moves together (just arrays, not matrices) and then randomly pulled a coordintate which in the array was bigger than 0 every 100ms, automatically entered it and decremented it by 1. There also was "fasthack" that took every number in the array mod 2 first :D looked cool as hell and i felt so fucking good about it in 7th grade
This is pretty relatable. I was playing a game (hammerwatch) that had the occasional 3x3 lights out puzzle. I would do the puzzles by trial and error until I learned that the fewer moves you took for the puzzle the greater your reward was. I tried several different approaches before realizing we were working with 9 entry vectors in Z2. I ended up with a general solution for any 3x3 lights out puzzle. What you need to do is know how to flip a single corner piece, a single side piece and a single middle piece hence by symmetry you can know how to flip any individual piece. And then for example to solve (1,0,0,0,1,1,0,0,0) you add mod2 the solutions of (1,0,0,0,0,0,0,0,0), (0,0,0,0,1,0,0,0,0) and (0,0,0,0,0,1,0,0,0).
I really like the story you have here as a kind of motivation and the process you went through, rather than just jumping directly to "matrix with elements of ring Z2."
Excellent video, though I have to admit that I was hoping that there would be a 10x10 lights puzzle instead of the sword next and you'd just break down from the matrix.
Aw, I hoped that in the end you would explain what the process of row reduction would look on the puzzle itself so that you don't have to switch between the m-by-n board of lights and mn-by-mn augmented matrix, and instead solve the puzzle by direct inspection.
I had this same problem in a game called Bean Stalker. Except instead it only flipped adjacent lights, and I just had to make them all the same, so 2 solutions per puzzle. One of the puzzles I messed up thinking it was a 5x5 grid, and when I thought of solving it like that, I gave up when I saw the number of vectors I was dealing with. Also tried working with the ammount of lights each button could switch at a time, but I currently wanna test a more "individual" way of solving. See which ones are lit up to know if around them there is an odd or even number of buttons pressed, and then trying to figure out which buttons are pressed to give me the pattern at hand. ...Though turns out the grid is 4x4, and after solving 3 different patterns, it would seem the game just takes a solved position, and randomly clicks 4~5 buttons...
Nice video! I was thinking of a slightly more efficient way to solve it, where you find a general rule to clear a single row by using moves that are in the next row (which is linear algebra but on a smaller matrix), then, using those rules to solve everything but the last row, then for each move in the first row, we can use that general rule to "solve" it to the last row to make a "last row move", then we only need to do the linear algebra on the last row using "last row moves". However, for boards which are 2 mod 3 in length or width, there may be no solution for clearing a row, and this technique fails. Though, we can generalise this technique for boards that do have a solution. For each light, (from left to right, from top to down), not in the last row or column, click the button in the next row and column from the light. This ensures we end up with only the last row and column lights possibly lit up. For the buttons not part of this procedure, we can "solve" them to make a "last row and column" move, then do linear algebra using those "last row and column" moves.
Very nice video but I find it more straightforward to think of the numbers as binary numbers and using the XOR operation. Also, instead of using Gauss-Jordan elimination, you can just work out the combinations needed to flip a single dot and then simplify the combination of all dot flips steps required to flip all dots that need flipping.
Great channel name and hoping for more content and more anecdotes in the future! I know there have been several occasions where I have also thrown some math at various puzzles in the past (with varying success) - though can't immediately recall a specific example.
Nice way to solve these types of problems. But throughout the video, I was wondering..."Is there some pattern that cannot be changed into another pattern?" Like with the sliding '15' puzzle, or Rubic's cube, do these have some sort of 'parity' where some combinations are just not possible? Is there a proof one way or the other?
That's a good question! If my memory of linear algebra serves me, the fact that we can row reduce the matrices in the 3x3 and 5x5 puzzles to row echelon form means that both matrices are invertible, which would imply they can reach any vector in their codomain space, so any arrangement of the lights could be turned into any other arrangement of the lights. I'm not entirely sure whether that theorem changes in mod 2 space, but my instinct is that it doesn't. Additionally, some other comments on this video have mentioned that there are other ways of solving the problem, such as using a XOR process to change each of the lights one at a time. If you can do that, then you can change any light you like without altering the rest of the lights, and that would again show that any pattern can be changed into any other pattern.
All you have to do is look at the augmented matrix. If it has a determinant not equal to 0, the system has only one solution mod 2, otherwise the system might have no solution, or infinitely many, though i'm not sure what infinitely many solutions would mean mod 2. I took the matrix from the possible moves from 12:50 and saw that its determinant is 1. What this means is that, for this particular arrangement, with a 3x3 grid and switching neighbours and the point itself, any configuration is achievable from any other configuration. However, this can change by varying grid size or the way the switches are made.
It is easy to observe that if grid is 2x3, then some combinations cannot be obtained from some others. It depends on determinant of the matrix. But it is possible to word it in simple terms. There are unattainable combinations if (and only if) action of several basic operations is equivalent to single basic operation. On 2x3 grid top-left corner and bottom-left corner give the same result. For larger grids, I think, it is a rather hard question, because this switch operation doesn't work so well with matrices.
omg this is so fun and engaging, but i also did feel like i learned a lot from it!!! i can feel how sincere the whole thing is 🥺 keep producing math stuff ♡♡♡
My reactions. "Ah, I got this far myself." "Ah, cool, I'm following this." "Good, and now what?" 13:18 numbers change magically at random. **Yes, that's what I was trying to achieve!** Me: (╯°□°）╯︵ ┻━┻
Ha ha, whoops. Sorry for that leap of logic. I didn't want the video to get bogged down by the long and boring row reduction process, so I sort of skipped through it. If you'd like to know how I changed the matrix to get the final answer, I recommend looking up row reduction or Gauss-Jordan elimination. There are lots of good resources, and the technique is pretty straightforward once you learn it.
I have developed light out games for android some time back. You can find a casual game approach with items on the play store called "Skull Flip" or a more minimalistic puzzle only version called "The Puzzle and You". Both have a tipp function, which show the next best step for a minimum solution. The first game has ads in it, the second does not, both are free. The approach in the video finds a solution, as in one of many, but it is not the best solution, as in minimum required steps. You will need quiet patterns for that, maybe you show that in the next video? :) Nice animation and story telling, really easy to understand things.
The time complexity here is way better than what I came up with. The best I could get is O(2^n). N being the shortest side. I need to look up Gauss-Jordan elimination... can you get multiple answers from this? If so, how?
Yes you can indeed get multiple answers in some cases. One of those cases is in fact puzzle 3 (14:36) !! If my quick and dirty code is right, the matrix at 14:47 is actually singular. And if you do the Gauss-Jordan elimination, you will find that the rank of the matrix is only 16, so we have 4 degrees of freedom. In particular, the last column of puzzle 3 can all be treated as free variables, and we should get 2^4 = 16 solutions in total. Btw I'm also guessing that only square puzzles will have unique solution, but I don't really know how to proof it.
Great job ! i would like to know wich operations are done since 13:18 for the row reduction, can someone explain or give me a link to a video that explain that ?
There are lots of really great examples of doing row reductions on RU-vid. I suggest searching "Gauss-Jordan elimination" or "matrix row reduction" on RU-vid and picking a video that seems to fit for you. :)
For every configuration of this lights off/on problem that is humanly possible you can code (a simplified version of) the puzzle instead of the algebra needed to solve it and throw brute force at it, mod2 all steps and get the solution much faster.
How do you solve this if you have more than two states per position? There's one of these Lights Out style puzzles in Destiny 2 for example, where each position of the 3x3 grid can be one of three symbols.
Interesting. I haven't tried a puzzle like that before. If the symbols always cycle through the same order as you click on them, then it's possible that this could be modeled in the exact same way but modulo three instead of two. So you would have a matrix filled with 0's, 1's, and 2's, and you'd need to reduce it mod 3. I'd be curious to know if a method like that worked.
Wilhelm Jordan, who was a professor of geodesy in the 19th century. He made some alterations to the Gaussian elimination method, so his name got tagged on as well. Confusingly, there's another mathematician named Jordan as well who's famous for different things.
