Amanda Borg: Backtracking och n-queens: hur radordning påverkar sökningens effektivitet

Abstract: The n-queens problem is well known within the field of combinatorics and has been studied since the mid 19th century. The purpose of the problem is to place n queens on a chessboard of size n x n in such a way that no queens attack each other. Since its beginning, the problem has evolved to also include a three-dimensional point of view. Several real-world applications have been found for the n-queens problem. This essay will cover the problem's historical background and development, mathematical structure, group action in relation to n-queens, and the implication of backtracking to find solutions.

The main focus of this essay is to analyze how the effectiveness of the backtracking algorithm is affected by the order in which the rows of the board are searched. In order to examine this, the 7 x 7 board was searched according to different permutations which represent row orders. To further look at backtracking and its effectiveness, a Python program is used to calculate the maximum number of backtracking steps for n = 4, 5, 6,..., 9. The permutations that resulted in the largest amount of steps are then analyzed and any pattern or structure is noted.

The results of the study show that it is possible to create a permutation from a pre-existing solution and in doing so in a structured manner, one receives a permutation which will generate a new solution with zero backtracking steps needed. By doing this, one will also generate the entire orbit of the original solution. Usage of the Python program showed that there existed both a pattern and structure among the permutations that required the greatest number of backtracking steps. It showed that a permutation had exactly the same amount of backtracking steps as its complement.The results also showed that many of the permutations that were among the least effective ones, began by placing a queen in a corner. By connecting the results to group action the essay demonstrates how group theory can be used to effectively search for solutions to the n-queens problem.

I would like to express my gratitude towards my supervisor Per Alexandersson who has provided me with valuable input during the course of the work.