3 ms·
I haven't downloaded the app, so maybe this makes sense somehow, but the following text from the app description confused me: Difficulty ratings: - 2x2 board
by smcmurtry 9y ago
I haven't downloaded the app, so maybe this makes sense somehow, but the following text from the app description confused me:
Difficulty ratings:
- 2x2 board - Easy
- 3x3 board - Easy
- 4x4 board - Hard
- 5x5 board - Medium
- 6x6 board - Impossible
- 7x7 board - Hard
Shouldn't the difficulty rating increase with increasing board size?
- rjp0008 9y agoSolving an even square might be inherently harder than an odd square. I haven't played the game though.
- rmal30 9y agoYep, it requires n^2 moves for even boards while odd boards require less moves (no formula found yet). Using a computer, I found, by brute force, that the 5x5 can be solved in 8 moves at most, the problem quickly becomes intractable for 7x7 and above. It looks like this might be NP hard according to another post: http://stackoverflow.com/questions/27436275/how-can-i-further-optimize-this-solver-of-a-variant-of-lights-out http://stackoverflow.com/questions/27436275/how-can-i-furthe...