tag:blogger.com,1999:blog-4115025577315673827.post4102047449034371708..comments2020-05-25T13:34:36.365+05:30Comments on CSE Blog - quant, math, computer science puzzles: Black and White Squares PuzzlePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-4115025577315673827.post-29072815795082801542013-05-20T17:11:36.356+05:302013-05-20T17:11:36.356+05:30Thanks for the solution. Interesting. I remember r...Thanks for the solution. Interesting. I remember reading about it some time back.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-15387778977711880002013-04-26T00:35:23.335+05:302013-04-26T00:35:23.335+05:30This is the "All Ones Problem"
The squa...This is the "<a href="http://www.academia.edu/1069942/Linear_cellular_automata_and_the_Garden-of-Eden" rel="nofollow">All Ones Problem</a>"<br /><br />The squares to switch are the solution to a system of n² equations Ax = B in Z₂.<br /><br />A is the n² by n² matrix whose kᵗʰ row represents which lights are toggled when the kᵗʰ square is "switched", and B is the state of the starting board.<br /><br />The system is always solvable because A has maximal rank (n² by n² symmetric matrix with non-zero determinant). Solve it and the 1s and 0s in x tell which squares to switch or not.<br /><br /><a href="http://mathworld.wolfram.com/LightsOutPuzzle.html" rel="nofollow">"Lights Out Puzzle" on Mathworld</a> gives a very clear worked example of this method.JDGMhttps://www.blogger.com/profile/11829357060109505064noreply@blogger.com