Solution for the n-queens problem

This is a C++ code to solve the classical n-queens problem.

It combines two codes:

For less than 17 queens it uses all_solutions.cpp and for more queens it uses n-warp.cpp

It offers these results:

Queens Tn for S0 Tn for S1 Sn in T10
15<1 sec.<1 sec.1,844,702
150<1 sec.<1 sec.1,458,572
1,500<1 sec.<1 sec.326,627
15,000<1 sec.<1 sec.39,280
150,000<1 sec.<1 sec.3,667
1,500,0001 sec.2 sec.128
15,000,0001 sec.13 sec.-

(1 thread, GNU Compiler, -O3 flag, Intel Core i7-3rd 2.1GHz, DDR3-1600)




/* author: ncomputers.org */
#include<cstdlib>
#include<iostream>
using namespace std;

template<typename type>
class all{
    typedef unsigned int seconds;

    const seconds start;
    const type nm1,n2m1;
    type *const sol,*const solnm1;
    bool *const line1,*const line2;
    type *p0,*columns,*lastcolumn;
    type x,y;
public:
    all(const type n,type quiet):
    start(time(0)),nm1(n-1),n2m1(2*n-1),
    sol(new type[n]),solnm1(sol+nm1),
    line1(new bool[n2m1]()),line2(new bool[n2m1]()+nm1),
    columns(new type[n]),lastcolumn(new type[n])
    {
        p0=columns,x=0;
        do *p0=x;
        while(p0++,++x<n);//Awaiting do...while improvement
        *lastcolumn=0,quiet=(bool)quiet,y=0;
        limit:
        if(*lastcolumn==n-y){
            if(y==0){if(quiet)cout<<endl;return;}
            remove:
            y--;
            x=*--columns,*columns=*(p0=columns+(*--lastcolumn)++),*p0=x;
            *(line1+y+x)=*(line2+y-x)=false;
            goto limit;
        }
        check:
        x=*(columns+*lastcolumn);
        if(*(line1+y+x)||*(line2+y-x)){
            ++*lastcolumn;
            goto limit;
        }
        else if(y<nm1){
            *(sol+y)=x;
            *(line1+y+x)=*(line2+y-x)=true;
            *(columns+*lastcolumn)=*columns,*columns++=x;
            *++lastcolumn=0;
            y++;
            goto check;
        }
        else{
            if(quiet){cout<<"\r"<<quiet++<<" solutions in "<<time(0)-start<<" seconds",cout.flush();}
            else {p0=sol;do cout<<*p0<<',';while(++p0<solnm1);cout<<x<<endl;}
            goto remove;
        }
    }~all(){delete[]sol,delete[]line1,delete[](line2-nm1),delete[](columns-y),delete[](lastcolumn-y);}
};

template<typename type>
class nwarp{
    typedef unsigned int seconds;

    const seconds start;
    const type nm1,n2m1,np1m4;
    type h,temp,temp1,x,x1,y,y1;
    type *const line0,*const line1;
    type *const sol,*const solnm1;
    type *const ys,*const ysnm1,*pys;
    type *const ys1,*const ys1nm1,*pys1;
    type *p0,*p1,*p2,*p3,*p4,*p5;
    type *p0y,*p1y,*p0y1,*p1y1;

    void reduce(const type y,const type x,type*const p0y,type*const p1y,type*const py){
        pys1=ys1,temp=*(p0=p0y+x)+*(p1=p1y-x);
        swap:
        y1=*ys1nm1,*ys1nm1=*pys1,*pys1=y1,x1=*(sol+y1);
        p2=(p0y1=line0+y1)+x,p3=(p1y1=line1+y1)-x,p4=p0y+x1,p5=p1y-x1;
        if((*p2+*p3+*p4+*p5+(p2==p4||p3==p5?6:4))<(temp+*(p0y1+x1)+*(p1y1-x1))){
            --*p0,--*p1,*py=x1,*(sol+y1)=x;
            //The "--*p0,--*p1;" operations must happen before the "h" update.
            h-=-(temp1=++*p2+ ++*p3)-++*p4-++*p5+temp+(*(p0y1+x1))--+(*(p1y1-x1))--;
            if(temp1>2)reduce(y1,x,p0y1,p1y1,sol+y1);
            x1=*py;if(*(p0y+x1)+*(p1y-x1)>2)reduce(y,x1,p0y,p1y,py);
        }
        else if(pys1<ys1nm1){pys1++;goto swap;}//Awaiting do...while improvement
    }
public:
    nwarp(const type n,type quiet):
    start(time(0)),nm1(n-1),n2m1(n*2-1),np1m4(4*n+4),
    line0(new type[n2m1]()),line1(new type[n2m1]()+nm1),
    sol(new type[n]),solnm1(sol+nm1),
    ys(new type[n]),ysnm1(ys+nm1),
    ys1(new type[n]),ys1nm1(ys1+nm1)
    {
        y1=nm1;do *(sol+y1)=*(ys+y1)=*(ys1+y1)=y1;while(--y1);
        h=0,p0=sol,srand(start);
        seed:
        x=*(p1=p0+rand()%(n-y1)),*p1=*p0,*p0=x;
        h+=(*(line0+x+y1))++ +(*(line1-x+y1))++;
        if(y1<nm1){p0++,y1++;goto seed;}//Awaiting do...while improvement
        cout<<"started in "<<time(0)-start<<" seconds"<<endl;
        quiet=(bool)quiet,p0y1=line0+y1,p1y1=line1+y1;
        start:
        pys=ys;
        if(h){
            do{
                y=*ysnm1,*ysnm1=*pys,*pys=y,x=*(sol+y);
                if(*(line0+y+x)+*(line1+y-x)>2){reduce(y,x,line0+y,line1+y,sol+y);if(!h)goto solved;}
            }while(++pys<ysnm1);
        }
        else{
            solved:
            if(quiet){cout<<"\r"<<quiet++<<" solutions in "<<time(0)-start<<" seconds",cout.flush();}
            else{p0=sol;do cout<<*p0<<',';while(++p0<solnm1);cout<<*p0<<endl;}//Awaiting do..while improvement
        }
        //For non-prime numbers:
        //p1=sol+y1,temp=y,temp1=temp+n;
        p1=sol+y1,temp=rand()%n,temp1=temp+n;
        warp:
        p0=sol+(y=temp%n),p0y=line0+y,p1y=line1+y;
        x=*p0,*p0=x1=*p1,*p1=x;
        h-=-++*(p0y1+x)-++*(p1y1-x)-++*(p0y+x1)-++*(p1y-x1)+--*(p0y+x)+--*(p1y-x)+--*(p0y1+x1)+--*(p1y1-x1);
        if(temp<temp1){temp++;goto warp;}//Awaiting do...while improvement
        else{h-=np1m4;goto start;}
    }~nwarp(){delete[]line0,delete[](line1-nm1),delete[]sol,delete[]ys,delete[]ys1;}
};

int main(){
    typedef unsigned int type;
    type input0=-1,input1=input0/2;
    cout<<"queens (4-"<<input1<<")? ",cin>>input0;
    if(input0<4||input0>input1)return 1;
    cout<<"quiet (1/0)? ",cin>>input1;
    if(input0<17)delete new all<type>(input0,input1);
    else delete new nwarp<type>(input0,input1);
    return 0;
};