Talk:Polyomino

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Low Priority  Field: Discrete mathematics

Added a sentence of history and the numbers of configurations of various orders. These are the output from a program of my own. Alan Peakall 16:47 Oct 18, 2002 (UTC)

I do not know an efficient algorithm. The algorithm that my own program uses is brute force inductive search. It has a heuristic hashing optimization in its implementation. On a 1GHz pentium machine it finds all 63000+ dodecominoes (ie order 12) in under 90 seconds. Alan Peakall 16:31 Nov 7, 2002 (UTC)


Minor problem: this page says 2D only and is unclear on whether reflections are counted as different. The tetromino page says there are 3D configurations made of cubes; and the pentomino page says mirror-image ones count as the same. -- Tarquin 11:12 Feb 16, 2003 (UTC)

Major Problem: "Polyomino" is a trademark owned by Professor Solomon Golomb. The mathematically correct word to be used instead is "polysquare". All references to polyominoes in Wikipedia, especially the title of this article, should read "polysquare", not "polyomino". Any use of the word 'Polyomino' should be with the high-'TM' trademark sign only. Authors of this article, please read the Wikipedia conventions on copyright! Editors of Wikipedia, please change all references accordingly. Thank you. Karl Scherer


Cheers, Karl Scherer

You say that there's a trademark problem, and that this violates Wikipedia's copyright conventions. Please make up your mind. Thank you. Arvindn 11:46, 16 Mar 2004 (UTC)

Contents

[edit] Greek or Latin??

Is the -omino suffix Greek or Latin?? 4, 5, 6, 7, 8, 10, and 12 are named with Greek numerical prefixes and 9 and 11 are Latin. Is any set rule being followed here?? 66.245.90.209 00:33, 10 Oct 2004 (UTC)

The set rule is to use Greek prefixes, but 9 and 11 are exceptions in many series of this type, e.g. "nonagon".

[edit] article clean up

I have attempted a clean up of the article. The main things I have modified are:

  • structure of the text, headings
  • made more consistent the different definitions of polyominoes: fixed and free, with or without holes
  • added some stats for fixed polyominoes
  • more involved discussion of the group of symmetries between free and fixed polyominoes

I think a few things still need some work:

  • It would be nice to have more details about the generating functions of the special classes of polyominoes. If it is possible, give expressions of the generating functions, or give the asymptotic growth of the number of polyominoes in those classes
  • The explanation of Conway's method and Jensen's method could be more precise. How are generating functions used?

--Bernard Helmstetter 01:47, 24 Dec 2004 (UTC)

[edit] Terminology - free/fixed?

The terminology on this page seems to be pretty mixed up. By my understanding, free polyominoes can be flipped or rotated, so mirror images and rotations don't count as distinct objects, while fixed polyominoes can not be flipped or rotated. But the table seems to have them the other way round. I'm not sure what the middle column, that say "fixed polyominoes with holes" is actually counting.

Yes, I messed it up badly when attempting to clean the article. I think it is corrected now.--Bernard Helmstetter 01:13, 26 Mar 2005 (UTC)


Also, there's no mention of what MathWorld calls one-sided polyominoes, that can be rotated, but not reflected. Since these are the type used in Tetris, it would be nice to enumerate them as well. sjorford →•← 12:03, 18 Mar 2005 (UTC)

[edit] Proposal to delete page "pentominoes"

I think we should remove the page "pentominoes" since there is already a page called "pentomino". Having two articles on the same subject is redundant and not necessary. I moved some of the information in the original "pentominoes" page to the "polyomino" and "pentomino" pages. What are your thoughts on the page deletion? HappyCamper 02:13, 26 Mar 2005 (UTC)

[edit] Reversed move to polysquare

I've reversed the cut-and-paste move to polysquare, as I disagree with the given reason - that it apparently violates a trademark. A web search for polyomino shows that it is used frequently as a generic noun - not that this is conclusive evidence against a move, but it most definitely needs discussion first. Anyway, there's a move button for doing moves properly, for crying out loud.

I haven't merged anything new back into polyomino, as the articles seemed virtually identical to me. sjorford →•← 15:42, 31 May 2005 (UTC)

As I recall, Golomb trademarked “pentominoes,” not “polyominoes,” because he was having plastic sets of pentominoes marketed as toys. See the Wikipedia article on pentominoes. I have seen some writers use “pentaminoes” instead of “pentominoes,” presumably to avoid infringing the trademark. Sicherman 16:09, 9 April 2007 (UTC)

[edit] Karl Scherer

Please be aware that Karl Scherer is not a reliable editor. See Wikipedia:Votes for deletion/Karlscherer3 for further information. ~~~~ 12:54, 23 Jun 2005 (UTC)

[edit] write a formula for the perimiter of a polyomino having area 12 and e eyes

[edit] Growth Method issue

The article states the following:

This method can be optimized so that it counts each polyomino only once, rather than n times. Starting with the initial square, declare it to be the lower-left square of the polyomino. Simply do not number any square which is on a lower row, or left of the square on the same row. With this improvement, the running time is divided by n, so it only takes about 1 second to enumerate the dodecominoes.

While it seems like a good idea, I think it would fail in the case of any polyomino which did not have any corner squares. The most obvious example would be the cross-piece pentomino. No matter how you rotate it, no square of that will ever occupy the lower-left corner (or any other corner) of the field. Obviously, the greater the value of n, the more polyominos will be omitted using this shortcut. I would hope and assume that anyone who researches this seriously would have taken that drawback into account... Lurlock 04:25, 6 May 2007 (UTC)

The "lower-left square" is the leftmost square on the bottom row; in the case of the cross, the (only) square on the bottom square is the lower-left square of the polyomino. This algorithm is that given by Redelmeier (though he has a more efficient method of counting free polyominoes than checking for symmetries after creating each n-omino), and parallel variants have been discussed by other authors; unfortunately the whole article is missing any references, and the figures for time taken are probably original research, as may be the inefficient "Inductive exhaustive search" method (possibly too trivial to have been worth publishing). Joseph Myers 12:11, 6 May 2007 (UTC)

[edit] oxford cite

The Oxford English Dictionary cite goes to the wiki article on the dictionary, as opposed to anything showing the eytomology —Preceding unsigned comment added by 194.72.50.160 (talk) 13:28, 12 December 2007 (UTC)