Spiral Galaxies is a puzzle played on a
The figure shows an instance of Spiral Galaxies (left) and a possible solution (right) in which the galaxies have been highlighted.
The problem of deciding whether an instance of Spiral Galaxies admits a solution is NP-Complete [1].
A solution can be found in
A solution for the variant in which all galaxies need to be rectangular can be found in
There exist instances of Spiral Galaxies with
[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.
[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]" }