/sci/ - Science & Math

https://arxiv.org/pdf/1805.07329
>New explicit solution to the N-Queens Problem and its relation to the Millennium Problem
>Dmitrii Mikhailovskii
>(Submitted on 18 May 2018)
>Using modular arithmetic of the ring [math] \mathbb{Z}_{n+1} [/math] we obtain a new short solution to the problem of existence of at least one solution to the N-Queens problem on an N×N chessboard. It was proved, that these solutions can be represented as the Queen function with the width fewer or equal to 3. It is shown, that this estimate could not be reduced. A necessary and sufficient condition of being a composition of solutions a solution is found. Based on the obtained results we formulate a conjecture about the width of the representation of arbitrary solution. If this conjecture is valid, it entails solvability of the N-Queens completion in polynomial time. The connection between the N-Queens completion and the Millennium P vs NP Problem is found by the group of mathematicians from Scotland in August 2017.