Counting Star-Battle configurations. (English) Zbl 07702678
Summary: Given an \(n\times 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.
MSC:
| 05B15 | Orthogonal arrays, Latin squares, Room squares |
| 05A15 | Exact enumeration problems, generating functions |
| 00A08 | Recreational mathematics |
References:
| [1] | https://krazydad.com/twonottouch/ |
| [2] | Bell, J.; Stevens, B., A survey of known results and research areas for n-queens, Discret. Math., 309, 1, 1-31 (2009) · Zbl 1228.05002 · doi:10.1016/j.disc.2007.12.043 |
| [3] | Berend, D., On the number of Sudoku squares, Discret. Math., 341, 11, 3241-3248 (2018) · Zbl 1395.05010 · doi:10.1016/j.disc.2018.08.005 |
| [4] | Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P.; Sutphen, S., Checkers is solved, Science, 317, 5844, 1518-1522 (2007) · Zbl 1226.00005 · doi:10.1126/science.1144079 |
| [5] | Steinerberger, S., On the number of positions in chess without promotion, Int. J. Game Theory, 44, 3, 761-767 (2015) · Zbl 1388.91080 · doi:10.1007/s00182-014-0453-7 |
| [6] | Tromp, J.: The number of legal go positions. In: Plaat, A., Kosters, W., van den Herik, J. (eds.) Computers and Games. CG 2016. Lecture Notes in Computer Science, vol 10068. Springer (2016) · Zbl 1398.91133 |
| [7] | Spahn, G., Enumerating solutions to grid-based puzzles with a fixed number of rows, Math. Comput. Sci. (2022) · Zbl 07570271 · doi:10.1007/s11786-022-00530-x |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
