Nichts gefunden?

Teilen Sie uns mit, welche Inhalte Sie auf unseren Seiten vermissen.

The n-queens completion problem

A well-known classic chess problem is the so-called $n$-queens problem, where $n$ queens have to be placed on a $n\times n$ chessboard such that no two queens attack each other according to the classical chess rules. Such a placement of queens is called  an $n$-queens configuration. This problem motivated countless other questions. This thesis focuses on the $n$-queens completion problem, which asks whether a set of non-attacking queens on the $n\times n$ chessboard can be extended to an $n$-queens configuration. More precisely, what is the maximum integer qc$(n)$, such that any arrangement of at most qc$(n)$ non-attacking queens is always completable? Progress on this question was obtained by Glock, Correia, and Sudakov in 2022 using graph theoretic arguments. In this work, I was able to improve their lower bound of qc$(n)\ge \frac{n}{60}$ to qc$(n)\ge \frac{n}{52}$.

Back to list

Year: 2023

Author : Danielle Eitelmann

Prof. Dr. Felix Joos