cqueen.cpp

采用c++编写,上机运行通过的N皇后实现代码,绝对可用

#include "stdafx.h"
#include "CQueen.h"

CQueen::CQueen(int row)
{
	m_bRuning = false;
	m_piSaveQPlace = NULL;
	m_pGridBitmap = NULL;
	m_pPlaceList = NULL;
	SetRow(row);
	m_iNowCol = 0;
}

CQueen::CQueen()
{
	m_bRuning = false;
	m_piSaveQPlace = NULL;
	m_pPlaceList = NULL;
	SetRow(0);
}

CQueen::~CQueen()
{
	if (m_piSaveQPlace != NULL) 
		delete m_piSaveQPlace;

	if (m_pGridBitmap != NULL)
		delete m_pGridBitmap;

	FreeList();
}

CSize CQueen::GetQueenGridSize()
{
	return m_sizeView;
}

int CQueen::GetQueenPlace(int row)
{
	int ret = -1;
	if (row < m_iCount && row >= 0)
		ret = m_piSaveQPlace[row];
	return ret;
}

void CQueen::SetRow(int row)
{
	if (m_bRuning)
	{
		return;
	}

	m_iCount = row;
	m_sizeView.cx = m_iCount * 40;
	m_sizeView.cy = m_iCount * 40;

	if (row == 0 || m_bRuning) return;

	if (m_pGridBitmap != NULL)
	{
		delete m_pGridBitmap;
	}

	m_pGridBitmap = new CBitmap();
	CDC *pDC = CDC::FromHandle(::GetDC(NULL));
	CDC MemDC;
	MemDC.CreateCompatibleDC(pDC);
	CRect rect(0,0,m_sizeView.cx,m_sizeView.cy);
	m_pGridBitmap->CreateCompatibleBitmap(pDC , m_sizeView.cx , m_sizeView.cy);
	
	CBitmap *oldbmp = MemDC.SelectObject(m_pGridBitmap);
	CBrush brush(RGB(255 , 255 , 255));
	MemDC.FillRect(rect , &brush);
	
	CBrush brushblue(RGB(0,0,255));
	
	for ( int i = 0 ; i < m_iCount ; i ++ )
	{
		rect.SetRect(0,0,40,40);
		rect.OffsetRect( 0 , i * 40);
		for ( int j = 0 ; j < m_iCount ; j ++ )
		{
			if (((j + i) % 2))
				MemDC.FillRect(rect , &brushblue);
			rect.OffsetRect(40, 0 );
		}
	}

	MemDC.SelectObject(oldbmp);
	::ReleaseDC(NULL , pDC->GetSafeHdc());

	if (m_piSaveQPlace != NULL)
		delete m_piSaveQPlace;

	m_piSaveQPlace = new int[m_iCount];
	
	for ( int j = 0 ; j < m_iCount; j ++)
	{
		m_piSaveQPlace[j] = -1;
	}

	FreeList();
	
	m_pPlaceList = new PlaceList[10];
	m_iListMaxSize = 10;
	m_iListNowSize = 0;

	m_iDrawIndex = -1;
}

void CQueen::ComputQueenPlace(int column , CView *view)
{
	int row = 0;
	int i ;
	int col ;

	m_iNowCol = column;

	// 相等说明全部递归完成
	if (column == m_iCount)
	{
		AddPlace(m_piSaveQPlace);
		m_bRuning = false;
		return;
	}
	m_bRuning = true;

	int *iPlaceOver = new int[m_iCount];
	
	// 初始化为都能放棋子
	for ( i = 0 ; i < m_iCount ; i ++)
	{
		iPlaceOver[i] = true;
	}
	
	// 将不能放棋子的点置False
	for (i = 0 ; i < column ; i ++)
	{
		col = m_piSaveQPlace[i];
		if ((col - (column - i)) >= 0)
		{
			iPlaceOver[col - (column - i)] = false;
		}
		if ((col + (column - i)) < m_iCount)
		{
			iPlaceOver[col + (column - i)] = false;
		}
		iPlaceOver[col] = false;
	}

	// 递归调用每一次的可能
	for (i = 0 ; i < m_iCount ; i ++)
	{
		if (iPlaceOver[i])
		{
			m_piSaveQPlace[column] = i;
			if (view != NULL && m_iDrawIndex == -1)
			{
				CDC *pDC = view->GetDC();
				DrawQueenN(pDC);
				view->ReleaseDC(pDC);
				Sleep(20);
			}
			ComputQueenPlace(column + 1 , view);
		}
	}
	m_bRuning = false;
	delete[] iPlaceOver;
	m_iNowCol = 0;
}

void CQueen::DrawQueenN(CDC *pDC)
{
	CBitmap bitmap;
	CDC MemDC;
	MemDC.CreateCompatibleDC(pDC);
	bitmap.CreateCompatibleBitmap(pDC , m_sizeView.cx , m_sizeView.cy);
	CBitmap * oldbmp = MemDC.SelectObject(&bitmap);
	DrawGird(&MemDC);
	DrawQueen(&MemDC);
	pDC->BitBlt(0 , 0  , m_sizeView.cx , m_sizeView.cy , &MemDC , 0 , 0 , SRCCOPY);
	MemDC.SelectObject(oldbmp);
}

