1. bookVolume 8 (2021): Issue 14 (October 2021)
Journal Details
License
Format
Journal
eISSN
2182-1976
First Published
16 Apr 2016
Publication timeframe
2 times per year
Languages
English
Open Access

An alternative algorithm for the n–Queens puzzle

Published Online: 22 Oct 2021
Volume & Issue: Volume 8 (2021) - Issue 14 (October 2021)
Page range: 39 - 73
Journal Details
License
Format
Journal
eISSN
2182-1976
First Published
16 Apr 2016
Publication timeframe
2 times per year
Languages
English
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.

Keywords

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

Recommended articles from Trend MD

Plan your remote conference with Sciendo