result.cpp

用分支界限法实现的n后问题 vc++ 语言效率很好

// result.cpp : implementation file
//

#include "stdafx.h"
#include "nqueue.h"
#include "result.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// result

////IMPLEMENT_DYNCREATE(result, CCmdTarget)

result::result()
{
	canarrange=false;
}
/*
result::~result()
{
}
*/

//BEGIN_MESSAGE_MAP(result, CCmdTarget)
	//{{AFX_MSG_MAP(result)
		// NOTE - the ClassWizard will add and remove mapping macros here.
	//}}AFX_MSG_MAP
//END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// result message handlers

void result::GET()
{
int y;
static int t=0;
int father=0;//记录出 队的数量,也 是当前的父结点
for(int i=0;i<n;i++)
{
	mid *mid1=new mid(0,i,-1);
	midlist.AddTail(mid1);
	//x[t]=new mid(0,i,-1);
	x[t].row=0;
	x[t].column=i;
	x[t].prior=-1;
    t++;
	while(!midlist.IsEmpty())
	{
	mid *mid2;
	mid2=midlist.GetHead();
	//delete midlist.GetHead();
	midlist.RemoveHead();
	
	for(int j=0;j<n;j++)
	{    y=mid2->row+1;//当前探测的行号
		if (y<n-1)
		{
			if (place(y,j,father))
			{ 
				//x[++t]=new mid(mid2->row+1,j,father);
				x[t].row=y;
				x[t].column=j;
				x[t].prior=father;
                t++; 
				mid *mid3=new mid(y,j,father);
			    midlist.AddTail(mid3);
			}
		}
         else//最后一行的安排
		 {
			 if (place(y,j,father))///已经找到
			 {
				 //x[++t]=new mid(n-1,j,father);
				 x[t].column=j;
				 x[t].row=y;
				 x[t].prior=father;
				 //t++;
				 for(int l=n-1;l>=0;l--)
				 {
			     save[l]=x[t].column;
				 t=x[t].prior;
				 }
				 canarrange=true;//可以完成安排
                 return;
			 }
		 }

	}
	father++;
    //对第一行的第i个位置探索失败
	}
	midlist.RemoveAll();
	t=0;///从下下[0]重新开此
	father=0;
}
}
/*
bool result::place(int row, int column, int father)
{
int i;
father1=father
guard=new mid();
while(father!=-1)
{
	guard=x[father1];
	if(absnum(row-guard.row)==absnum(column-guard.column) || column=guard.column )
		return false;
	father1=guard.fathar;
}
return true;
}

	

}
*/
//DEL int result::absnum(int x)
//DEL {
//DEL if (x>0 ) 
//DEL return x;
//DEL else return -x;
//DEL }

bool result::place(int row, int column, int father)
{
int father1=father;
mid *guard;
while(father1!=-1)
{
	guard=new mid(x[father1].row,x[father1].column,x[father1].prior);//father 与 prior意义一样
	if((absint(row-guard->row)==absint(column-guard->column)) ||( column==guard->column ))
		return false;
	father1=guard->prior;              
}
return true;
}

//DEL int result::absint(int a)
//DEL {
//DEL if (a>0)
//DEL return x;
//DEL else
//DEL return (-x);
//DEL }

int result::absint(int a)
{
if(a>0)
return a;
else
return(-a);
}
//DEL void result::operator = (mid a)
//DEL {
//DEL 	
//DEL }

void result::setn(int x)
{
  n=x;
}