New explicit solution to the N-Queens Problem and its relation to the Millennium Problem

arXiv1805.07329MaRDI QIDQ6301792FDOQ6301792

Authors: Dmitrii Mikhailovskii 

Publication date: 18 May 2018

Abstract: Using modular arithmetic of the ring $mathbb{Z}_{n+1}$ we obtain a new short solution to the problem of existence of at least one solution to the $N$-Queens problem on an $NimesN$ 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.

Has companion code repository: https://github.com/TheInventorMan/N-Queens-GPU

This page was built for publication: New explicit solution to the N-Queens Problem and its relation to the Millennium Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301792)