eightqueenview.cpp

人工智能中八皇后问题的算法演示

// EightQueenView.cpp : implementation of the CEightQueenView class
//

#include "stdafx.h"
#include "EightQueen.h"

#include "EightQueenDoc.h"
#include "EightQueenView.h"


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

/////////////////////////////////////////////////////////////////////////////
// CEightQueenView

IMPLEMENT_DYNCREATE(CEightQueenView, CView)

BEGIN_MESSAGE_MAP(CEightQueenView, CView)
	//{{AFX_MSG_MAP(CEightQueenView)
	ON_COMMAND(ID_MYSTART, OnMystart)
	ON_WM_MOUSEMOVE()
	ON_WM_LBUTTONDOWN()
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CEightQueenView construction/destruction

CEightQueenView::CEightQueenView()
{
	// TODO: add construction code here
	Grid_Width = 50;
	Init();
}

CEightQueenView::~CEightQueenView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CEightQueenView drawing

void CEightQueenView::OnDraw(CDC* pDC)
{
	CEightQueenDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);

	WINDOWPLACEMENT *lpwndpl  = new WINDOWPLACEMENT;
	GetWindowPlacement(lpwndpl);
		
	int DocSizey = lpwndpl->rcNormalPosition.bottom-lpwndpl->rcNormalPosition.top-4;
	int DocSizex = lpwndpl->rcNormalPosition.right-lpwndpl->rcNormalPosition.left-4;
	int posx = (int)(DocSizex - Grid_Width * 8) / 2;
	int posy = (int)(DocSizey - Grid_Width * 8) / 2;
	
	CBitmap bitmap_8Queen;
	bitmap_8Queen.LoadBitmap(IDB_8Queen);
	
	BITMAP* pBitMap = new BITMAP;
	bitmap_8Queen.GetBitmap(pBitMap);
	
	int bitmap_width = pBitMap->bmWidth;
	int bitmap_height = pBitMap->bmHeight;
	
	int bitmap_pos_x = (int)(DocSizex - bitmap_width-100) / 2;
	int bitmap_pos_y = (int)(posy - bitmap_height) / 2;
	CFont m_Font;
	m_Font.CreatePointFont(330,"隶书",pDC);
	pDC->SelectObject(&m_Font);
	CString str;
	str.Format("%d",PreRecord+1);
	str = "第"+ str+"种解";
	pDC->TextOut(bitmap_pos_x+bitmap_width,bitmap_pos_y,str);//(bitmap_pos_x+100,bitmap_pos_y,"第0种解");

	CDC pdc;
	pdc.CreateCompatibleDC(pDC);
	pdc.SelectObject(&bitmap_8Queen);

	pDC->BitBlt(bitmap_pos_x,bitmap_pos_y,bitmap_width,bitmap_height,&pdc,0,0,SRCCOPY);

	COLORREF TopLeft = ::GetSysColor(COLOR_BTNHILIGHT);
	COLORREF BottomRight = ::GetSysColor(COLOR_BTNSHADOW);
	int i,j;
	char color;
	for(i=0;i<8;++i)
	{
		if((i%2) == 0)
			color = 'b';
		else
			color = 'w';
		for(j=0;j<8;++j)
		{
			if(color == 'b')
			{
				pDC->FillSolidRect(posx+i*Grid_Width,posy+j*Grid_Width,
					Grid_Width,Grid_Width,RGB(0,0,0));
				color = 'w';
			}
			else
			{
				pDC->FillSolidRect(posx+i*Grid_Width,posy+j*Grid_Width,
					Grid_Width,Grid_Width,RGB(255,255,255));
				color = 'b';
			}
			pDC->Draw3dRect(posx+i*Grid_Width,posy+j*Grid_Width,
				Grid_Width,Grid_Width,TopLeft,BottomRight);
		}
	}
	// TODO: add draw code for native data here

	//画棋子
	for(i=0;i<8;++i)
	{
		if(Queen_Pos[i] != -1)
		{
			Put_Queen_Bitmap(i,Queen_Pos[i]);
		}
	}

	//判断载入何种Previour图片
	CBitmap m_BitmapNext;
	CBitmap m_BitmapPrev;
	if(m_bPrevChecked)
	{
		m_BitmapPrev.LoadBitmap(IDB_PREVIOUR_CHECKED);
	}
	else
	{
		m_BitmapPrev.LoadBitmap(IDB_PREVIOUR);
	}
	//计算Previour按扭的位置
	m_BitmapPrev.GetBitmap(pBitMap);

	bitmap_width = pBitMap->bmWidth;
	bitmap_height = pBitMap->bmHeight;

	bitmap_pos_x = (int)(DocSizex - bitmap_width*2 - 200) / 2;
	bitmap_pos_y = (int)((posy - bitmap_height) / 2) + (DocSizey - posy);
	
	//画Previour按扭
	pdc.SelectObject(&m_BitmapPrev);
	pDC->BitBlt(bitmap_pos_x,bitmap_pos_y,bitmap_width,bitmap_height,&pdc,0,0,SRCCOPY);
	
	//记录Previour按扭的位置
	m_CRectPrev.left = bitmap_pos_x;
	m_CRectPrev.right = bitmap_pos_x + bitmap_width;
	m_CRectPrev.top = bitmap_pos_y;
	m_CRectPrev.bottom = bitmap_pos_y + bitmap_height;
	
	//判断载入何种Next图片
	if(m_bNextChecked)
	{
		m_BitmapNext.LoadBitmap(IDB_NEXT_CHECKED);
	}
	else
	{
		m_BitmapNext.LoadBitmap(IDB_NEXT);
	}
	//计算Next按扭的位置
	bitmap_pos_x += 200;
	
	//画Next按扭
	pdc.SelectObject(&m_BitmapNext);
	pDC->BitBlt(bitmap_pos_x,bitmap_pos_y,bitmap_width,bitmap_height,&pdc,0,0,SRCCOPY);
	
	//记录Nect按扭的位置
	m_CRectNext.left = bitmap_pos_x;
	m_CRectNext.right = bitmap_pos_x + bitmap_width;
	m_CRectNext.top = bitmap_pos_y;
	m_CRectNext.bottom = bitmap_pos_y + bitmap_height;
}

