Lights Out and its unusual uses
Probably some of you have heard of such a puzzle as Lights Out. If someone does not know, the essence in brief is as follows: there is a field of nxn cells, some of the cells are “on”, some are “off”. When you click on a cell, all cells in the area of the cross will switch their state. Like that:
Actually, the task is to make all the cells of the field "turned off". Under the cut something more interesting than just a solution.
The solution algorithm itself is quite tedious and it's a long time to explain it. In short - for the field of each size there is a binary matrix A of all possible moves. If the initial field is represented as a binary vector X, then the solution of the field b is the solution of the system of binary linear equations Ab = X. It is easy to guess that you can invert the matrix A, save it in a variable and find the solution of any field using the formula b = A - 1 X. If someone wants to read more, then there is an amazing article that describes all the nuances. We move on.
')
By the way, the solution does not always exist for any dimension. Sizes 5x5 or 17x17, for example, do not always have a solution, and we do not consider them in this article.
For example, consider the following 20x20 field:
And now let's look at his decision:
Beautiful, is not it? Let's increase the size (and turn off the borders, otherwise it dazzles in their eyes). Take, for example, 75x75:
And look at his decision:
Pretty pretty. But let's not waste time on trifles, but take 150x150 right away:
And his decision will be ... Wow.
Mesmerizing. From a distance, it looks like a city plan. Or an ancient Greek mosaic. Or on the Turkmen carpet. Only for some reason green.
And what happens if you try to get a solution for a solution? We get another pattern derived. And then you can do it again and get another derived pattern.
In this case, sooner or later, the patterns are fixated. For different sizes there are different periods, while for even fields the period is longer than for odd fields (6x6 and 7x7, on large sizes the period is already at several hundred minimum):
At the same time, any derived pattern retains any axial reflective symmetry (animations are not looped, there should be 2045 frames in the looped version):
In addition to the reflectivity, the derived pattern is also capable of maintaining rotational symmetry:
In addition to patterns, Lights Out can be used as a slow, cryptographically unstable (due to determinism), but an exotic hash function.
How exactly to consider it? Well, for example, if you consider the entire field as the initial value, you can use the first two columns of the second derived field as a hash. They retain the main task of the hash function — with a small change in the initial data, the hash changes noticeably. Here, see for yourself:
And only hash:
No animation to notice the difference:
Where can this be applied? Well, probably nowhere. It is too slow for checksums. In cryptography, too, do not apply, because it is very easy to pick up the initial data that gives this hash. But it is unusual.
The last application is to hide data inside the field. You can draw something on the field, then calculate the derived pattern several times and lay it out somewhere. And due to the cyclicity, the initially encrypted field will show itself sooner or later. Here is an example (carefully, a gif in 252 frames). If anything, the data on the 9th frame:
Source app on codeplex . Unfortunately, while there is a version only for Windows.
Actually, the task is to make all the cells of the field "turned off". Under the cut something more interesting than just a solution.
The solution algorithm itself is quite tedious and it's a long time to explain it. In short - for the field of each size there is a binary matrix A of all possible moves. If the initial field is represented as a binary vector X, then the solution of the field b is the solution of the system of binary linear equations Ab = X. It is easy to guess that you can invert the matrix A, save it in a variable and find the solution of any field using the formula b = A - 1 X. If someone wants to read more, then there is an amazing article that describes all the nuances. We move on.
')
By the way, the solution does not always exist for any dimension. Sizes 5x5 or 17x17, for example, do not always have a solution, and we do not consider them in this article.
Pattern generation
For example, consider the following 20x20 field:
And now let's look at his decision:
Beautiful, is not it? Let's increase the size (and turn off the borders, otherwise it dazzles in their eyes). Take, for example, 75x75:
And look at his decision:
Pretty pretty. But let's not waste time on trifles, but take 150x150 right away:
And his decision will be ... Wow.
Mesmerizing. From a distance, it looks like a city plan. Or an ancient Greek mosaic. Or on the Turkmen carpet. Only for some reason green.
And what happens if you try to get a solution for a solution? We get another pattern derived. And then you can do it again and get another derived pattern.
In this case, sooner or later, the patterns are fixated. For different sizes there are different periods, while for even fields the period is longer than for odd fields (6x6 and 7x7, on large sizes the period is already at several hundred minimum):
At the same time, any derived pattern retains any axial reflective symmetry (animations are not looped, there should be 2045 frames in the looped version):
In addition to the reflectivity, the derived pattern is also capable of maintaining rotational symmetry:
Hashes
In addition to patterns, Lights Out can be used as a slow, cryptographically unstable (due to determinism), but an exotic hash function.
How exactly to consider it? Well, for example, if you consider the entire field as the initial value, you can use the first two columns of the second derived field as a hash. They retain the main task of the hash function — with a small change in the initial data, the hash changes noticeably. Here, see for yourself:
And only hash:
No animation to notice the difference:
Where can this be applied? Well, probably nowhere. It is too slow for checksums. In cryptography, too, do not apply, because it is very easy to pick up the initial data that gives this hash. But it is unusual.
Data hiding
The last application is to hide data inside the field. You can draw something on the field, then calculate the derived pattern several times and lay it out somewhere. And due to the cyclicity, the initially encrypted field will show itself sooner or later. Here is an example (carefully, a gif in 252 frames). If anything, the data on the 9th frame:
Source app on codeplex . Unfortunately, while there is a version only for Windows.
Source: https://habr.com/ru/post/255457/
All Articles