Central symmetry of the grid

Studying one optimization problem, I ran into the problem of symmetry of configurations with direct enumeration of options. A similar problem arises in some solutions to the eight queens problem . Investigating the central symmetry of a rectangular grid, I discovered a revolutionary rather interesting method for determining and checking symmetric configurations using “shifter” numbers.

A little bit about symmetry


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

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

Essence of the question


There is a grid of 3 by 6 cells. Also available is a list of 14 components, any of which can be placed in any cell, and repetitions are possible. The number of fill options for such a grid with repetitions is 14 18 , it would naturally be nice to halve them by discarding fill options that are centrally symmetrical to those already tested. For simplicity of output, let the components be numbers from 0 to 13 inclusive. A list of 18 components is generated by the product function from the itertools package (to be precise, the function returns an iterator tuple, which, like an odometer, changes the right-hand element at each iteration). This list is filled in columns with a grid.

Examples of zero, first, second and 178th grid configuration


Objective: Exclude grid filling options that are centrally symmetric to the already verified options.

Implementation


We number the cells in columns, starting from the upper left corner, from 0 to 17. For each configuration, we try to find the number symmetrical to it with respect to the center. Numbering of configurations, as usual, from scratch.

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

Configuration 1. Cell 17 receives 1, the rest with zeros. Symmetric to it will be a configuration in which in cell 0 is “1”, 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 over 14, but each of its configuration accounts for 14 iterations of cell 17, i.e. for 14 2 , etc. Therefore, cell 0 will dial 1 at 14 17 iterations.

Configuration 2.Cell number 17 gets 2, the rest with zeros. The configuration 2⋅14 17 will be symmetric to it , in which in the cell 0 it costs 2, the remaining zeros.

Configuration 3 -> Configuration 3-14 14

Configuration 4 -> Configuration 4-14 17 , etc. to 13 -> 13⋅14 17 .

Following this logic, it is worth writing down the number of the variant symmetrical to the first, as 1⋅14 17 , and symmetrical to the zero, as 0⋅14 17 .

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

  • 0 and 0⋅14 17
  • 1 and 1⋅14 17
  • 2 and 2⋅14 17

etc. to 13.

Configuration 14. 1 is in the penultimate cell, the remaining zeros. Symmetric to it is 1⋅14 16 .

Configuration 15. Units in the last two cells, the rest zeros. Symmetric to it, when 1 in the first two cells, the rest are zeros. 1 becomes in cell No. 0 at iteration 14 17 , and after 14 16 1 will also appear in cell No. 1, therefore, the desired configuration will be numbered 14 16 + 14 17 .

Configuration 16. Element “A” in cell No. 16, “B” in cell No. 17. Symmetric to it, obviously 14 16 + 2⋅14 17 .
...
Configuration 27 -> 1⋅14 16+ 13⋅14 17 .

Configuration 28 -> 2-14 14 .

Configuration 29 -> 2⋅14 16 + 14 17 .

This story continues until iteration 195, which is symmetric 13⋅14 16 + 13⋅14 17 . In iteration 196, cell 1 is set to 1, the rest are empty. Symmetrical thereto iteration 14 15 .

In iteration 197, the unit is also placed in cell No. 17, therefore it is symmetrical to it - 14 15 + 14 17 , etc.

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

image


Then the formula on the left seemed to me familiar. This is the formula for converting a number from a number system with an arbitrary base to decimal. And, accordingly image, this is a number in the base notation 14.

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

Criterion and Validation Algorithm


If the configuration number is long in the number of cells and recorded in the number system with a base equal to the number of elements, it is less than its own “reversal” number, then the symmetric 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. Convert configuration number to number system with base equal to the number of elements
  2. Write down the number-"changeling" of length 18
  3. If the “changeling” is greater than the configuration number, then simulations of this configuration and symmetrical to it have not yet been carried out; if not, then a configuration was symmetric that was symmetrical, therefore, skip.

Or as a code
def validate(number, radix, length):
	fingers = '0123456789abcdefghijklmnopqrstuvwxyz'
	n = number
	# перевод в систему счисления с основанием radix без разворота
	turn = ''
	while n > 0:
		turn += fingers[n % radix]
		n = n // radix
	# добавим недостающие нули до нужной длинны
	turn += '0' * (length - len(turn))
	return number <= int(turn, radix)


Conclusion


Obviously, this algorithm is applicable not only for determining the central symmetry of a two-dimensional grid, but also for an arbitrary dimension grid, because any such configuration can be reduced to a list, or a grid can be filled 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 computing resources, then it may be worth using it.

Also popular now: