Maximum arrangements of nonattacking kings on the 2n × 2n chessboard

Brown, Tricia Muldoon

doi:10.2478/rmm-2025-0003

Abstract

To count the number of maximum independent arrangements of n² kings on a 2n × 2n chessboard, we build a 2ⁿ × (n + 1) matrix whose entries are independent arrangements of n kings on 2 × 2n rectangles. Utilizing upper and lower bound functions dependent of the entries of the matrix, we recursively construct independent solutions, and provide an equation and algorithm.

References

[AM66] M. Abramson and W. Moser, Combinations, Successions and the n-Kings Problem, Math. Mag. (1966) pp. 269–273.
Search in Google Scholar Back to article
[BS09] J. Bell and B. Stevens, A survey of known results and research areas for n-queens, Discrete Math. 309 (2009) no. 1, pp. 1–31.
Search in Google Scholar Back to article
[Bro19] T. M. Brown, The problem of pawns, Elec. J. Combin. 22(3) (2019) P3.21.
Search in Google Scholar Back to article
[Brown] T. M. Brown, Nonattacking Arrangements of Kings on Even Length Chessboard, Mathematica Notebook Archive, https://notebookarchive.org/2022-02-0zki6rn.
Search in Google Scholar Back to article
[CJPRSY06] N. J. Calkin, K. James, S. Purvis, S. Race, K. Schneider and M. Yancey, Counting kings: as easy as λ₁, λ₂, λ₃, . . ., Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 183 (2006) pp. 83-95.
Search in Google Scholar Back to article
[CJPRSY06] N. J. Calkin, K. James, S. Purvis, S. Race, K. Schneider and M. Yancey, Counting kings: explicit formulas, recurrence relations, and generating functions! Oh my!, Proceedings of the Thirty-Seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 182 (2006) pp. 41-51.
Search in Google Scholar Back to article
[CW90] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions, J. Symbolic Computation, 9(3) (1990) pp. 251-280.
Search in Google Scholar Back to article
[Dud17] H. E. Dudeney, Amusements in Mathematics, Edinburgh: Thomas Nelson & Sons, Limited (1917).
Search in Google Scholar Back to article
[Knuth] D. Knuth, Non-attacking Kings on a Chessboard, unpublished, https://www-cs-faculty.stanford.edu/~knuth/preprints.html#unpub (1994).
Search in Google Scholar Back to article
[Kot13] V. Kotěšovec, Non-attacking chess pieces, 6ed, self pub. http://www.kotesovec.cz (2013).
Search in Google Scholar Back to article
[Kra42] M. Kraitchik, Mathematical Recreations, New York: W. W. Norton & Company Inc. (1942).
Search in Google Scholar Back to article
[Lar95] M. Larsen, The problem of kings, Elec. J. Combin, 2 (1995), R18.
Search in Google Scholar Back to article
[Mad79] J. S. Madachy, Mathematical Recreations, New York: Dover (1979).
Search in Google Scholar Back to article
[Mathematica20] Wolfram Research, Inc., Mathematica, Version 12.1, Champaign, IL (2020).
Search in Google Scholar Back to article
[OEIS] N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org (2020).
Search in Google Scholar Back to article
[Wat04] J. J. Watkins, Across the Board; The Mathematics of Chessboard Problems, Princeton: Princeton University Press (2004).
Search in Google Scholar Back to article
[Wil95] H. Wilf, The problem of kings, Elec. J. Combin., 2 (1995), R3.
Search in Google Scholar Back to article
[YY64] A. Yaglom and I. Yaglom, Challenging Mathematical Problems with Elementary Solutions. Vol I: Combinatorial Analysis and Probability Theory (Trans. James McCawley, Jr.), San Francisco, CA: Holden-Day Inc. (1964, Revised and edited by Basil Gordon).
Search in Google Scholar Back to article

Maximum arrangements of nonattacking kings on the 2n × 2n chessboard

Abstract

Paradigm

My account