Lights Out is a logic game wherein all lights need to be turned off to complete each board. See the first problem in the series for an introduction.
This problem contains boards that each require six moves to solve. For example, if
board = [1 0 1 0 1
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
1 0 1 0 1]the answer is:
moves = [1 5 11 15 21 25]
Prev.: 5x5, 4 moves — Next: 5x5, 8 moves
Solution Stats
Problem Comments
10 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers20
Suggested Problems
-
Sort a list of complex numbers based on far they are from the origin.
5796 Solvers
-
1713 Solvers
-
Number of 1s in the Binary Representation of a Number
479 Solvers
-
Omit columns averages from a matrix
618 Solvers
-
Given a window, how many subsets of a vector sum positive
871 Solvers
More from this Author139
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Will problem "Lights Out 3 - 5x5, 12 moves" be created?
nchoosek(25, 12) = 5200300, not so big.
It can also be solved by brute-forces.
please merge problem "Lights Out 3 - 5x5, 3 moves", "Lights Out 3 - 5x5, 4 moves" , "Lights Out 3 - 5x5, 6 moves" and "Lights Out 3 - 5x5, N moves"(not publish yet), becase they can be solve by same brute-force method.
@li haitao: I understand that you might not want to see so many problems in the series, but they are purposefully building up to larger, more difficult problems in a pedantic fashion so as to be accessible to a broad range of users.
It is rather curious that you make such comments about being able to solve these problems using brute-force methods without having solved any of them, as far as I can see. I have timed each of the submitted problems for the three problems so far using Cody servers, and they yield the following approximate times:
#1 (3 moves): 1/4 to 1/2 second
#2 (4 moves): 1/2 to 2 seconds
#3 (6 moves): 25 to 30 seconds (this includes a modified solution from a prior problem)
As far as I am aware, the Cody servers time out at 30 seconds, so further problems will not be solvable by brute-force methods. I tested that on a planned problem with more moves using two modified solutions from prior problems, and they do appear to time out. While it is technically possible to solve many of these (current and planned) problems by brute-force methods, it is not practically feasible (or possible on Cody due to server time limits). The number of test cases in future problems generally increases or stays at a high number to help prevent brute-force methods from working.
I added various references to the first problem in the series as potential starting points for developing actual solvers. I would encourage you to check them out and try these first problems without using brute-force methods that will only go so far.
@goc "#3 (6 moves): 25 to 30 seconds"
My brute-force solution runs less than 2 second.
@goc I admit that it's hard to solve "12 moves" less than 30 seconds using brute-force methods in cody's computer(but less than 30 seconds in my computer).
I'm glad to see some elegent methods in the future.
@goc "#3 (6 moves): 25 to 30 seconds" My brute-force solution runs less than 0.8 second.
https://ww2.mathworks.cn/matlabcentral/cody/problems/44753-lights-out-3-5x5-6-moves/solutions/1668893
@li haitao: While your solution does solve many test cases in under 0.8 seconds, the times above were referring to the total time for the whole test suite. When your times are added up for all the test cases, the total time is over 4 seconds. While less than the total time for other solutions, it is still increasing over other problems with fewer moves. Also, as I already mentioned, future problems will tend to have even more test cases, making it harder to solve some within the time limit. And, the final problems will most definitely not be solvable by brute-force methods.
@goc3
With brute-force Alfonso solution you can solve everything, everywhere, every time...
@goc3
To be clear, I speak about Solution 1720010 of Alfonso (https://www.mathworks.com/matlabcentral/cody/problems/44755-lights-out-4-5x5-8-moves/solutions/1720010).
Incredible no ?
@Jean-Marie Sainthillier: Amazing. I'll have to make sure that some later problems in the series can't be brute forced, even by him, though he may still find a way. These test suites take long enough to create as it is.