nqueens

nqueens.cpp

#include<iostream>
#include<cstring>
using namespace std;
int n=0,sum=0;
int a[20][20];
int check(int curx,int cury)
{
	int i;
	if(curx>=n || curx<0 || cury>=n || cury<0)
		return 0;
	for(i=0;i<n;i++)
		if ((a[curx][i]==1 && i != cury) || (a[i][cury]==1 && i != curx))
			return 0;
	while(curx < n && cury < n)
	{
		curx++;
		cury++;
		if(a[curx][cury]==1)
			return 0;
	}
	while(curx >= 0 && cury >= 0)
	{
		curx--;
		cury--;
		if(a[curx][cury]==1)
			return 0;
	}
	return 1;
}
void dfs(int curx,int cury)
{
	if (curx == n)
	{
		sum++;
		return;
	}
	else
	{
		if(check(curx,cury)==0)
			return;
		else
		{
			a[curx][cury]=1;
			dfs(curx+1,cury);
			a[curx][cury]=0;
			dfs(curx+1,cury+1);
			a[curx][cury]=0;
		}
	}
}
int main()
{
	int i,j;
	cin >>n;
	for(i=0;i<=n-1;i++)
		for(j=0;j<=n-1;j++)
			a[i][j]=0;
	dfs(0,0);
	cout <<sum<<endl;
	return 0;
}