An incremental approach to the n-queen problem with polynomial time
Bouneb Zine El Abidine · Journal of King Saud University - Computer and Information Sciences · 2023
This paper shows that computing the n-queen solution of the chessboard n-by-n from the chessboard (n-1)-by-(n-1) can be used in polynomial time O(n2) using symbolic computation on the complement of the n queen Graph. Nevertheless, continuing further in an incremental approach, besides the n-1 solution, which represents the maximum cliques of size n-1 on the complement of the graph corresponding to the chessboard n-1, we need the maximum cliques of size n-2,and below. By doing so, we need to eliminate the anti-chain problem, which increases the algorithm’s complexity.