New Explicit Solution to the N-Queens Problem and the Millennium Problem

Overview

The N-Queens Problem is the problem of placing N chess queens on a NxN chessboard so that no two queens attack each other. Calculation of the number of different solutions is related to the problem of completion the NxN chessboard with m<N queens to complete board with N queens. All known algorithms stop working for N>=1000. In August 2017 a group of Scottish mathematicians proved that N-Queens Completion is NP-complete and suggested one million dollars for a polynomial-time algorithm or just more efficient algorithm than existing algorithms which solve this problem. The main results of my work are: 1) Composition of arrangements A and B is a queens arrangement obtained by insertion of B into queens positions of A. I find the criterion of being a composition of solutions a solution. Sufficiency was proved 100 years ago, and I prove the most difficult part - the necessity with new consequences. 2) Queen function with width k is a special map which is defined on partition of a segment [1, N] by the k segments as an almost usual linear map. I prove that for any N>3 there exists a solution which can be represented as Queen function with width fewer or equal to 3. And this estimate of width cannot be reduced. 3) Based on obtained results I formulate a hypothesis: if for N-1 and N there are no solutions which are compositions of smaller boards then there exists a set of solutions which generate all solutions by symmetry which can be represented as a Queen function with width fewer or equal to 3. If this hypothesis is true then for such N I can construct a polynomial-time algorithm which solves N-Queens Completion. This hypothesis raises a new problem: is the number of such N is infinite? In particular, is the number of primes of the form 2^k3^l-1 is infinite?

Awards (1)

• American Mathematical Society: Certificate of Honorable Mention

Competition history

• ISEF 2018 Mathematics · Entry MATH004

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.