**Booth Id:**

MATH004

**Category:**

Mathematics

**Year:**

2018

**Finalist Names:**

Mikhailovskii, Dmitrii (School: School 564)

**Abstract:**

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 Won:**

American Mathematical Society: Certificate of Honorable Mention