Tuesday, 24 July 2012

UVa 750 - 8 Queens Chess Problem Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define LL long long
#define MX 100000
#define MOD 1000000007


vector<string>result;
int tmp[10];
string s;
int lft[20],rgt[20],row[10],max_sol;    //bottom left diagonal and bottom right diagonal, it can be -8 to +8

void solutions(int n) //all solutions return with string vector result
{
    if(n==8)
    {
        s="";
        for(int j=0;j<8;j++)
        {
            s+=  (tmp[j]+'0');
        }
        result.PB(s);
        return;
    }

    for(int i=1;i<=8;i++)
        if(!row[i] && !lft[n+i] && !rgt[n-i+8])//if not visited
        {
            row[i]=lft[n+i]=rgt[n-i+8]=1;//set visit
            tmp[n]=i;
            solutions(n+1);
            row[i]=lft[n+i]=rgt[n-i+8]=0;
        }
}

int main()
{
    solutions(0);
    //cout<<result[0]<<endl;
    int len=result.size();
    int t,x,y;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>x>>y;
        if(i!=1)
        cout<<endl;
        int kk=1;
        cout << "SOLN       COLUMN" << endl;
        cout << " #      1 2 3 4 5 6 7 8" << endl<<endl;
        for(int j=0;j<len;j++)
            if(result[j][y-1]== x+'0')
            {
                cout<<setw(2)<<kk++<<"     ";
                for(int k=0;k<8;k++)
                    cout<<" "<<result[j][k];
                cout<<endl;
            }
    }

return 0;
}

No comments:

Post a Comment