/////////////////////////////////////////////////////////////////////////////
// CEightQueenView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CEightQueenView diagnostics

#ifdef _DEBUG
void CEightQueenView::AssertValid() const
{
	CView::AssertValid();
}

void CEightQueenView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

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

/////////////////////////////////////////////////////////////////////////////
// CEightQueenView message handlers

void CEightQueenView::Put_Queen()
{
	int i,j;
	bool Have_put;
	while(true)
	{
		if(Pre_Column<8)
		{
			Have_put = false;
			for(i=0;i<8;++i)
			{
				if((Queen_Pos[i] == -1) && (Diagonal(i,Pre_Column)) && 
					(!record[Pre_Column][i]))
				{
					//记录
					Queen_Pos[i] = Pre_Column;
					record[Pre_Column][i] = true;
					Have_put = true;
					Pre_Column++;

				}
			}
			if(!Have_put)
			{
				//没有找到合适的位置，回溯
			
				for(j=0;j<8;++j)
				{
					if(Queen_Pos[j] == Pre_Column-1)
					{
						//消去上一行的棋子
						Remove_Queen_Bitmap(j,Pre_Column-1);
						Queen_Pos[j] = -1;
					}
					if(record[Pre_Column][j])
					{
						record[Pre_Column][j] = false;
					}
				}
				Pre_Column--;

			}
		}
		else
		{
			//保存记录
			for(i=0;i<8;++i)
			{
				QueenPos_Record[PreNumRecord][i] = Queen_Pos[i];
			}
			PreNumRecord++;
			PreRecord++;
			OnDraw(GetDC());
			break;
		}
	}

}

