[소급법] n황후 문제

1841 단어
하나.차례로 거슬러 올라가다
#include <iostream>
using namespace std;

#define N 8
int sum=0;
int *x=new int[N+1];

bool place(int k)
{
	int i;
	for(i=1; i<k; i++)
	{
		if(x[i]==x[k] || abs(i-k)==abs(x[i]-x[k]))
			return false;
	}
	return true;
}

void backtrack(int t)// 
{
	int i=0;
	if(t>N)
	{
		for(i=1; i<=N; i++)
			cout<<x[i]<<" ";
		cout<<endl;
		sum++;
	}
	else
	{
		for(i=1; i<=N; i++)
		{
			x[t]=i;
			if(place(t))
				backtrack(t+1);
		}
	}
}
void main()
{

	backtrack(1);
	cout<<sum<<endl;
}	

둘.반복해서 거슬러 올라가다
#include <iostream>
using namespace std;

#define N 8
int sum=0;
int *x=new int[N+1];

bool place(int k)
{
	int i;
	for(i=1; i<k; i++)
	{
		if(x[i]==x[k] || abs(i-k)==abs(x[i]-x[k]))
			return false;
	}
	return true;
}

void backtrack2()// 
{
	int i;
	x[1]=0;
	int k=1;
	while(k>0)
	{
		x[k]+=1;// 1 
		while((x[k]<=N) && !place(k))// 
			x[k]+=1;// , 

		if(x[k]<=N)// 
		{
			if(k==N)// , 
			{
				for(i=1; i<=N; i++)
					cout<<x[i]<<" ";
				cout<<endl;
				sum++;

			}
			else// , 
			{
				k++;
				x[k]=0;
			}
		}
		else// 
		{
			k--;
		}

	}
}

void main()
{
	backtrack2();
	cout<<sum<<endl;
	
}


좋은 웹페이지 즐겨찾기