Spiral Galaxies

A puzzle in which the player tiles a grid with polyominos with 180° rotational symmetry about given centers.

Description

Spiral Galaxies is a puzzle played on a n×m grid of squares containing a collection C of center points (represented as dots). Center points can appear both in the center of a grid square, or in the center of an edge connecting two neighboring squares. The goal is to find a tiling of the grid with polyominos such that each polyomino (also called a galaxy) contains exactly one center cC and is 180° rotationally symmetric about c.

The figure shows an instance of Spiral Galaxies (left) and a possible solution (right) in which the galaxies have been highlighted.

Computational complexity

The problem of deciding whether an instance of Spiral Galaxies admits a solution is NP-Complete [1].

A solution can be found in 4nm2n+mpoly(nm) time [2] and by an FPT algorithm parameterized in the number of corners of a solution (a corner is an internal vertex of the grid such that 1, 3, or 4 of the 4 neighboring squares belong to the same galaxy) [2].

A solution for the variant in which all galaxies need to be rectangular can be found in |C|!poly(|C|lognm) time [2].

Notes

There exist instances of Spiral Galaxies with |C|=O(1) and an arbitrarily large number of corners [2].

[3] shows 36 Spiral Galaxies instances whose unique solutions form the 10 Arabic numerals and the 26 uppercase letters of the ISO basic Latin alphabet. A corresponding interactive tool is available here.

References

[1] E. Friedman, “Spiral Galaxies Puzzles are NP-complete”.

[2] G. Fertin, S. Jamshidi, C. Komusiewicz, “Towards an Algorithmic Guide to Spiral Galaxies” in FUN 2014.

[3] W. Anderson, E. D. Demaine, M. L. Demaine, “Spiral Galaxies Font”, The Mathematics of Various Entertaining Subjects Volume 3: The Magic of Mathematics.

@misc{cog:spiral-galaxies,
    author = "{CoG contributors}",
    title  = "{Spiral Galaxies --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/spiral-galaxies/",
    note   = "[Online; accessed 2024-05-28]"
}