main.cpp

8皇后问题的c++解决方案

#include <list>
#include <algorithm>
#include <functional>
#include "eight.h"
using namespace std;
int k=0;
bool findlist(list<int> & li,int ai)
{
	list<int>::iterator i=find(li.begin(),li.end(),ai);
	if(*i==ai)
		return true;
	else 
		return false;
}
void change(eight & start,eight & aim,list<int> & li)
{
	start.print();
	li.insert(li.begin(),start.toint());

	point pos[4];	
	pos[0].cal=start.blank.cal-1;
	pos[0].row=start.blank.row;
	pos[1].row=start.blank.row-1;
	pos[1].cal=start.blank.cal;
	pos[2].cal=start.blank.cal+1;
	pos[2].row=start.blank.row;	
	pos[3].row=start.blank.row+1;
	pos[3].cal=start.blank.cal;
	

	for(int i=0;i<=3;i++)
	{
		if(pos[i].cal==start.pre.cal&&pos[i].row==start.pre.row)
			continue;
		if(pos[i].check())
		{
			eight* a=new eight(start);
			start.move(pos[i],start.blank,*a);
			if(*a==aim)
			{
				int i;
				cout<<"-----------------------------OK-----------------------------------------";
				cin>>i;
			}
			if(findlist(li,a->toint()))	
			{
				delete a;
				k--;
				return;
			}
			k++;
			if(k>5)
			{
				k--;
				return;
			}
			change(*a,aim,li);
			k--;
			delete a;
		}
	}
}
int main()
{
	list<int> lis;
	eight aim;
	aim.vec[0][0]=1;
	aim.vec[0][1]=2;
	aim.vec[0][2]=3;
	aim.vec[1][0]=8;
	aim.vec[1][1]=0;
	aim.vec[1][2]=4;
	aim.vec[2][0]=7;
	aim.vec[2][1]=6;
	aim.vec[2][2]=5;	
	eight in;
	//in.input();
	in.vec[0][0]=2;
	in.vec[0][1]=8;
	in.vec[0][2]=3;
	in.vec[1][0]=1;
	in.vec[1][1]=6;
	in.vec[1][2]=4;
	in.vec[2][0]=7;
	in.vec[2][1]=0;
	in.vec[2][2]=5;
	in.blank.row=2;
	in.blank.cal=1;

	change(in,aim,lis);
	int i;
	cin>>i;
	return 1;
}