title: Solving N-Queens Problem... How far can we go?
body: <p>The N-Queens Problem: </p>
  
  <p>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 threatening each other.</p>
  
  <p>My question is:<br>
  <strong>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?</strong></p>
  
  <p>Here is my program in CLPFD(Prolog):</p>
  
  <pre><code>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).
  </code></pre>
  
  <p>This program works just fine, but the the time it takes keeps on increasing with N.
  Here is a sample execution:</p>
  
  <pre><code>?- queens(4,L).
  
  L = [2, 4, 1, 3] ;
  
  L = [3, 1, 4, 2] ;
  
  No
  </code></pre>
  
  <p>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)</p>
  
  <p>Now lets see how this program performs(Time taken in calculating the first permutation):<br>
  For N=4,5.....10 Computes within a second<br>
  For N=11-30 Takes between -1-3 seconds<br>
  For N=40..50 Still calculates within a minute<br>
  At N=60 It goes out of Global stack(Search space being enormous).  </p>
  
  <p>This was a past Homework problem. (The original problem was just to code N-Queens)</p>
  
  <p><strong>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</strong></p>