递归回溯法.cpp

算法设计分析的一些例子程序....凑字数..凑字数

#include <iostream>
#include <iomanip>
#include <cmath>


using namespace std;

class Queen
{
public:
	Queen(int n)
	{
		size=n;
		x=new int[size+1];
		sum=0;
	}

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

	void backTrack(int row)
	{
		int i,j;
		if (row>size) 
		{
			sum++;
			cout<<"method:"<<endl;
			for (i=1;i<=size;i++)
			{
				for (j=1;j<=size;j++)
				{
					if (j==x[i]) cout<<setw(2)<<"1";
					else
						cout<<setw(2)<<"0";
				}
				cout<<endl;
			}
			return;
		}

		for (i=1;i<=size;i++)
		{
			x[row]=i;
			if (place(row)) backTrack(row+1);
		}
	}

	int size;
	int *x;
	int sum;
};

int main()
{
	Queen queen(8);
	queen.backTrack(1);
	cout<<"total:";
	cout<<queen.sum;
	cout<<endl;
	return 0;
}