void CEightQueenView::Init()
{
	int i,j;
	//记录初始化
	for(i=0;i<8;++i)
	{
		for(j=0;j<8;++j)
		{
			record[i][j] = false;
		}
	}
	Pre_Column = 0;
	for(i=0;i<8;++i)
		Queen_Pos[i] = -1;

	PreNumRecord = 0;
	PreRecord = -1;
	m_bNextChecked = FALSE;
	m_bPrevChecked = FALSE;
}


bool CEightQueenView::Diagonal(int row, int column)
{
	int m_row = row - 1;
	int m_column = column - 1;
	while((m_row<8) && (m_column<8) && (m_row>=0) && (m_column>=0))
	{
		if(Queen_Pos[m_row] == m_column)
		{
			return false;
		}
		else
		{
			m_row--;
			m_column--;
		}
	}
	m_row = row + 1;
	m_column = column + 1;
	while((m_row<8) && (m_column<8) && (m_row>=0) && (m_column>=0))
	{
		if(Queen_Pos[m_row] == m_column)
		{
			return false;
		}
		else
		{
			m_row++;
			m_column++;
		}
	}

	m_row = row + 1;
	m_column = column - 1;
	while((m_row<8) && (m_column<8) && (m_row>=0) && (m_column>=0))
	{
		if(Queen_Pos[m_row] == m_column)
		{
			return false;
		}
		else
		{
			m_row++;
			m_column--;
		}
	}

	m_row = row - 1;
	m_column = column + 1;
	while((m_row<8) && (m_column<8) && (m_row>=0) && (m_column>=0))
	{
		if(Queen_Pos[m_row] == m_column)
		{
			return false;
		}
		else
		{
			m_row--;
			m_column++;
		}
	}
	return true;	
}

void CEightQueenView::Put_Queen_Bitmap(int row, int column)
{
	char grid_color;
	//计算所在的方格的颜色
	if((column % 2) == 0)
	{
		if((row % 2) == 0)
		{
			grid_color = 'B';
		}
		else
		{
			grid_color = 'W';
		}
	}
	else
	{
		if((row % 2) == 0)
		{
			grid_color = 'W';
		}
		else
		{
			grid_color = 'B';
		}
	}

	CDC* pDC = GetDC();
	CDC pdc;
	pdc.CreateCompatibleDC(pDC);
	CBitmap bitmap_Queen;
	

	//调入相应的位图
	if(grid_color == 'B')
	{
		bitmap_Queen.LoadBitmap(IDB_QUEEN_BLACK);
	}
	else
	{
		bitmap_Queen.LoadBitmap(IDB_QUEEN_WHITE);
	}
	pdc.SelectObject(&bitmap_Queen);

	//计算放置的位置
	WINDOWPLACEMENT *lpwndpl  = new WINDOWPLACEMENT;
	GetWindowPlacement(lpwndpl);
		
	int DocSizey = lpwndpl->rcNormalPosition.bottom-lpwndpl->rcNormalPosition.top-4;
	int DocSizex = lpwndpl->rcNormalPosition.right-lpwndpl->rcNormalPosition.left-4;
	int posx = (int)(DocSizex - Grid_Width * 8) / 2;
	int posy = (int)(DocSizey - Grid_Width * 8) / 2;

	int queen_pos_x = posx + row * Grid_Width;
	int queen_pos_y = posy + column * Grid_Width;
	pDC->BitBlt(queen_pos_x,queen_pos_y,Grid_Width,Grid_Width,&pdc,0,0,SRCCOPY);


}

