Solving N Queens problem with polynomial computational complexity

pdf version Made public May 15th 2020.

The problem.

  1. The problem is well known and was mentioned first time in literature in 1848. More about history of that problem can be found in Wikipedia
  2. Originally the problem is stated as following: place N queens on the chessboard size N (N x N square) in such a way that no single queen beat any other queen by the rules of chess.
  3. We can formulate it following way: for some arbitrary N find all existing solutions.
  4. Currently the only known algorithms are brute force with computational complexity O(N!).
  5. Here we are trying to describe an algorithm to do that with polynomial complexity.

Some considerations.

  1. For any existing solutions there will be a queen in last (Nth) column. It follows from the notion that one and only one queen will be in the each column in order for them not to beat each other.
  2. Let look at solution shown on the following diagram (queen in the Nth column and Kth row):
A A A A
A A A A
Q
B B B B
B B B B
  1. In the area A there are K-1 queens. None of these queens beat each other.
  2. In the area B there are N-K queens. None of these queens beat each other.
  3. When K == 1 only area B exists. Position of queens in area B will represent solution for N-1. Not all N-1 solutions can be placed into area B, but only those without a single queen on the reverse main diagonal.
  4. When K == N only area A exists. It represents a solution for N-1. Not all N-1 solutions can be placed into area A, but only those without a single queen on the main diagonal.
  5. It is obvious that for any solution with K <= N/2 exists a symmetrical solution with N-K. So, for any practical purposes we are concerned only with K<=N/2.
  6. For queens in areas A and B - if we remove last column and row K and then start to shift rows from A into B as if they are on the cylinder we will get following position
B B B B
B B B B
A A A A
A A A A

This position will represent a solution for N-1, because: - there will be one and only one queen in each row - there will be one and only one queen in each column - I do not know why but it still works for each diagonal for all solutions known to me. It can be somehow seen by turning the board into cylinder - it looks if chessboard will be cylindrical (not true for toroidal) solutions will still hold. We need to look how diagonals change when board becomes cylindrical.

  1. The above consideration means that if we remove row K and column N then new united in the described way areas A and B on the new board N-1 will represent solution of the “N-1 queens”.

The algorithm.

To compute all possible solutions for N we will take all solutions of N-1 and try to insert a queen in the way described above for each shifting rowws from area B to area A K times for K from 0 to N/2. For each position we will check that queen from last column would not beat the rest of the queens. For each solution found by the described way we will produce all symmetrical solutions and check for uniqueness.

Solutions for N-1 are computed the same way by using solutions for N-2.

Solutions for N == 4 are computed using brute force.

Proposed algorithm suppose to produce all solutions with a queen in the last columns => so, if all solutions for N-1 problem will be used the algorithm should produce all the solutions for N.

Computational complexity of proposed algorithm.

  1. For each N-1 solution we will be checking N/2 positions of the queen in last column.
  2. We also need to check if the queen from the last column beats queens from both areas A and B, amount of checks ~ 2*(N-1), complexity O(N)
  3. There are N/2 positions described above => complexity of checking one N-1 solution is O(N2)
  4. Lets assume that amount of solutions for N-1 is f(N-1).
  5. Then complexity of the step from N-1 to N will be O(N2*f(N-1))
  6. Checking that given solution is unique will be proportional to amount of solutions, so it is O(f(N)), it is less then O(N2*f(N)) and can be disregarded in computing complexity.
  7. There will be N-4 such steps, so, complexity of whole computation is no more then O(N3*f(N)) - it can be polynomial - if f(N) is polynomial- instead being exponential for brute force algorithms.
  8. The problem is to estimate f(N) - and it seems that it might be exponential - see attached graph for first 16: the graph.
  9. From another point of view - if we can prove that number of solutions grows exponentially with N - we will prove that the problem cannot be solved other then in exponential time, what is a result of its own.

Unproven assumptions

  1. The described way of removing the queen from the last column will always produce a working solution for N-1 (considerations # 8 and 9).
  2. Amount of solutions is polynomial - it is a pretty strong assumption and it seems to be a wrong one. May be we can come up with better estimate by considering the algorithm itself?

References

Originally Author was inspired by the lenta.ru article that $1M prize was proposed for solving this problem. It leads to St.Andreas University article where they explain that the promise of prize is a misunderstanding and that originally they meant that solving N Queens problem will help to solve one of the Millennium Problems. Clay Mathematical Institute proposed $1M for solving any one of the Millennium Problems. So, it seems no prize for the Author …

The program

Will be added soon.

Please email Author with questions.