chessview.cpp

人工智能的经典八皇后问题,这个算法是a*算法.利用这个算法可以解决八数码,八皇后问题等

// ChessView.cpp : implementation of the CChessView class
//

#include "stdafx.h"
#include "Chess.h"

#include "ChessDoc.h"
#include "ChessView.h"
#include "DataType.h"
#include "conio.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CChessView

IMPLEMENT_DYNCREATE(CChessView, CScrollView)

BEGIN_MESSAGE_MAP(CChessView, CScrollView)
	//{{AFX_MSG_MAP(CChessView)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CScrollView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CScrollView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CScrollView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CChessView construction/destruction

CChessView::CChessView()
{
	// TODO: add construction code here

}

CChessView::~CChessView()
{
}

BOOL CChessView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CScrollView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CChessView drawing

void CChessView::OnDraw(CDC* pDC)
{
	CChessDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	CPen *pNewPen,*pOldPen;
	CFont *pOldFont,*pNewFont;

	//AfxMessageBox("aaa");

	GetClientRect(&m_Rect);
	CSize TextSize;
	
	
	

	
	CBrush *pBrush;
	pBrush=new CBrush;
	pBrush->CreateSolidBrush(RGB(255,255,255));

	//pDC->SelectStockObject(WHITE_BRUSH);
	//pDC->Rectangle(&m_Rect);
	pDC->FillRect(&m_Rect,pBrush);

	delete pBrush;

	pNewPen=new CPen;
	pNewPen->CreatePen(PS_SOLID,1,RGB(255,0,0));
	pOldPen=pDC->SelectObject(pNewPen);
	
	pNewFont=new  CFont;
	pNewFont->CreateFont(12,0,0,0,
					400,FALSE,FALSE,0,
					ANSI_CHARSET,OUT_DEFAULT_PRECIS,
					CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,
					DEFAULT_PITCH & FF_SWISS,
					"黑体");
	pOldFont=pDC->SelectObject(pNewFont);

	TEXTMETRIC textMetric;
	pDC->GetTextMetrics(&textMetric);

	
	int GridWidth=textMetric.tmHeight+2;

	/*for(i=0;i<pDoc->m_nResult;i++)
	{
		for(j=0;j<pDoc->m_Result[i].depth;j++)
		{	
			sprintf(buf,"%c",pDoc->m_Result[i].moves[j]);
			pDC->TextOut(j*10,i*20,buf);
			sprintf(buf,"%d",pDoc->m_Result[i].rules[j]);
			pDC->TextOut(j*10,i*20+20,buf);
		}
	}
		
	*/
	/*switch(m_nType)
	{
	case 0:
		break;
	case 1:
		//SearchDFS(CPoint((m_Rect.right/2,m_Rect.bottom/2)),GridWidth,GridWidth,GridWidth,pDC);

	default:
		break;
	}*/
	
	ShowResult(CPoint(m_Rect.right/2,10),GridWidth,GridWidth,GridWidth,pDC);
	
	CSize srcSize;
	srcSize.cx=m_Rect.right-m_Rect.left;
	srcSize.cy=m_Rect.bottom-m_Rect.top;
	SetScrollSizes(MM_TEXT,srcSize);

	pDC->SelectObject(pOldFont);
	pNewFont->DeleteObject();

	pDC->SelectObject(pOldPen);
	pNewPen->DeleteObject();

}

void CChessView::OnInitialUpdate()
{
	CScrollView::OnInitialUpdate();

	CSize sizeTotal;
	// TODO: calculate the total size of this view
	sizeTotal.cx = sizeTotal.cy = 100;
	SetScrollSizes(MM_TEXT, sizeTotal);
}

/////////////////////////////////////////////////////////////////////////////
// CChessView printing

BOOL CChessView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CChessView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CChessView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CChessView diagnostics

#ifdef _DEBUG
void CChessView::AssertValid() const
{
	CScrollView::AssertValid();
}

void CChessView::Dump(CDumpContext& dc) const
{
	CScrollView::Dump(dc);
}