void CEightQueenView::Remove_Queen_Bitmap(int row, int column)
{
	char grid_color;
	//计算所在的方格的颜色
	if((column % 2) == 0)
	{
		if((row % 2) == 0)
		{
			grid_color = 'B';
		}
		else
		{
			grid_color = 'W';
		}
	}
	else
	{
		if((row % 2) == 0)
		{
			grid_color = 'W';
		}
		else
		{
			grid_color = 'B';
		}
	}

	CDC* pDC = GetDC();
	COLORREF Pre_Color;

	if(grid_color == 'B')
	{
		Pre_Color = RGB(0,0,0);
	}
	else
	{
		Pre_Color = RGB(255,255,255);
	}

	//计算放置的位置
	WINDOWPLACEMENT *lpwndpl  = new WINDOWPLACEMENT;
	GetWindowPlacement(lpwndpl);
		
	int DocSizey = lpwndpl->rcNormalPosition.bottom-lpwndpl->rcNormalPosition.top-4;
	int DocSizex = lpwndpl->rcNormalPosition.right-lpwndpl->rcNormalPosition.left-4;
	int posx = (int)(DocSizex - Grid_Width * 8) / 2;
	int posy = (int)(DocSizey - Grid_Width * 8) / 2;
	
	pDC->FillSolidRect(posx+row*Grid_Width,posy+column*Grid_Width,
		Grid_Width,Grid_Width,Pre_Color);

	COLORREF TopLeft = ::GetSysColor(COLOR_BTNHILIGHT);
	COLORREF BottomRight = ::GetSysColor(COLOR_BTNSHADOW);
	pDC->Draw3dRect(posx+row*Grid_Width,posy+column*Grid_Width,
				Grid_Width,Grid_Width,TopLeft,BottomRight);
}



void CEightQueenView::OnMystart() 
{
	// TODO: Add your command handler code here
	Put_Queen();
}

void CEightQueenView::OnMouseMove(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if((point.x>m_CRectPrev.left) && (point.x<m_CRectPrev.right) &&
		(point.y>m_CRectPrev.top) && (point.y<m_CRectPrev.bottom))
	{
		if(!m_bPrevChecked)
		{
			m_bPrevChecked = TRUE;
			OnDraw(GetDC());
		}
	}
	else
	{
		if(m_bPrevChecked)
		{
			m_bPrevChecked = FALSE;
			OnDraw(GetDC());
		}
	}

	if((point.x>m_CRectNext.left) && (point.x<m_CRectNext.right) &&
		(point.y>m_CRectNext.top) && (point.y<m_CRectNext.bottom))
	{
		if(!m_bNextChecked)
		{
			m_bNextChecked = TRUE;
			OnDraw(GetDC());
		}
	}
	else
	{
		if(m_bNextChecked)
		{
			m_bNextChecked = FALSE;
			OnDraw(GetDC());
		}
	}
	CView::OnMouseMove(nFlags, point);
}

void CEightQueenView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	int i,j;
	if(m_bPrevChecked)
	{
		if(PreRecord>0)
		{
			PreRecord--;
		
			//从记录中提取放置的位置
			for(i=0;i<8;++i)
			{
				Queen_Pos[i] = QueenPos_Record[PreRecord][i];
			}
			OnDraw(GetDC());
		}
	}
	if(m_bNextChecked)
	{
		if(PreRecord == (PreNumRecord-1))
		{//显示的是新产生的
		
			if(Pre_Column != 0)
			{
				//在棋盘上消去棋子
				for(j=0;j<8;++j)
				{
					if(Queen_Pos[j] == Pre_Column-1)
					{
						//消去该行的棋子
						Remove_Queen_Bitmap(j,Pre_Column-1);
						//清除记录
						Queen_Pos[j] = -1;
					}
				}
				Pre_Column--;
			}
			Put_Queen();
		}
		else
		{
			if(PreRecord<91)
			{
				PreRecord++;
			
				//从记录中提取放置的位置
				for(i=0;i<8;++i)
				{
					Queen_Pos[i] = QueenPos_Record[PreRecord][i];
				}
				OnDraw(GetDC());
			}
		}
		
	}
	CView::OnLButtonDown(nFlags, point);
}