An alternative algorithm for the n–Queens puzzle

David Luque Sacaluga

doi:10.2478/rmm-2021-0003

Abstract

In this paper a new method for solving the problem of placing n queens on a n×n chessboard such that no two queens directly threaten one another and considering that several immovable queens are already occupying established positions on the board is presented. At first, it is applied to the 8–Queens puzzle on a classical chessboard and finally to the n Queens completion puzzle. Furthermore, this method allows finding repetitive patterns of solutions for any n.

References

[GJN17] Ian P. Gent, Christopher Je erson and Peter Nightingale. “Complexity of n– Queens Completion.” Journal of Artificial Intelligence Research Vol. 59 (2017): 815–848 DOI: https://doi.org/10.1613/jair.551210.1613/jair.5512
Search in Google Scholar Back to article
[CMA21] Clay Mathematis Institute. “P vs NP Problem.” Accessed 21 September, 2021. https://www.claymath.org/millennium-problems/p-vs-np-problem
Search in Google Scholar Back to article
[Coo71] Stephen A. Cook. “The complexity of theorem proving procedures.” Proceedings Third Annual ACM Symposium on the Theory of Computing, 1971.
Search in Google Scholar Back to article
[Sch15] Fred Schuh. The Master book of mathematical recreations. Translated by F. Göbel. New York: Dover Publications, 1968: 34–346
Search in Google Scholar Back to article
[BSR08] Roman Barták, Miguel A. Salido and Francesca Rossi. “Constraint Satisfaction Techniques in Planning and Scheduling.” Journal of Intelligent Manufacturing 21, (2010): 5–15 DOI: https://doi.org/10.1007/s10845-008-0203-4.10.1007/s10845-008-0203-4
Search in Google Scholar Back to article
[BSR10] Roman Barták, Miguel A. Salido and Francesca Rossi. “New Trends in Constraint Satisfaction, Planning, and Scheduling: A Survey.” The Knowledge Engineering Review 25 (3) (2010): 249–279 DOI: https://doi.org/10.1017/S026988891000020210.1017/S0269888910000202
Search in Google Scholar Back to article
[ACP68] Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links. Addison-Wesley Professional, 2019.
Search in Google Scholar Back to article
[ACJ18] Nélia Amado, Susana Carreira and Keith Jones. Broadening the Scope of Research on Mathematical Problem Solving. Springer, 2018: 551–55210.1007/978-3-319-99861-9
Search in Google Scholar Back to article
[PrE17] Thomas B. Preußer and Mathias R. Engelhardt. “Putting Queens in Carry Chains, Noź27.” Journal of Signal Processing Systems, 88(2). (2017):185-–201. DOI: https://doi.org/10.1007/s11265-016-1176-810.1007/s11265-016-1176-8
Search in Google Scholar Back to article
[AY89] B. Abramson and M. Yung. “‘Divide and conquer under global constraints: a solution to the n–queens probelm,” Journal of Parallel and Distributed Computing 6(3), (1989): 649–66210.1016/0743-7315(89)90011-7
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 Mathematics, 309 (2009): 1-–31. DOI: http://dx.doi.org/10.1016/j.disc.2007.12.04310.1016/j.disc.2007.12.043
Search in Google Scholar Back to article
[BD75] A. A. Bruen and R. Dixon. “The n-queen problem.” Discrete Mathematics, 12, (1975): 393—395. DOI: https://doi.org/10.1016/0012-365X(75)90079-510.1016/0012-365X(75)90079-5
Search in Google Scholar Back to article
[BM02] A. P. Burger and C. M. Mynhardt. “An upper bound for the minimum number of queens covering the n×n chessboard.” Discrete Applied Mathematics 121, (2002): 51—60. DOI: https://doi.org/10.1016/S0166-218X(01)00244-X10.1016/S0166-218X(01)00244-X
Search in Google Scholar Back to article
[Eng07] M. R. Engelhardt. “A group-based search for solutions of the n-queens problem.” Discrete Mathematics 307, (2007): 2535—2551. DOI: https://doi.org/10.1016/j.disc.2007.01.00710.1016/j.disc.2007.01.007
Search in Google Scholar Back to article
[ET92] C. Erbas, S. Sarkeshik and M. M. Tanik, “Di erent perspectives of the N– queens problem.” Proceedings ACM Computer Science Conference (1992): 99-–108. DOI: https:/doi.org/10.1145/131214.131227
Search in Google Scholar Back to article
[Ber91] Bo Bernhardsson. “Explicit Solutions to the N–Queens Problem for All N.” ACM SIGART Bulletin 2 (2) (1991). DOI: https://doi.org/10.1145/122319.12232210.1145/122319.122322
Search in Google Scholar Back to article
[GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. ISBN 978-0-7167-1045-5
Search in Google Scholar Back to article
[CMA21] Clay Mathematis Institute. “The 8-Queens Puzzle.” Accessed 21 September, 2021. https://www.claymath.org/events/news/8-queens-puzzle
Search in Google Scholar Back to article

An alternative algorithm for the n–Queens puzzle

Abstract

Paradigm

My account