Генерация "уникальных" матриц

Question

Это может быть скорее математический вопрос, чем вопрос программирования, но, поскольку я специально работаю на c ++, я подумал, что, возможно, есть библиотека или что-то, о чем я не знаю. В любом случае, я работаю над игрой, в которой я генерирую несколько булевых массивов X by X и случайным образом присваиваю Y из них значение true. Думаю, тетрис блокирует такие вещи. Что мне нужно знать, так это умный способ генерирования «уникальных» массивов без необходимости вращать массив 4 раза и сравнивать каждый раз. Чтобы снова использовать тетрис в качестве примера. фигура "L" - это фигура "L", независимо от того, как она вращается, но фигура "J" - это другая уникальная фигура. В качестве дополнительного вопроса, есть ли способ определить максимальное количество уникальных возможных конфигураций для массива X by X с Y заполненными элементами?

Answer 1

Вы можете суммировать (x-X/2)^2 + (y-X/2)^2 для каждого (x, y) истинного элемента сетки. Это эффективно дает квадрат расстояния от центра вашей сетки до каждой «истинной» клетки. Две сетки, которые одинаковы при повороте, имеют то свойство, что их «истинные» ячейки находятся на одинаковом расстоянии от центра, поэтому эта сумма также будет одинаковой. Если все сетки имеют уникальные суммы квадратов, они уникальны при вращении.

Обратите внимание, что хотя уникальные суммы не гарантируют дублирование вращения, обратное утверждение неверно; две несоответствующие сетки могут иметь одинаковую сумму квадратов.

Если ваши сетки довольно малы, и вы изо всех сил пытаетесь максимизировать количество различных шаблонов, вы, вероятно, захотите проверить их с равными суммами. В противном случае, если ваш генератор выплевывает сетку с суммой квадратов, которая соответствует ранее созданной сетке, отклоните ее.

Answer 2

То, что вы можете сделать, это создать базовую c форму: каким-то образом однозначно решить, какая из 4 возможных ориентаций является базовой c, а затем сравнить их только с помощью базовых c форм.

Как решить, какая форма является базовой c? Это на самом деле не имеет значения, если оно последовательное. Скажем, выберите самую высокую в соответствии с лексикографическим сравнением.

Редактировать: О количестве уникальных фигур: грубо говоря, это биномиальное число (n^2 over k)/4 - только то, что оно не учитывает симметричные формы, которые сохранились с поворотом на 180 °, хотя для сравнения имеется только несколько таких форм (по крайней мере, для больших n, k).

Примечание: следует также учитывать случай форм, отличающихся только смещением.