main.cpp

数据结构课程设计-八皇后算法的实现。 使用链表堆栈来实现的

/////////////////////////////////////////////////////////////////////////////////////
//                
//                  $ Data structure program project $
// 
// Project name:         Eight queens problem
// Program description:  In the 8*8 chessboard there is one queen in every line must:
//                       (1)not same line (2)not same colcumn(3)not same diagonal
// Complete Language  :  C++ program language
// Program Workplat   :  Win32 SDK
// Group   Members    :  Class 2 Yang zhuo  20034399
//                       Class 2 Li binghai 20034383
//                       Class 2 Li peng    20034447
// Complete Date      :  1/7/2005
// 
/////////////////////////////////////////////////////////////////////////////////////

#include <windows.h>
#include <assert.h>
#include "stdio.h"
#include "LinkedStack.h"
#include "Position.h"
#include "resource.h"

LRESULT CALLBACK WndProc(HWND hwnd , UINT message , WPARAM wParam , LPARAM lParam) ;


TCHAR szAppName[] = TEXT ("MENU") ;
TCHAR szIconName[] = TEXT ("ICON") ;
static HBITMAP hbmpBoard = NULL , hbmpButton = NULL , hbmpIcon = NULL ,
               hbmpButton1 = NULL , hbmQueen = NULL , hbmReset = NULL ;
static HINSTANCE hInstance ;
PAINTSTRUCT ps ;
HWND hwnd ;
static int iCount = 1 ;

static int Queen[8][8];
static int a[8];
static int b[15];
static int c[15];
static int iQueenNum=0;  /*记录总的棋盘状态数*/

static LinkedStack<Position> QueuePos  ;
static Position ps1(0 , 0) ;

void qu(int i , LinkedStack<Position> &pos , Position &ps);  /*参数i代表行*/

void initial()
{
	int iLine,iColumn;

	//棋盘初始化
	for(iLine=0;iLine<8;iLine++)
	{
		a[iLine]=0;  //列标记初始化，表示无列冲突
		for(iColumn=0;iColumn<8;iColumn++)
			Queen[iLine][iColumn] =0;
	}

	//主、从对角线标记初始化，表示没有冲突
	for(iLine=0;iLine<15;iLine++)
		b[iLine]=c[iLine]=0;

	qu(0 ,QueuePos , ps1);
}

void Draw(HWND hwnd , HBITMAP &hbmBitmap , LinkedStack<Position> &pos) ;

void qu(int i , LinkedStack<Position> &pos , Position &ps)
{
	int iColumn;

	for(iColumn=0;iColumn<8;iColumn++)
	{
		if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0) /*如果无冲突*/
		{
			Queen[i][iColumn]=1; /*放皇后*/
			a[iColumn]=1;   /*标记，下一次该列上不能放皇后*/
			b[i-iColumn+7]=1;  /*标记，下一次该主对角线上不能放皇后*/
			c[i+iColumn]=1;   /*标记，下一次该从对角线上不能放皇后*/
			if(i<7) qu(i+1 , pos , ps); /*如果行还没有遍历完，进入下一行*/
			else    
			{
				int iLine,iColumn;

				for(iLine=0;iLine<8;iLine++)
				{
					for(iColumn=0;iColumn<8;iColumn++)
					{
						if(Queen[iLine][iColumn] == 1)
						{
							ps.SetXDistance(iLine) ;
							ps.SetYDistance(iColumn) ;
							pos.Add(ps) ;
						}
					}

				}
			}

			/*如果前次的皇后放置导致后面的放置无论如何都不能满足要求，则回溯，重置*/
			Queen[i][iColumn] = 0 ;
			a[iColumn]=0;
			b[i-iColumn+7]=0;
			c[i+iColumn]=0;
		}
	}
}

void Draw(HDC hdc , HDC hdcMem , HBITMAP &hbmBitmap)
{
	Position QueenPosition = QueuePos.Top() ;

	for(int a = 0 ; a < 8 ; a++)
	{
		QueuePos.Delete(QueenPosition) ;
		SelectObject(hdcMem , hbmBitmap) ;
		BitBlt(hdc ,QueenPosition.GetXDistance() * 40 , QueenPosition.GetYDistance() * 40
			, 40 , 40 , hdcMem , 0 , 0 , SRCCOPY) ;
	}

	DeleteDC(hdc) ;
	ReleaseDC(hwnd , hdc) ;
}

void Reset(HDC hdc , HDC hdcMem , HBITMAP &hbmBitmap)
{
	for(int i = 0 ; i < 8 ; i++)
	{
		for(int j = 0 ; j < 8 ; j++)
		{
			SelectObject(hdcMem , hbmpBoard) ;
			BitBlt(hdc , j * 40 , i * 40 , 40 , 40 , hdcMem , 0 , 0 , SRCCOPY) ;
		}
	}
}