void CQueen::DrawGird(CDC *pDC)
{
	if (m_pGridBitmap != NULL)
	{
		CDC MemDC;
		MemDC.CreateCompatibleDC(pDC);
		CBitmap *oldbitmap = MemDC.SelectObject(m_pGridBitmap);
		pDC->BitBlt( 0 , 0 , m_sizeView.cx , m_sizeView.cy , &MemDC , 0 , 0 , SRCCOPY);
		MemDC.SelectObject(oldbitmap);
	}
}

void CQueen::DrawQueen(CDC *pDC)
{
	CBrush brush(RGB(255,0,0));
	CRect rect;
	CBrush *oldbrush = pDC->SelectObject(&brush);
	for ( int i = 0 ; i <= m_iCount ; i ++)
	{
		rect.SetRect(0,0,40,40);
		if (m_iDrawIndex > -1)
			rect.OffsetRect(m_pPlaceList[m_iDrawIndex].Place[i] * 40 , i * 40);
		else
			rect.OffsetRect(m_piSaveQPlace[i] * 40 , i * 40);
		pDC->Ellipse(rect);
	}
	pDC->SelectObject(oldbrush);
}

void CQueen::AddPlace(int *place)
{
	if (m_iListNowSize == m_iListMaxSize)
	{
		m_iListMaxSize += 10;
		PlaceList *temlist = new PlaceList[m_iListMaxSize];
		for ( int i = 0 ; i < m_iListNowSize; i ++)
		{
			temlist[i].Place = m_pPlaceList[i].Place;
		}
		delete[] m_pPlaceList;
		m_pPlaceList = temlist;
	}
	int *iPlace = new int[m_iCount];
	for ( int i = 0 ; i < m_iCount ; i ++)
	{
		iPlace[i] = place[i];
	}
	m_pPlaceList[m_iListNowSize++].Place = iPlace;
}

void CQueen::FreeList()
{
	for ( int i = 0 ; i < m_iListNowSize ; i ++)
	{
		if (m_pPlaceList[i].Place != NULL)
		{
			delete[] m_pPlaceList[i].Place;
		}
	}
	if (m_pPlaceList)
	{
		delete[] m_pPlaceList;
	}
	m_iListMaxSize = 10;
	m_iListNowSize = 0;
}

void CQueen::DrawList(int index)
{
	if (index < m_iListNowSize)
	{
		m_iDrawIndex = index;
	}
	else
	{
		m_iDrawIndex = -1;
	}
}

int CQueen::GetListSize()
{
	return m_iListNowSize;
}

int CQueen::GetDrawIndex()
{
	return m_iDrawIndex;
}

void CQueen::SaveToBMPFile()
{
	CString name;
	CFileDialog fdlg( FALSE , NULL,NULL,OFN_HIDEREADONLY,"BMP File (*.bmp)|*.bmp||");
	if (fdlg.DoModal()==IDOK)
	{
		name = fdlg.GetPathName();
		CString tem;
		tem = name.Right(name.GetLength() - name.ReverseFind('.'));
		tem.MakeLower();
		if (tem != ".bmp" )
		{
			name += ".bmp";
		}
	}
	else
	{
		return;
	}
	CDC *pDC = CDC::FromHandle(::GetDC(NULL));	
	CBitmap bm;
	bm.CreateCompatibleBitmap(pDC,m_sizeView.cx , m_sizeView.cy);
	CDC tdc;
	tdc.CreateCompatibleDC(pDC);
	CBitmap *pOld=tdc.SelectObject(&bm);
	DrawQueenN(&tdc); //将图像画到临时DC
	tdc.SelectObject(pOld);
	BITMAP btm;
	bm.GetBitmap(&btm);
	DWORD size=btm.bmWidthBytes*btm.bmHeight;
	LPSTR lpData=(LPSTR)::GlobalAlloc(GPTR,size);
	/////////////////////////////////////////////
	BITMAPINFOHEADER bih;
	bih.biBitCount=btm.bmBitsPixel;
	bih.biClrImportant=0;
	bih.biClrUsed=0;
	bih.biCompression=0;
	bih.biHeight=btm.bmHeight;
	bih.biPlanes=1;
	bih.biSize=sizeof(BITMAPINFOHEADER);
	bih.biSizeImage=size;
	bih.biWidth=btm.bmWidth;
	bih.biXPelsPerMeter=0;
	bih.biYPelsPerMeter=0;
	GetDIBits(pDC->GetSafeHdc(),bm,0,bih.biHeight,lpData,(BITMAPINFO*)&bih,DIB_RGB_COLORS);
	BITMAPFILEHEADER bfh;
	bfh.bfReserved1=bfh.bfReserved2=0;
	bfh.bfType=((WORD)('M'<< 8)|'B');
	bfh.bfSize=54+size;
	bfh.bfOffBits=54;
	CFile bf;
	if(bf.Open(name,CFile::modeCreate|CFile::modeWrite))
	{
		bf.WriteHuge(&bfh,sizeof(BITMAPFILEHEADER));
		bf.WriteHuge(&bih,sizeof(BITMAPINFOHEADER));
		bf.WriteHuge(lpData,size);
		bf.Close();
	}
	GlobalFree(lpData);
	::ReleaseDC(NULL , pDC->GetSafeHdc());
}