迭代回溯法.cpp

来自「算法设计分析的一些例子程序....凑字数..凑字数」· C++ 代码 · 共 68 行

#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=1;
	   x[1]=0;

	   while (row>0)
	   {
		   x[row]++;

		   while (x[row]<=size&&!place(row)) x[row]++;

		   if (x[row]<=size)
			   if (row==size) 
			   {
				   sum++;
			   }
			   else
			   {
				   row++;
				   x[row]=0;
			   }
			   else
				   row--;
	   }

	}

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

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