Nonomino

A nonomino or Jigsaw Sudoku puzzle, as seen in the Sunday Telegraph

A nonomino (or 9-omino) is a polyomino of order 9, that is, a polygon in the plane made of 9 equal-sized squares connected edge-to-edge.[1] The name of this type of figure is formed with the prefix non(a)-. When rotations and reflections are not considered to be distinct shapes, there are 1,285 different free nonominoes. When reflections are considered distinct, there are 2,500 one-sided nonominoes. When rotations are also considered distinct, there are 9,910 fixed nonominoes.[2]

Symmetry

The 1,285 free nonominoes can be classified according to their symmetry groups:[2]

Unlike octominoes, there are no nonominoes with rotational symmetry of order 4 or with two axes of reflection symmetry aligned with the diagonals.

If reflections of a nonomino are considered distinct, as they are with one-sided nonominoes, then the first and fourth categories above double in size, resulting in an extra 1,215 nonominoes for a total of 2,500. If rotations are also considered distinct, then the nonominoes from the first category count eightfold, the ones from the next three categories count fourfold, the ones from the fifth category count twice, and the ones from the last category count only once. This results in 1,196 × 8 + (38+26+19) × 4 + 4 × 2 + 2 = 9,910 fixed nonominoes.

Packing and tiling

37 nonominoes have holes.[3][4] Therefore a complete set cannot be packed into a rectangle and some admit no tilings. However, 1050 free nonominoes (all but 235) do admit tilings;[5] of the tiling nonominoes, all but two of them form a patch of at least one tile satisfying the Conway criterion, the two exceptions shown to the right. This is the lowest order of polyomino for which such exceptions exist.[6]
One nonomino has a two-square hole (second rightmost in the top row) and is the smallest polyomino with such a hole.

References

  1. Golomb, Solomon W. (1994). Polyominoes (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 0-691-02444-8.
  2. 1 2 Redelmeier, D. Hugh (1981). "Counting polyominoes: yet another attack". Discrete Mathematics 36: 191–203. doi:10.1016/0012-365X(81)90237-5.
  3. Weisstein, Eric W., "Polyomino", MathWorld.
  4. "Sloane's A001419 : Number of n-celled polyominoes with holes", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  5. Rawsthorne, Daniel A. (1988). "Tiling complexity of small n-ominoes (n<10)". Discrete Mathematics 70: 71–75. doi:10.1016/0012-365X(88)90081-7.
  6. Rhoads, Glenn C. (2005). "Planar tilings by polyominoes, polyhexes, and polyiamonds". Journal of Computational and Applied Mathematics 174 (2): 329–353. doi:10.1016/j.cam.2004.05.002.
This article is issued from Wikipedia - version of the Sunday, March 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.