The N queens problem - new variants of the Wirth algorithm

• Autorzy: Łajtar M.

Identyfikatory

DOI

10.2478/v10065-012-0013-3

• Języki publikacji: EN

Abstrakty

EN

The paper presents new ways of n-queens problem solving . Briefly,this is a problem on a nxn chessboard of a set n-queens, so that any two of the mare not in check. At the beginning, currently used algorithm to find solutions is discussed. Then sequentially 4 new algorithms, along with the interpretation of changes are given. The research results, including comparison, of calculation times of all algorithms together with their interpretation are discussed. Finally, conclusions are given. The results were obtained thanks to the pre-created application.Chapters except for By filtering ver. 2 were based on the previous studies carried out during the Bachelor course [1].

Słowa kluczowe

EN

N-Queens Problem; filtering algorithm; backtracking

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2013
• Tom: Vol. 13, no. 1
• Strony: 53--61
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Łajtar M.

• Institute of Computer Science, Lublin University of Technology, ul. Nadbystrzycka 36b, 20-618 Lublin, Poland

Bibliografia

• [1] Łajtar M., Implementacja i porównanie wybranych metod w problemie N-królowych, BSc Thesis supervision Grzegórski S., Lublin University of Technology (2011).
• [2] http://www.etsi.org/plugtests/grid/Document/N-QUEENS-CHALLENGE-2007-v4.pdf (01.10.2012).
• [3] Wirth N., Program Development by Refinement, Communication of the ACM (1971).
• [4] Letavec C. Ruggiero J., The n-Queens Problem, INFORMS Transcations on Education (2002).
• [5] Tesler G., n-Queens, Math 188 (2001).
• [6] http://jsomers.com/nqueen_demo/nqueens.html (01.10.2012).
• [7] Hać M., Brzuszek M, Równoległe rozwiązanie problemu N-królowych z wykorzystaniem standardu OPENMP, Scientific Bulletin of Chełm 1 (2008).
• [8] Rok S., Jun G., Polynomial Time Algorithms for the N-Queen Problem, ACM SIGART (1990).
• [9] Alfeld P., The N by N Queens Problem, Univerity of Utah (1997).
• [10] Chatham R. D., Reflections on the N + k Queens Problem, Integre Technical Publishing (2009).
• [11] http://www.academic.marist.edu/∼jzbv/algorithms/Backtracking.htm (01.10.2012).
• [12] http://proactive.inria.fr/index.php?page=nqueens25 (01.10.2012).