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

Created by goc3

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></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:jc w:val=\"left\"/></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:jc w:val=\"left\"/></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:jc w:val=\"left\"/></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:jc w:val=\"left\"/></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:jc w:val=\"left\"/></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=\"\"><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=\"\"><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=\"\"><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=\"\"><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=\"\"><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:jc w:val=\"left\"/></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>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: normal; text-decoration: none; white-space: normal; "><div style="display: block; min-width: 0px; padding-top: 0px; vertical-align: baseline; "><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><a target='_blank' href = "https://en.wikipedia.org/wiki/Lights_Out_(game)"><span style=""><span style="">Lights Out</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> 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).</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">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</span></span></div><div style="background-color: rgb(247, 247, 247); border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-bottom: 10px; margin-left: 3px; margin-right: 3px; margin-top: 10px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; "><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-inline-end: 1px solid rgb(233, 233, 233); border-inline-start: 1px solid rgb(233, 233, 233); border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-height: 18px; padding-left: 4px; white-space: nowrap; "><span style="border-inline-end: 0px none rgb(0, 0, 0); border-inline-start: 0px none rgb(0, 0, 0); border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-right: 45px; min-height: 0px; padding-left: 0px; tab-size: 4; white-space: pre; margin-right: 45px; "><span style="margin-right: 0px; "> board = [0 1 0 0 0</span></span></div><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-inline-end: 1px solid rgb(233, 233, 233); border-inline-start: 1px solid rgb(233, 233, 233); border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-height: 18px; padding-left: 4px; white-space: nowrap; "><span style="border-inline-end: 0px none rgb(0, 0, 0); border-inline-start: 0px none rgb(0, 0, 0); border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-right: 45px; min-height: 0px; padding-left: 0px; tab-size: 4; white-space: pre; margin-right: 45px; "><span style="margin-right: 0px; ">          1 1 1 0 1</span></span></div><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-inline-end: 1px solid rgb(233, 233, 233); border-inline-start: 1px solid rgb(233, 233, 233); border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-height: 18px; padding-left: 4px; white-space: nowrap; "><span style="border-inline-end: 0px none rgb(0, 0, 0); border-inline-start: 0px none rgb(0, 0, 0); border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-right: 45px; min-height: 0px; padding-left: 0px; tab-size: 4; white-space: pre; margin-right: 45px; "><span style="margin-right: 0px; ">          0 1 0 1 1</span></span></div><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-inline-end: 1px solid rgb(233, 233, 233); border-inline-start: 1px solid rgb(233, 233, 233); border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-height: 18px; padding-left: 4px; white-space: nowrap; "><span style="border-inline-end: 0px none rgb(0, 0, 0); border-inline-start: 0px none rgb(0, 0, 0); border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-right: 45px; min-height: 0px; padding-left: 0px; tab-size: 4; white-space: pre; margin-right: 45px; "><span style="margin-right: 0px; ">          1 0 0 0 1</span></span></div><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-inline-end: 1px solid rgb(233, 233, 233); border-inline-start: 1px solid rgb(233, 233, 233); border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-height: 18px; padding-left: 4px; white-space: nowrap; "><span style="border-inline-end: 0px none rgb(0, 0, 0); border-inline-start: 0px none rgb(0, 0, 0); border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-right: 45px; min-height: 0px; padding-left: 0px; tab-size: 4; white-space: pre; margin-right: 45px; "><span style="margin-right: 0px; ">          1 1 0 0 0]</span></span></div></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 10px; text-align: left; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">the answer is:</span></span></div><div style="background-color: rgb(247, 247, 247); border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-bottom: 10px; margin-left: 3px; margin-right: 3px; margin-top: 10px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; "><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-inline-end: 1px solid rgb(233, 233, 233); border-inline-start: 1px solid rgb(233, 233, 233); border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-height: 18px; padding-left: 4px; white-space: nowrap; "><span style="border-inline-end: 0px none rgb(0, 0, 0); border-inline-start: 0px none rgb(0, 0, 0); border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-right: 45px; min-height: 0px; padding-left: 0px; tab-size: 4; white-space: pre; margin-right: 45px; "><span style="margin-right: 0px; "> moves = [5 7 23]</span></span></div></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 10px; text-align: left; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">In this first problem, all boards have solutions of only three moves.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">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.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">As a potential starting point, you might check out one or more of the following resources by</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/44751-lights-out-1-5x5-3-moves/edit#null"><span style=""><span style="">Vicente Muñoz</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">;</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/44751-lights-out-1-5x5-3-moves/edit#null"><span style=""><span style="">Chen, et al.</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">;</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/44751-lights-out-1-5x5-3-moves/edit#null"><span style=""><span style="">Vincent Russo</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">;</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/44751-lights-out-1-5x5-3-moves/edit#null"><span style=""><span style="">Margherita Barile (on wolfram.com)</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">;</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/44751-lights-out-1-5x5-3-moves/edit#null"><span style=""><span style="">Keith Schwarz</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">; or</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> </span></span><a target='_blank' href = "https://dc.ewu.edu/cgi/viewcontent.cgi?referer=https://www.google.com/&amp;httpsredir=1&amp;article=1166&amp;context=theses"><span style=""><span style="">Rebecca Meyer (a master's thesis)</span></span></a><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">.</span></span></div><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-bottom: 9px; margin-left: 4px; margin-right: 10px; margin-top: 2px; text-align: left; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style="">Next:</span></span><span style="display: inline; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; "><span style=""> </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/44752-lights-out-2-5x5-4-moves"><span style=""><span style="">5x5, 4 moves</span></span></a></div></div></div>

<https://en.wikipedia.org/wiki/Lights_Out_(game) Lights Out> 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

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]

the answer is:

moves = [5 7 23]

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 <http://www.mat.ucm.es/~vmunozve/lights-out.pdf Vicente Muñoz>; <http://www.ijritcc.org/download/browse/Volume_5_Issues/August_17_Volume_5_Issue_8/1503304082_21-08-2017.pdf Chen, et al.>; <http://vprusso.github.io/blog/2017/the-mathematics-of-lights-out/ Vincent Russo>; <http://mathworld.wolfram.com/LightsOutPuzzle.html Margherita Barile (on wolfram.com)>; <http://www.keithschwarz.com/interesting/code/?dir=lights-out Keith Schwarz>; or <https://dc.ewu.edu/cgi/viewcontent.cgi?referer=https://www.google.com/&httpsredir=1&article=1166&context=theses Rebecca Meyer (a master's thesis)>.

Next: <https://www.mathworks.com/matlabcentral/cody/problems/44752-lights-out-2-5x5-4-moves 5x5, 4 moves>

Solve

Solution Stats

132 Solutions
18 Solvers

Last Solution submitted on Jun 12, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers18

Problem Tags

flip game lamp light lights logic out puzzle toggle

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

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

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers18

Suggested Problems

More from this Author139

Problem Tags

Community Treasure Hunt

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

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers18

Suggested Problems

More from this Author139

Problem Tags

Community Treasure Hunt

Players