CCE Faculty Articles
Counting Star-Battle Configurations
Document Type
Article
Publication Title
Mathematics in Computer Science
ISSN
1661-8289
Publication Date
4-24-2023
Abstract
Given an n×n grid of cells, a valid configuration for the Star-Battle problem is a subset of 2n cells—those containing ‘stars’—such that each row and each column contains exactly two stars, and no two stars are orthogonally or diagonally adjacent. The standard Star-Battle game assumes a plane topology in which stars bordering opposite edges of the board are nonadjacent. We present an algorithm for counting the number of distinct valid configurations as a function of n, for plane, cylindrical, and toroidal board topologies. We have run our algorithm up to n = 15, for which the number of valid configurations is equal to 106,280,659,533,411,296 for the plane topology, and somewhat less for the cylindrical and toroidal topologies.
DOI
10.1007/s11786-023-00558-7
Volume
14
Issue
8
NSUWorks Citation
Laszlo, Michael and Mukherjee, Sumitra, "Counting Star-Battle Configurations" (2023). CCE Faculty Articles. 530.
https://nsuworks.nova.edu/gscis_facarticles/530
Comments
Copyright © 2023, The Author(s), under exclusive licence to Springer Nature Switzerland AG
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.