24

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"?

JMP
  • 35,612
  • 7
  • 78
  • 151
math maniac.
  • 423
  • 4
  • 10

3 Answers3

48

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.

Jaap Scherphuis
  • 53,019
  • 7
  • 120
  • 208
  • 3
    After applying this technique to the 16 squares, you need one final flip to make all of them vertical. But why does it work? – Shivansh Sharma Apr 01 '20 at 06:09
  • It seems to me that you have your parity backwards in your answer. The goal is to get all the tiles vertical, not horizontal. – Ian MacDonald Apr 01 '20 at 21:30
  • @IanMacDonald Which is why the number of vertical tiles amongst the seven forming a row and column should be odd, and if it isn't, you make it odd by flipping them. In the solved position they are all odd since 7 is odd. – Jaap Scherphuis Apr 01 '20 at 21:39
  • 1
    Ah, I read your statement wrong. I had interpreted it as "find one where it's odd, ...". Yes. – Ian MacDonald Apr 01 '20 at 22:40
  • Clicking one tile flips seven, but clicking two tiles in the same row flips four? You lost me – Andreas Apr 02 '20 at 12:00
  • @Andreas: Consider the 7 tiles formed by the top row and the left column. Only think of those 7 tiles and imagine the rest of the board is empty. If I click the top-right square, then the four tiles of the top row are flipped but none of the rest of left column. If instead I click the bottom-right square, only two tiles are flipped, one in the top row and one in the left column. – Jaap Scherphuis Apr 02 '20 at 12:16
  • 5
    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? – Jafe Apr 02 '20 at 12:38
  • 2
    @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. – Jaap Scherphuis Apr 02 '20 at 13:09
  • Yeah, I kind of just played around with it as if it were a Rubik’s cube. Tried to come up with my own algorithms for certain situations, I eventually got a pretty good pace going. But man, this answer just throws all that out the window! I almost laugh hysterically at how simple this apparently was. It makes sense too, very good explanation – Cotton Headed Ninnymuggins Feb 04 '21 at 06:37
17

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.

hdsdv
  • 5,180
  • 18
  • 29
12

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!

JMP
  • 35,612
  • 7
  • 78
  • 151