CChessDoc* CChessView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CChessDoc)));
	return (CChessDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CChessView message handlers

void CChessView::SearchDFS(CPoint &p0,int width,int v,int h,CDC* pDC)
{
	int p1,p2,p3,exp;
	p1=Start2GoalS(m_strStart,m_strEnd,m_N,m_NUM);
	p2=Start2GoalL(m_strStart,m_strEnd,m_N,m_NUM);
	   
	p3=Start2GoalZ(m_strStart,m_strEnd,m_NUM);
	exp=p1+p2+2*p3;
	if((exp+p2)%2!=0) exp--;
	for(;_kbhit()==0 && exp<100;exp+=2)
	{	
		
		m_nResult=0;
		m_nDepth=exp;

		CPen  *pNewPen,*pOldPen;
		pNewPen=new CPen;
		pNewPen->CreatePen(PS_SOLID,1,RGB(255,255,255));
		pOldPen=pDC->SelectObject(pNewPen);

		GetClientRect(&m_Rect);
		pDC->SelectStockObject(WHITE_BRUSH);
		pDC->Rectangle(&m_Rect);
		
		pNewPen->DeleteObject();
		pDC->SelectObject(pOldPen);

		if(DFS(m_strStart,m_strEnd,p0,width,v,h,pDC)==0)
		{
			CSize scrSize;
			scrSize.cx=m_Rect.right-m_Rect.left;
			scrSize.cy=m_Rect.bottom-m_Rect.top;
			SetScrollSizes(MM_TEXT,scrSize);
			break;
		}

	}
}

int CChessView::DFS(unsigned char *start, unsigned char *goal,CPoint &p0,int width,int v,int h,CDC* pDC)
{
	
	CPathNode *info,*p,*OpenFirst;
	CPen *pNewPen,*pOldPen;
	pNewPen=new CPen;
	pNewPen->CreatePen(PS_SOLID,1,RGB(0,0,255));

	OpenFirst=NULL;
	unsigned char nextspace;
	int m,n,same,flag=-1;
	//初始化第一个结点
	info=new CPathNode(m_N,p0,width);
	memcpy(info->state,start,m_NUM);
	info->space=strcspn((char*)start,"0");
	info->move='0';
	info->depth=info->rule=0;
	
	info->next=NULL;
	OpenFirst=info;

	info->DrawNode(pDC);

	m_nGenerate=0;
	m_nSplit=1;
	m_nResult=0;
	flag=1;
	while(_kbhit()==0)
	{
		CPoint tempPoint(OpenFirst->P0.x+(m_N*width+h)*(2*OpenFirst->rule-3)/2,OpenFirst->P0.y+m_N*width+v);

		info=new CPathNode(m_N,tempPoint,width);

		if((info->P0.x-width)<m_Rect.left) m_Rect.left=info->P0.x-width;
		if((info->P0.x+width)>m_Rect.left) m_Rect.right=info->P0.x+width+50;
		if(info->P1.y>m_Rect.bottom) m_Rect.bottom=info->P1.y+50;

		memcpy(info->state,OpenFirst->state,m_NUM);
		info->space=OpenFirst->space;
		info->depth=OpenFirst->depth;
		info->rule=OpenFirst->rule;
		OpenFirst->rule++;//下一规则
		
		if(OpenFirst->rule>=(UINT)4)
			m_nSplit++;

		if(info->rule>=(UINT)4 || info->depth>m_nDepth)
		{
			delete info;
			//////////////////////
			if(OpenFirst)
			{
				OpenFirst=(p=OpenFirst)->next;
				delete p;
			}
			if(OpenFirst==NULL) 
				return flag;
			continue;
		}
		
	
		nextspace=info->space+(2*info->rule-3)/2*m_N+
			1/(2*info->rule-3);
		if(nextspace<0 || nextspace>m_NUM-1 ||
			(info->space%m_N==0 && info->rule==1) ||
			(info->space%m_N==m_N-1 && info->rule==2))
		{//空格出界
			delete info;
			continue;
		}

		info->move=info->state[info->space]=info->state[nextspace];

		info->state[nextspace]='0';//填充当前结点
		m=Start2GoalS(info->state,goal,m_N,m_NUM);
		n=m_nDepth-info->depth;

		for(p=OpenFirst,same=0;p;p=p->next)
		{
			if(m>n|| memcmp(p->state,info->state,m_NUM)==0)
			{
				same=-1;
				delete info;
				break;
			}
		}
		if(same==0)
		{
			info->space=nextspace;
			info->depth++;
			info->rule=0;
			
			pDC->MoveTo(OpenFirst->P1);
			pDC->LineTo(info->P1.x,info->P0.y);

			//将该结点加入链表
			if(!OpenFirst)
			{
				info->next=NULL;
				OpenFirst=info;
			}
			else
			{
				info->next=OpenFirst;
				OpenFirst=info;
			}
			m_nGenerate++;
			
			info->DrawNode(pDC);

		//	pDC->MoveTo(OpenFirst->P1);
		//	pDC->LineTo(info->P1.x,info->P0.y);


			if(memcmp(info->state,goal,m_NUM)==0)
			{//若当前结点和目标状态相同
				m_nResult=(m_nDepth>info->depth)? 1: m_nResult+1;
				if(m_nResult>MAXRESULT)
				{
					AfxMessageBox("结果数目超出缓存空间");
					flag=-2;
					break;
				}
				m_nDepth=info->depth;
				CResult *res=&m_Result[m_nResult-1];
				if(res->depth!=0)
				{
					delete[] res->moves;
					delete[] res->rules;
				}
				res->moves=new unsigned char[OpenFirst->depth];
				res->rules=new unsigned char[OpenFirst->depth];

			
				res->generate=m_nGenerate;
				res->split=m_nSplit;
				res->depth=OpenFirst->depth;
				for(m=info->depth-1,p=OpenFirst;p&& p->move!='0';p=p->next)
				{
					res->moves[m]= p->move;
					res->rules[m]=p->rule;
					m--;
				}

				flag=0;
			}
		}
	}
	pNewPen->DeleteObject();
}



int CChessView::Start2GoalS(unsigned char *start, unsigned char *goal,int N,int NUM)
{//求各数码当前位置到目标位置的距离之和
	int i,j,s;
	for(s=0,i=0;i<NUM;i++)
	{
		if(goal[i]!='0')
		{
			for(j=0;j<NUM && start[j]!=goal[i];j++);
			s+=abs(i/N-j/N)+abs(i%N-j%N);
		}
	}
	return s;

}

//求当前状态到目标状态的换位数
int CChessView::Start2GoalL(unsigned char *start, unsigned char *goal,int N,int NUM)
{
	int i,j,l,m,n,init,data;
	unsigned char temp[16];
	for(i=0;i<NUM;i++) temp[i]=i;
	for(i=0,j=0,l=0;i<NUM && j<NUM;i++,l+=n-1)
	{
		data=init=goal[temp[0]];
		n=0;
		do
		{
			for(j++,n++,m=0;m<NUM-j;m++)
				if(goal[temp[m]]==data) break;
			data=start[temp[m]];
			memcpy(temp+m,temp+m+1,NUM-j-m);
			temp[NUM-j]=0;
		}
		while(init!=data);
	}
	return l;
}

int CChessView::Start2GoalZ(unsigned char *start, unsigned char *goal,int NUM)
{
//当前状态到目标状态未移动的码数
	int i,z;
	for(z=0,i=0;i<NUM;i++)
		z+=(start[i]==goal[i])? 1:0;
	return z;
}

void CChessView::OnUpdate(CView* pSender, LPARAM lHint, CObject* pHint) 
{
	// TODO: Add your specialized code here and/or call the base class
	CChessDoc *pDoc=GetDocument();

	m_N=pDoc->m_N;
	m_NUM=pDoc->m_NUM;
	m_nType=pDoc->m_nType;
	
	memcpy(m_strStart,pDoc->m_strStart,m_NUM);
	memcpy(m_strEnd,pDoc->m_strEnd,m_NUM);
	Invalidate();
	
}	
void CChessView::ShowResult(CPoint &p0,int gridwidth,int vert,int hori,CDC *pDC)
{
	CChessDoc *pDoc=GetDocument();
	CPathNode *info;
	int i,j;
	int nextspace;
	

	for(i=0;i<pDoc->m_nResult ;i++)
	for(i=0;i<1;i++)
	{
		info=new CPathNode(m_N,p0,gridwidth);

		memcpy(info->state,pDoc->m_strStart,m_NUM);
		info->space=strcspn((char*)info->state,"0");
		info->DrawNode(pDC);

		CResult *res=&pDoc->m_Result[i];
		for(j=0;j<res->depth;j++)
		
		{
			CPoint tempPoint((float)info->P0.x+
				((float)m_N*(float)gridwidth+(float)hori)*(2.0*(float)res->rules[j]-3.0)/2.0,
				(float)info->P0.y+(float)m_N*(float)gridwidth+(float)vert);
			
			pDC->MoveTo(info->P1);
			pDC->LineTo(tempPoint.x+(float)m_N*(float)gridwidth/2.0,tempPoint.y);
			
			info->P0.x=tempPoint.x;
			info->P0.y=tempPoint.y;
			info->P1.x=(float)info->P0.x+(float)info->width/2.0;
			info->P1.y=(float)info->P0.y+(float)info->N*(float)gridwidth;

			if((info->P0.x-gridwidth)<m_Rect.left) m_Rect.left=info->P0.x-gridwidth;
			if((info->P0.x+gridwidth)>m_Rect.left) m_Rect.right=info->P0.x+gridwidth+50;
			if(info->P1.y>m_Rect.bottom) m_Rect.bottom=info->P1.y+50;

			
			nextspace=info->space+(2*res->rules[j]-3)/2*m_N+
				1/(2*res->rules[j]-3);
			info->state[info->space]=info->state[nextspace];
			info->state[nextspace]='0';
			info->space=nextspace;
			info->DrawNode(pDC);
		}
		delete info;
	}
	
}