Central grid symmetry

Investigating one optimization problem, I encountered the problem of symmetry of configurations with a direct enumeration of options. A similar problem arises in some solutions of the eight-queen problem . Exploring the central symmetry of a rectangular grid, I found a revolutionary, quite an interesting method for determining and testing symmetric configurations using reversible numbers.

A little bit about symmetry

Central symmetry or symmetry with a center at a point is a transformation of space that takes a point X to a point X 'so that the center of symmetry is the center of the segment XX'. A figure is called symmetric with respect to point A, if for each point of the figure its symmetric point with respect to point A also belongs to this figure.

If we are talking about the central symmetry of a grid consisting of cells, then we will be talking not about points, but about grid cells. For example, after a centrally symmetric transformation of a chessboard, cell A1 will take the place of H8, A2 - on H7, and B1 - on G8.
In this article we will use a rectangular grid. Like the rectangle, such a grid has two axes of symmetry and one center, but concentrate only on the central symmetry.

Essence of the question

There is a grid size of 3 to 6 cells. Also in the presence of a list of 14 components, any of which can be put in any cell, with possible repetitions. The number of options for filling such a grid with repetitions is equal to 14 ¹⁸ , it would be nice to reduce them by half, discarding the filling options that are centrally symmetric to those already tested. For simplicity of output, let the components be numbers from 0 to 13 inclusive. The list of 18 components is generated by the product function from the itertools package (to be exact, the function returns a tuple iterator that, like the odometer, changes the right-standing element at each iteration). This list of columns and fills the grid.
')

Task: Exclude grid fill options that are centrally symmetric to already proven options.

Implementation

Let us number the cells by columns, starting from the upper left corner, from 0 to 17. We will try for each configuration to find the number symmetrical to it with respect to the center. Numbering configurations, as usual, from scratch.

The configuration 0 (all cells with zeros) is obviously symmetrical to itself: 0 -> 0.

Configuration 1. Cell 17 gets 1, the rest with zeros. The configuration will be symmetrical to it, in which “0” stands in square 0, the rest with zeros. Cell 17 will pass 14 of its values ​​(from 0 to 13) in the first 14 iterations. Cell 16 is also 14, but for each of its configuration there are 14 iterations of cell 17, i.e. for 14 ² , etc. Therefore, cell 0 will pick up 1 for 14 ¹⁷ iterations.

Configuration 2. Cell # 17 gets 2, the rest with zeros. The configuration 2-14 ¹⁴ in which 0 is 2 in square 0, the rest are zero, will be symmetrical to it.

Configuration 3 -> Configuration 3⋅14 ¹⁷

Configuration 4 -> Configuration 4⋅14 ¹⁷ , etc. up to 13 -> 13⋅14 ¹⁷ .

Following this logic, it is necessary to write down the number of the variant, symmetrical to the first, as 114 ¹⁷ , and symmetrical to the zero - as 0⋅14 ¹⁷ .

We already have some list of configuration numbers that are symmetrical to each other:

• 0 and 0⋅14 ¹⁷
• 1 and 1⋅14 ¹⁷
• 2 and 2⋅14 ¹⁷

etc. until 13.

Configuration 14. 1 is in the penultimate cell, the rest are zeros. Symmetrical to it is 1⋅14 ¹⁶ .

Configuration 15. The units in the last two cells, the remaining zeros. Symmetric to it, when 1 in the first two cells, the rest are zeros. 1 becomes cell 0 at iteration 14 ¹⁷ , and after 14 ¹⁶ 1 it will appear in cell 1, therefore the desired configuration will be 14 ¹⁶ + 14 ¹⁷ .

Configuration 16. Element "A" in cell No. 16, "B" - in cell No. 17. Symmetrical to her, obviously 14 ¹⁶ + 2⋅14 ¹⁷ .
...
Configuration 27 -> 1⋅14 ¹⁶ + 13⋅14 ¹⁷ .

Configuration 28 -> 2⋅14 ¹⁶ .

Configuration 29 -> 2⋅14 ¹⁶ + 14 ¹⁷ .

This story continues until iteration 195, which is symmetrical 13⋅14 ¹⁶ + 13⋅14 ¹⁷ . In iteration 196, cell 1 is put 1, the rest are empty. An iteration of 14 ^{15 is} symmetrical to it.

In iteration 197, the unit is also placed in cell No. 17, because it is symmetrical to it - 14 ¹⁵ + 14 ¹⁷ , and so on.

The general law of symmetry of the grid configurations will be:



Then I thought the familiar formula on the left. This is a formula for converting a number from an arbitrary base to a decimal number system. And correspondingly - This is a number in the number system with a base of 14.

It is easy to notice that the number on the right side is written down from the left side in reverse order - if on the left side we “write” the number from right to left, then on the left side we write the same numbers, but from left to right. Simply put, the number on the right is the “flipper” of the number on the left, both of which are recorded in the number system with base 14 and have a length of 18.

Criterion and algorithm validation

If the configuration number is long in the number of cells and recorded in the numeral system with a base equal to the number of elements, less than the proper number of the “changeling”, then the symmetrical configuration has not yet been encountered. If they (numbers) are equal, then we are dealing with a palindrome, which occurs only once and, therefore, is subject to verification.

The validation algorithm itself is as follows:

1. Transfer configuration number to number system with base equal to the number of elements
2. Record number- "Changeling" length 18
3. If the “changeling” is larger than the configuration number, then simulations of this configuration and symmetrical to it have not yet been carried out; if not, then a simulation was performed that was symmetrical to this, therefore skip.

Conclusion

Obviously, this algorithm is applicable not only to determine the central symmetry of the two-dimensional grid, but also the grid in an arbitrary dimension, because it is possible to reduce any such configuration to the list, or to fill the grid with a list, for example, line by line.
The algorithm itself is quite heavy, which raises the question of its applicability in practice. But in the case when checking each configuration costs even more computational resources, it may be worth using it.