N-Queens Problem..How far can we go?

Question

The N-Queens Problem:

This problem states that Given a chess board of size N by N. Find the different permutations in which N queens can be placed on the Board without any one killing each other.

My question is:
What is the maximum value of N for which a program can calculate the answer in reasonable amount of time? Or what is the largest N we have seen so far?

Here is my program in CLPFD(Prolog):

generate([],_).
generate([H|T],N) :- H in 1..N , generate(T,N).
lenlist(L,N) :- lenlist(L,0,N).
lenlist([],N,N).
lenlist([_|T],P,N) :- P1 is P+1 , lenlist(T,P1,N).

queens(N,L) :-
        generate(L,N),lenlist(L,N),
        safe(L),!,
        labeling([ffc],L).

notattack(X,Xs) :- notattack(X,Xs,1).
notattack(X,[],N).
notattack(X,[Y|Ys],N) :- X #\= Y,
                         X #\= Y - N,
                         X #\= Y + N,
                         N1 is N + 1,
                         notattack(X,Ys,N1).

safe([]).
safe([F|T]) :- notattack(F,T), safe(T).

This program works just fine, but the the time it takes keeps on increasing with N. Here is a sample execution:

?- queens(4,L).

L = [2, 4, 1, 3] ;

L = [3, 1, 4, 2] ;

No

This means you place the 4 queens at Row 2 in Column1, Row 4 in Column 2, Row 1 in 3 and Row 3 in 4.(In a 4 By 4 chess board)

Now lets see how this program performs(Time taken in calculating the first permutation):
For N=4,5.....10 Computes within a second
For N=11-30 Takes between -1-3 seconds
For N=40..50 Still calculates within a minute
At N=60 It goes out of Global stack(Search space being enormous).

This was a Homework problem which was due last month. So I think its right to discuss it now.(The original problem was just to code N-Queens)

I am also interested in seeing alternate implementations in other languages(which performs better than my implementation) or If there is room for improvement in my algorithm/program

Answer 1

a short solution presented by raymond hettinger at pycon: easy ai in python

#!/usr/bin/env python
from itertools import permutations
n = 12
cols = range(n)
for vec in permutations(cols):
 if (n == len(set(vec[i] + i for i in cols))
       == len(set(vec[i] - i for i in cols))):
  print vec

computing all permutations is not scalable, though (O(n!))

Answer 2

I dragged out an old Delphi program that counted the number of solutions for any given board size, did a quick modification to make it stop after one hit and I'm seeing an odd pattern in the data:

The first board that took over 1 second to solve was n = 20. 21 solved in 62 milliseconds, though. (Note: This is based off Now, not any high precision system.) 22 took 10 seconds, not to be repeated until 28.

I don't know how good the optimization is as this was originally a highly optimized routine from back when the rules of optimization were very different. I did do one thing very different than most implementations, though--it has no board. Rather, I'm tracking which columns and diagonals are attacked and adding one queen per row. This means 3 array lookups per cell tested and no multiplication at all. (As I said, from when the rules were very different.)

Now for some real insanity: 29 took 9 seconds. 30 took almost 6 minutes!

Answer 3

This discussion conflates three different computational problems: (1) Finding a solution to the N queens problem, (2) Listing all solutions for some fixed N, and (3) counting all of the solutions for some fixed N. The first problem looks tricky at first for a size of board such as N=8. However, as Wikipedia suggests, in some key ways it is easy when N is large. The queens on a large board don't communicate all that much. Except for memory constraints, a heuristic repair algorithm has an easier and easier job as N increases.

Listing every solution is a different matter. That can probably be done with a good dynamic programming code up to a size that is large enough that there is no point in reading the output.

The most interesting version of the question is to count the solutions. The state of the art is summarized in a fabulous reference known as The Encyclopedia of Integer Sequences. It has been computed up to N=26. I would guess that that also uses dynamic programming, but unlike the case of listing every solution, the algorithmic problem is much deeper and open to further advances.

Answer 4

Loren Pechtel said: "Now for some real insanity: 29 took 9 seconds. 30 took almost 6 minutes!"

This fascinating lack of predictability in backtrack-complexity for different board sizes was the part of this puzzle that most interested me. For years I've been building a list of the 'counts' of algorithm steps needed to find the first solution for each board size - using the simple and well known depth-first algorithm, in a recursive C++ function.

Here's a list of all those 'counts' for boards up to N=49 ... minus N=46 and N=48 which are still work-in-progress:

http://queens.cspea.co.uk/csp-q-allplaced.html

(I've got that listed in the Encyclopedia of Integer Sequences (OEIS) as A140450)

That page includes a link to a list of the matching first solutions.

(My list of First Solutions is OEIS Sequence number A141843)

I don't primarily record how much processing time each solution demands, but rather I record how many failed queen-placements were needed prior to discovery of each board's algorithmically-first solution. Of course the rate of queen placements depends on CPU performance, but given a quick test-run on a particular CPU and a particular board size, it's an easy matter to calculate how long it took to solve one of these 'found' solutions.

For example, on an Intel Pentium D 3.4GHz CPU, using a single CPU thread -

• For N=35 my program 'placed' 24 million queens per second and took just 6 minutes to find the first solution.
• For N=47 my program 'placed' 20.5 million queens per second and took 199 days.

My current 2.8GHz i7-860 is thrashing through about 28.6 million queens per second, trying to find the first solution for N=48. So far it has taken over 550 days (theoretically, if it had never been uninterrupted) to UNsuccessfully place 1,369,331,731,000,000 (and rapidly climbing) queens.

My web site doesn't (yet) show any C++ code, but I do give a link on that web page to my simple illustration of each one of the 15 algorithm steps needed to solve the N=5 board.

It's a delicious puzzle indeed!