Heuristic-queen n-Queens Problem has complexity O(n^2) The solution for n = 1000 can be found in about 2-10 seconds The solution for n = 2000 can be found in about 20-60 seconds