Нономино - Nonomino

Нономино или Головоломка Судоку головоломка, как видно на Sunday Telegraph

А нономино (или 9-омино) это полимино порядка 9, то есть многоугольник в самолет состоит из 9 одинаковых по размеру квадраты соединены встык.[1] Название этого типа фигур состоит из приставки не (а) -. Когда вращения и размышления не считаются отдельными формами, существует 1285 различных свободный нономино. Когда отражения считаются отчетливыми, получается 2500 односторонний нономино. Когда вращения также считаются отдельными, имеется 9 910 исправлено нономино.[2]

Симметрия

1285 бесплатных нономино можно классифицировать в соответствии с их группы симметрии:[2]

Отражение-симметричный-нономино-90-deg.svg

  • 26 нономино имеют ось симметрии отражения под углом 45 ° к линиям сетки. Их группа симметрии состоит из двух элементов: тождества и диагонального отражения.

Отражательно-симметричные нономино 45-deg.svg

  • 19 нономино обладают точечной симметрией, также известной как вращательная симметрия порядка 2. Их группа симметрии состоит из двух элементов: идентичности и поворота на 180 °.

C2-Вращательно-симметричные nonominoes.svg

  • 4 нономино имеют две оси симметрии отражения, обе совпадающие с линиями сетки. Их группа симметрии состоит из четырех элементов: идентичности, двух отражений и поворота на 180 °. Это группа диэдра порядка 2, также известный как Кляйн четыре группы.

D2 Симметричное вращение и отражение Nonominoes.svg

  • 2 нономино имеют четыре оси симметрии отражения, выровненные с линиями сетки и диагоналями, и вращательную симметрию четвертого порядка. Их группа симметрии, двугранная группа порядка 4, состоит из восьми элементов.

D4 Симметричное вращение и отражение Nonominoes.svg

в отличие октимино, нет нономино с вращательной симметрией 4-го порядка или с двумя осями симметрии отражения, совмещенными с диагоналями.

Если отражения нономино считаются отдельными, как в случае односторонних нономино, то первая и четвертая вышеупомянутые категории удваиваются по размеру, что приводит к дополнительным 1215 нономино, всего 2500. Если ротации также считаются различными, то нономино из первой категории засчитывается восьмикратно, из следующих трех категорий засчитывается четырехкратно, из пятой категории засчитывается дважды, а из последней категории засчитывается только один раз. В результате получается 1,196 × 8 + (38 + 26 + 19) × 4 + 4 × 2 + 2 = 9910 фиксированных нономино.

Упаковка и укладка

Критерий Конвея ложноотрицательный nonominoes.svg

В 37 нономино дырки.[3][4] Поэтому полный комплект не может быть упакованный в прямоугольник, и не все нономино имеют мозаики. Из 1285 бесплатных нономино 960 удовлетворяют требованиям Критерий Конвея и еще 88 могут образовать заплатку, удовлетворяющую этому критерию. Однако 1050 (а не 1048) бесплатных нономино допускают мозаики,[5] два исключения, показанные справа. Это самый низкий порядок полимино, для которого существуют такие исключения.[6]

Один нономин имеет отверстие в виде двух квадратов (второе крайнее правое в верхнем ряду) и является самым маленьким полимино с таким отверстием.37 Nonominoes with Holes.svg

использованная литература

  1. ^ Голомб, Соломон В. (1994). Полимино (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN  0-691-02444-8.
  2. ^ а б Редельмайер, Д. Хью (1981). «Подсчет полимино: еще одна атака». Дискретная математика. 36: 191–203. Дои:10.1016 / 0012-365X (81) 90237-5.
  3. ^ Вайсштейн, Эрик В. «Полёмино». MathWorld.
  4. ^ Слоан, Н. Дж. А. (ред.). «Последовательность A001419 (Количество n-клеточных полиамино с отверстиями)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
  5. ^ Росторн, Дэниел А. (1988). «Сложность плитки малая п-омино (п<10)". Дискретная математика. 70: 71–75. Дои:10.1016 / 0012-365X (88) 90081-7.
  6. ^ Роадс, Гленн С. (2005). «Плоские мозаики из полимино, полигексов и полиалмазов». Журнал вычислительной и прикладной математики. 174 (2): 329–353. Дои:10.1016 / j.cam.2004.05.002.