4 ms·

Polyominoes (2019)

26 points by fatneckbeardz 4y ago

fatneckbeardz 4y ago
A 404 page book on polyominoes
- deleted 4y ago
  [deleted]
- tartakovsky 4y ago
  No wonder it doesn’t load.
tyleo 4y ago
Upon reading the first few pages and seeing the pictures I realized that all Tetris pieces are made of shapes with 4 adjacent cells. Additionally, all permutations of 4-cell shapes are represented in Tetris. It also clicked that the prefix is similar to tetra. I suspect many other folks realized this already but it was a charming lightbulb moment for myself.
alcover 4y ago
Polyominoes have been obsessing me. Not tiling but counting them. No formula has been yet found. Their free numbers (i.e up to rotations and flipping) go 1, 1, 2, 5, 12, 35, 108, 369, 1285, ... Meaning for ex. there are 5 tetrominoes : ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ The myterious sequence follows a ~4 growth rate. I've been (nowhere as a mathematician) exploring this problem for years, generating them and trying in vain to find patterns in their properties. I'd love readers with a high view in combinatorics telling what they think of this problem. Do you think a formula will one day be found or rather that there can't be a closed one for some necessary reason ?
- lkozma 4y ago
  This is a very nice and deep question. Are you aware of the published research on the problem? The growth rate is indeed around 4 and now known to be strictly above 4: https://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf https://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf If I remember correctly, there was a non-rigorous argument for a concrete conjectured value not far above 4.
  - alcover 4y ago
    Thanks for the link. we obtain 4.00253176 as a certified lower bound How intringing it's strictly just above 4 ! Maybe it has to do with symmetries. The proportion of symmetric polys in successive generations goes towards zero. I suspect that this 'pollutes' the asymptot. About published research, I just glanced at the little I found, (as I often can't do more than glance, being limited in Maths.) Also I prefer to go at it naively first.
- slazaro 4y ago
  First thing that came to mind is, maybe if you don't eliminate symmetries or roations or both, that maybe a clear formula appears? Maybe it's one of those steps that makes it a hard problem.
  - alcover 4y ago
    Alas, a formula for what you suggest (called fixed polyominoes) seems also out of reach.
dynamic_sausage 4y ago
This text seems to quickly get rather technical, with theorems and stuff. I would suggest looking at Golomb's classical Polyominoes first https://archive.org/details/polyominoes00golo/page/n7/mode/2up https://archive.org/details/polyominoes00golo/page/n7/mode/2... If you like playing with polyominoes, there is a really fun chesslike table game inspired by them called Blokus, and someone wrote an open-source engine for it: https://pentobi.sourceforge.io/ https://pentobi.sourceforge.io/ Of course, as already noted in another comment, there's the ultimate tetromino game: Tetris (literally defined as tetromino tennis)...
- cableshaft 4y ago
  There's tons of polyomino games that have come out in the past 8 or so years. I wouldn't necessarily say they do a better job than Blokus did (imo, I really like Blokus), but it's interesting to see what game designers have been doing with the concept lately. Uwe Rosenberg in particular has designed a bunch of games playing around with the polyomino concept, starting with Patchwork, then a trilogy of games Indian Summer, Cottage Garden, and Spring Meadow, and then culminating in a rules-heavy game A Feast for Odin. Phil Walker-Harding designed a very popular one called Barenpark, where you cover spots on a board which unlock different types of tiles and new boards. A recently released game that's been well received that utilizes a lazy susan for tile selection is called Planet Unknown. There's also a tile drafting game called Isle of Cats that's quite popular as well. A game that combines polyominoes with roll and write games that's quite popular is Cartographers. Patchwork kicked off this new trend in board games, and was released in 2014.
NKosmatos 4y ago
A000105: Number of free polyominoes (or square animals) with n cells https://oeis.org/A000105 https://oeis.org/A000105

Polyominoes (2019)

26 points by fatneckbeardz 4y ago

fatneckbeardz 4y ago

A 404 page book on polyominoes

deleted 4y ago
[deleted]
tartakovsky 4y ago
No wonder it doesn’t load.

tyleo 4y ago

Upon reading the first few pages and seeing the pictures I realized that all Tetris pieces are made of shapes with 4 adjacent cells. Additionally, all permutations of 4-cell shapes are represented in Tetris. It also clicked that the prefix is similar to tetra. I suspect many other folks realized this already but it was a charming lightbulb moment for myself.

alcover 4y ago

Polyominoes have been obsessing me. Not tiling but counting them. No formula has been yet found. Their free numbers (i.e up to rotations and flipping) go 1, 1, 2, 5, 12, 35, 108, 369, 1285, ... Meaning for ex. there are 5 tetrominoes : ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ The myterious sequence follows a ~4 growth rate. I've been (nowhere as a mathematician) exploring this problem for years, generating them and trying in vain to find patterns in their properties. I'd love readers with a high view in combinatorics telling what they think of this problem. Do you think a formula will one day be found or rather that there can't be a closed one for some necessary reason ?

lkozma 4y ago
This is a very nice and deep question. Are you aware of the published research on the problem? The growth rate is indeed around 4 and now known to be strictly above 4: https://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf https://page.mi.fu-berlin.de/rote/Papers/pdf/Lambda-4.pdf If I remember correctly, there was a non-rigorous argument for a concrete conjectured value not far above 4.
- alcover 4y ago
  Thanks for the link. we obtain 4.00253176 as a certified lower bound How intringing it's strictly just above 4 ! Maybe it has to do with symmetries. The proportion of symmetric polys in successive generations goes towards zero. I suspect that this 'pollutes' the asymptot. About published research, I just glanced at the little I found, (as I often can't do more than glance, being limited in Maths.) Also I prefer to go at it naively first.
slazaro 4y ago
First thing that came to mind is, maybe if you don't eliminate symmetries or roations or both, that maybe a clear formula appears? Maybe it's one of those steps that makes it a hard problem.
- alcover 4y ago
  Alas, a formula for what you suggest (called fixed polyominoes) seems also out of reach.

dynamic_sausage 4y ago

This text seems to quickly get rather technical, with theorems and stuff. I would suggest looking at Golomb's classical Polyominoes first https://archive.org/details/polyominoes00golo/page/n7/mode/2up https://archive.org/details/polyominoes00golo/page/n7/mode/2... If you like playing with polyominoes, there is a really fun chesslike table game inspired by them called Blokus, and someone wrote an open-source engine for it: https://pentobi.sourceforge.io/ https://pentobi.sourceforge.io/ Of course, as already noted in another comment, there's the ultimate tetromino game: Tetris (literally defined as tetromino tennis)...

cableshaft 4y ago
There's tons of polyomino games that have come out in the past 8 or so years. I wouldn't necessarily say they do a better job than Blokus did (imo, I really like Blokus), but it's interesting to see what game designers have been doing with the concept lately. Uwe Rosenberg in particular has designed a bunch of games playing around with the polyomino concept, starting with Patchwork, then a trilogy of games Indian Summer, Cottage Garden, and Spring Meadow, and then culminating in a rules-heavy game A Feast for Odin. Phil Walker-Harding designed a very popular one called Barenpark, where you cover spots on a board which unlock different types of tiles and new boards. A recently released game that's been well received that utilizes a lazy susan for tile selection is called Planet Unknown. There's also a tile drafting game called Isle of Cats that's quite popular as well. A game that combines polyominoes with roll and write games that's quite popular is Cartographers. Patchwork kicked off this new trend in board games, and was released in 2014.

NKosmatos 4y ago

A000105: Number of free polyominoes (or square animals) with n cells https://oeis.org/A000105 https://oeis.org/A000105