int WINAPI  WinMain(HINSTANCE hInstance , HINSTANCE hPrevInstance , 
					  PSTR szCmdLine , int iCmdShow)
{
	HWND hwnd ;
	MSG msg ;
	WNDCLASS wndclass ;

	wndclass.style		 = CS_HREDRAW | CS_VREDRAW | CS_DBLCLKS ;
	wndclass.lpfnWndProc = WndProc ;
	wndclass.cbClsExtra  = 0 ;
	wndclass.cbWndExtra  = 0 ;
	wndclass.hInstance   = hInstance ;
	wndclass.hIcon		  = LoadIcon (hInstance, szIconName) ;
  	wndclass.hCursor	  = LoadCursor (NULL, IDC_ARROW) ;
 	wndclass.hbrBackground	= (HBRUSH) GetStockObject (WHITE_BRUSH) ;
  	wndclass.lpszMenuName	= szAppName ;
	wndclass.lpszClassName	= szAppName ;

	if (!RegisterClass (&wndclass))
     {
		MessageBox (	NULL, TEXT ("This program requires Windows NT!"), 
          				szAppName, MB_ICONERROR) ;
		return 0 ;
     }
	hwnd = CreateWindow( szAppName,	// window class name
			TEXT ("MazeMouse Game"),	// window caption
			WS_BORDER|WS_CAPTION|WS_SYSMENU|WS_MINIMIZEBOX,	// window style
			20,	// initial x position
			20,	// initial y position
			12 * 40 ,	// initial x size
			10 * 40 ,	// initial y size
			NULL,			// parent window handle
		    NULL,	        // window menu handle
		    hInstance,	    // program instance handle
		    NULL) ; 	    // creation parameters
     
	ShowWindow (hwnd, iCmdShow) ;
	UpdateWindow (hwnd) ;
     
	while (GetMessage (&msg, NULL, 0, 0))
     {
		TranslateMessage (&msg) ;
  		DispatchMessage (&msg) ;
     }
	return msg.wParam ;
}

LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	HDC			hdc , hdcMem ;
	PAINTSTRUCT ps ;
	HMENU hMenu ;
	HICON hIcon ;
	int i = 0 , j = 0 ;
	TCHAR text[1024] ;

	static POINT ptPosition , ptBmpButton ;
	
	hdc = GetDC( hwnd );
	assert( hdc );
	hdcMem = CreateCompatibleDC( hdc );
     
	switch (message)
     {
	case WM_CREATE:
		hInstance =((LPCREATESTRUCT) lParam)->hInstance ;
		hbmpBoard = LoadBitmap(hInstance , "Board") ;
		hbmpButton = LoadBitmap(hInstance , "Button") ;
		hbmpButton1 = LoadBitmap(hInstance , "Button1") ;
		hbmQueen = LoadBitmap(hInstance , "Queen") ;
		hbmpIcon = LoadBitmap(hInstance , "ICON") ;

		initial() ;		
		hMenu = LoadMenu(hInstance , szAppName) ;
		hIcon = LoadIcon(hInstance , szIconName) ;
		return 0;	
		
	 case 	WM_PAINT:
		hdc = BeginPaint (hwnd, &ps) ;
		hdcMem = CreateCompatibleDC( hdc ) ;

		for(i = 0 ; i < 8 ; i++)
		{
			for(j = 0 ; j < 8 ; j++)
			{
				SelectObject(hdcMem , hbmpBoard) ;
				BitBlt(hdc , j * 40 , i * 40 , 40 , 40 , hdcMem , 0 , 0 , SRCCOPY) ;
			}
		}

		i = j = 0 ;

		SelectObject(hdcMem , hbmpButton) ;
		BitBlt(hdc , 330 , 120 , 135 , 57 , hdcMem , 0 , 0 , SRCCOPY) ;
		
   		DeleteDC( hdcMem );  
        ReleaseDC(hwnd , hdc) ;
  		EndPaint (hwnd, &ps) ;
		return 0 ;
	case	WM_COMMAND:
		switch (LOWORD (wParam))
		{
			case IDM_GAME_EXIT:
				int i ;
				i = MessageBox(hwnd , "你是否真的要退出？" , "message" , 1) ;
				if (i == 1)
					SendMessage (hwnd, WM_CLOSE, 0, 0) ;
			return 0;
		}

	case	WM_LBUTTONDOWN:
		ptPosition.x = LOWORD (lParam) ;
		ptPosition.y = HIWORD (lParam) ;

		hdc = GetDC(hwnd) ;
		hdcMem = CreateCompatibleDC( hdc ) ;

		if(ptPosition.x >= 350 && ptPosition.x <= 450
			&& ptPosition.y >= 130 && ptPosition.y <= 187)
		{
			sprintf(text , "第[%d]种方法" , iCount) ;
			TextOut (hdc, 340, 190, text, strlen(text)) ;
			
			SelectObject(hdcMem , hbmpButton1) ;
			BitBlt(hdc , 330 , 120 , 135 , 57 , hdcMem , 0 , 0 , SRCCOPY) ;

			Reset(hdc , hdcMem , hbmpBoard) ;
			Draw(hdc , hdcMem , hbmQueen) ;
			iCount ++ ;
		}

		DeleteDC(hdcMem) ;
		ReleaseDC(hwnd , hdc) ;
		return 0 ;

	case	WM_LBUTTONUP:
		hdc = GetDC(hwnd) ;
		hdcMem = CreateCompatibleDC( hdc ) ;
		
		SelectObject(hdcMem , hbmpButton) ;
		BitBlt(hdc , 330 , 120 , 135 , 57 , hdcMem , 0 , 0 , SRCCOPY) ;

		DeleteDC(hdcMem) ;
		ReleaseDC(hwnd , hdc) ;
		return 0 ;
		

	case	WM_DESTROY:
		DeleteObject(hbmpBoard) ;
		DeleteObject(hbmpButton) ;
		DeleteObject(hbmpButton1) ;
		DeleteObject(hbmQueen) ;
		PostQuitMessage (0) ;
		return 0 ;
     }
   return DefWindowProc (hwnd, message, wParam, lParam) ;
}