Problem 44751. Lights Out 1 - 5x5, 3 moves

Created by goc3

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Lights_Out_(game)\"><w:r><w:t>Lights Out</w:t></w:r></w:hyperlink><w:r><w:t> is a logic game wherein all lights need to be turned off to complete each board. Pressing any button on the board toggles that button as well as adjacent buttons vertically and horizontally, where present (and no wrapping here), to the opposite state (i.e., on to off and off to on). For example, pressing a corner button toggles three button states, an edge button four button states, and an interior button five button states (as can be visualized by the example below).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This first problem uses a 5x5 board and requires that your function return a column-major vector of button presses (indices) that will solve the board by turning off all lights. Since pressing any button twice will return to the same board state, only one move is needed (and allowed) per button. For example, if</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ board = [0 1 0 0 0\n 1 1 1 0 1\n 0 1 0 1 1\n 1 0 0 0 1\n 1 1 0 0 0]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>the answer is:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ moves = [5 7 23]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In this first problem, all boards have solutions of only three moves.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note: while brute-force solutions will solve some problems in this series, they will time out on later ones. Solving the first few problems by developing a robust solver function is encouraged.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>As a potential starting point, you might check out one or more of the following resources by</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mat.ucm.es/~vmunozve/lights-out.pdf\"><w:r><w:t>Vicente Muñoz</w:t></w:r></w:hyperlink><w:r><w:t>;</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.ijritcc.org/download/browse/Volume_5_Issues/August_17_Volume_5_Issue_8/1503304082_21-08-2017.pdf\"><w:r><w:t>Chen, et al.</w:t></w:r></w:hyperlink><w:r><w:t>;</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://vprusso.github.io/blog/2017/the-mathematics-of-lights-out/\"><w:r><w:t>Vincent Russo</w:t></w:r></w:hyperlink><w:r><w:t>;</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://mathworld.wolfram.com/LightsOutPuzzle.html\"><w:r><w:t>Margherita Barile (on wolfram.com)</w:t></w:r></w:hyperlink><w:r><w:t>;</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.keithschwarz.com/interesting/code/?dir=lights-out\"><w:r><w:t>Keith Schwarz</w:t></w:r></w:hyperlink><w:r><w:t>; or</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://dc.ewu.edu/cgi/viewcontent.cgi?referer=https://www.google.com/&amp;httpsredir=1&amp;article=1166&amp;context=theses\"><w:r><w:t>Rebecca Meyer (a master's thesis)</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Next:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/44752-lights-out-2-5x5-4-moves\"><w:r><w:t>5x5, 4 moves</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

<a href = "https://en.wikipedia.org/wiki/Lights_Out_(game)">Lights Out</a> is a logic game wherein all lights need to be turned off to complete each board. Pressing any button on the board toggles that button as well as adjacent buttons vertically and horizontally, where present (and no wrapping here), to the opposite state (i.e., on to off and off to on). For example, pressing a corner button toggles three button states, an edge button four button states, and an interior button five button states (as can be visualized by the example below).This first problem uses a 5x5 board and requires that your function return a column-major vector of button presses (indices) that will solve the board by turning off all lights. Since pressing any button twice will return to the same board state, only one move is needed (and allowed) per button. For example, if<pre> board = [0 1 0 0 0
 1 1 1 0 1
 0 1 0 1 1
 1 0 0 0 1
 1 1 0 0 0]</pre>the answer is:<pre> moves = [5 7 23]</pre>In this first problem, all boards have solutions of only three moves.Note: while brute-force solutions will solve some problems in this series, they will time out on later ones. Solving the first few problems by developing a robust solver function is encouraged.As a potential starting point, you might check out one or more of the following resources by <a href = "http://www.mat.ucm.es/~vmunozve/lights-out.pdf">Vicente Muñoz</a>; <a href = "http://www.ijritcc.org/download/browse/Volume_5_Issues/August_17_Volume_5_Issue_8/1503304082_21-08-2017.pdf">Chen, et al.</a>; <a href = "http://vprusso.github.io/blog/2017/the-mathematics-of-lights-out/">Vincent Russo</a>; <a href = "http://mathworld.wolfram.com/LightsOutPuzzle.html">Margherita Barile (on wolfram.com)</a>; <a href = "http://www.keithschwarz.com/interesting/code/?dir=lights-out">Keith Schwarz</a>; or <a href = "https://dc.ewu.edu/cgi/viewcontent.cgi?referer=https://www.google.com/&httpsredir=1&article=1166&context=theses">Rebecca Meyer (a master's thesis)</a>.Next: <a href = "https://www.mathworks.com/matlabcentral/cody/problems/44752-lights-out-2-5x5-4-moves">5x5, 4 moves</a>

Solve

Solution Stats

132 Solutions
25 Solvers

Last Solution submitted on Jun 12, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers25

Problem Tags

flip game lamp light lights logic out puzzle toggle

Problem 44751. Lights Out 1 - 5x5, 3 moves

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers25

Suggested Problems

More from this Author139

Problem Tags

Problem 44751. Lights Out 1 - 5x5, 3 moves

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers25

Suggested Problems

More from this Author139

Problem Tags

Players