On generating solutions to the N-queens problem using 2-circulants

• Main Authors: Montemayor, Margarita I., Ogilvie, Jane Denise C.
• Format: text
• Language: English
• Published: Animo Repository 1997
• Subjects: Programming (Mathematics); Chess problems; Queen (Chess); Mathematical recreations
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/16449
• Institution: De La Salle University

This thesis presents the different constructions used in generating the solutions to the N-Queens problem, where N > 4. The N-Queens problem is about how one can place N queens on an N x N chessboard so that no two queens can attack each other. The concepts used in this study are the circulant matrices, specifically, 2-circulant matrices, latin squares and latin rectangles. Four different constructions were used in this study. Constructions A and B were used for even values of N while Constructions C1 and C2 were used for odd values of N. For each construction, a set of solutions could be obtained by constructing the 2-circulant matrices. These matrices were obtained by following the steps given in each construction. The theorems and lemmas which were proven verifies the validity of each step. All the theorems and lemmas found in this study were presented by Cengiz Erbas and Murat M. Tanik in their article Generating Solutions to the N-Queens Problem Using 2-circulants . The researchers have proven these theorems and lemmas in detail, using number theoretic concepts and concepts in 2-circulant matrices. Aside from this, a computer program which generates the solutions to the N-Queens problem was also developed. A user's manual was also provided to give the procedures in using the computer program.