24
$\begingroup$

lightssout

https://js13kgames.com/games/lock-puzzle/index.html

The link provides an online puzzle game of $16$ tiles in the form of a $4 \times 4$ matrix of which some entries are in the form of vertical tiles and other in the form of horizontal tiles arranged randomly by the system. Once you press a tile the tile along with all the tiles with same rows and columns get reversed i.e. vertical tiles becomes horizontal and vice versa. In order to solve it all we have to do is to make each of the $16$ tiles vertical.

I have solved it yesterday taking about half an hour. But I don't remember all the methods I used. My question is "Is there any algorithmic way of solving this puzzle which needs small amount of time"?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
48
$\begingroup$

There is an easy way to solve it in the minimum number of moves.

For any square you can look at the seven tiles in the same row or same column, and count how many horizontal and how many vertical tiles there are. You want the number of vertical tiles to be odd, or equivalently the number of horizontal tiles to be even. If that is not the case, click the square to flip the seven tiles.

Apply the above rule for each of the 16 squares, and the puzzle will be solved.

The reason this works is:

Consider the 7 tiles that lie in the row or column of a particular square. Clicking the square would flip all 7 tiles, clicking a different square in the same row or column would flip 4 of those seven tiles, and clicking any other square would flip only 2 of those seven tiles. Flipping 2 or 4 tiles cannot change the parities - if the number of vertical tiles is odd it remains odd, if it's even it remains even. The only way to change the number of vertical tiles from even to odd is by pressing the chosen square.

Improve this answer
$\endgroup$
9
  • 3
    $\begingroup$ After applying this technique to the 16 squares, you need one final flip to make all of them vertical. But why does it work? $\endgroup$
    – Shivansh Sharma
    Commented Apr 1, 2020 at 6:09
  • $\begingroup$ It seems to me that you have your parity backwards in your answer. The goal is to get all the tiles vertical, not horizontal. $\endgroup$
    – Ian MacDonald
    Commented Apr 1, 2020 at 21:30
  • 1
    $\begingroup$ Ah, I read your statement wrong. I had interpreted it as "find one where it's odd, ...". Yes. $\endgroup$
    – Ian MacDonald
    Commented Apr 1, 2020 at 22:40
  • 5
    $\begingroup$ Is there an intuitive way to see that the only configuration where every square's parity is odd is when all bars on the board are vertical? $\endgroup$
    – Jafe
    Commented Apr 2, 2020 at 12:38
  • 2
    $\begingroup$ @jafe Good question. I don't know. The only way I know is to show that (1) a single tile can be flipped by clicking the 7 squares in the same row or column (2) Therefore all tile patterns are solvable (3) Hence one-to-one relationship between $2^{16}$ tile patterns and $2^{16}$ clicking patterns. The solution method in my answer can create $2^{16}$ solutions, since each button press is determined independently of whether other buttons have been pressed. So with this method no two tile patterns can give the same solution, and the all-vertical tile pattern is the only one with zero clicks. $\endgroup$
    – Jaap Scherphuis
    Commented Apr 2, 2020 at 13:09
17
$\begingroup$

I don't know why this works, but I tried my old strategy from other similar puzzles and it has worked in several cases so far:

Make a note of all squares with horizontal lines initially. Click each of these squares once.

Then,

Do the same thing until it is solved: make a note of all squares with a horizontal line now. Click each of them once. Repeat and eventually you will solve it.

One final note - since I don't know why it works, I also can't prove that it always works, unfortunately. But in my many years of solving puzzles in this genre, that strategy always seems to eventually land on a solution.

Edit: See Jaap Scherphuis's comment and answer for an explanation of why this works.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Oh! What a brilliant way. I have solved it using your ways in less than $5$ minutes. Nice observation +1. $\endgroup$
    – math maniac.
    Commented Apr 1, 2020 at 5:47
  • $\begingroup$ Now it's a matter of fact why should the process work? Actually the process you are trying to do is to make all the horizontal tiles vertical after each move and this process gradually converge. $\endgroup$
    – math maniac.
    Commented Apr 1, 2020 at 5:48
  • 5
    $\begingroup$ It is easy to see that after the first round, every row and every column will have an even number of horizontal tiles. From my answer you can then see that a second round will solve the puzzle. $\endgroup$
    – Jaap Scherphuis
    Commented Apr 1, 2020 at 5:51
  • $\begingroup$ Oh, I proved this in one of my high school research projects! To me it's quite an interesting result. $\endgroup$
    – greenturtle3141
    Commented Apr 8, 2020 at 7:28
  • $\begingroup$ I’d argue this way is fastest $\endgroup$
    – Cotton Headed Ninnymuggins
    Commented Feb 4, 2021 at 6:34
12
$\begingroup$

Each cells operates one of sixteen NOT switches, each one of which changes seven cells. Cells that are vertical need to be changed an even number of times, cells that are horizontal need to be affected by an odd number of switches.

Given a particular state $S$, we need to find a solution to: $$S=\sum_\limits{k=1}^{16} \delta_{k}S_i \pmod 2 $$ because each switch $S_i$ has the property that $S_i^2=I$, therefore $\delta_k\in\{0,1\}$. So we get $16$ equations in $16$ unknowns, of the (example) form: $$S_2+S_5+S_6+S_7+S_8+S_{10}+S_{14}=x_6$$ and this can be solved using Gaussian Elimination over $GF_2$.

Or, create a new blank board, and click on it all the positions of the 'on' switches from the original board. Take this new pattern back to the original board, and click every 'off' position from the new board onto the original board. All lights are on!

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Oh, the good old days of linear algebra! +1 for the mathematics. $\endgroup$
    – ThatOneNerdyBoy
    Commented Apr 1, 2020 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.