شطرنج در سی شارپ

8 شاه
[ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

// 8Queen.cpp : Defines the entry point for the application.
//

#include "stdafx.h"
#include "resource.h"
#include "8Queen.h"
#include <process.h>
#include <stdio.h>

// Global Variables:
HINSTANCE hInst; // current instance
TCHAR szTitle[MAX_LOADSTRING]; // The title bar text
TCHAR szWindowClass[MAX_LOADSTRING]; // The title bar text
BOOL g_Stop;
int g_BoardSize;
BOOL **g_QueenArray;

int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
// TODO: Place code here.
MSG msg;
HACCEL hAccelTable;

// Initialize global strings
LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadString(hInstance, IDC_MY8QUEEN, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);

if(DialogBox(hInst, (LPCTSTR)DLG_SIZE, GetDesktopWindow(), (DLGPROC)SizeProc) == IDCANCEL)
return TRUE;

// Perform application initialization:
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}

hAccelTable = LoadAccelerators(hInstance, (LPCTSTR)IDC_MY8QUEEN);

// Main message loop:
while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}

return msg.wParam;
}

//
// FUNCTION: MyRegisterClass()
//
// PURPOSE: Registers the window class.
//
// COMMENTS:
//
// This function and its usage is only necessary if you want this code
// to be compatible with Win32 systems prior to the 'RegisterClassEx'
// function that was added to Windows 95. It is important to call this function
// so that the application will get 'well formed' small icons associated
// with it.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;

wcex.cbSize = sizeof(WNDCLASSEX);

wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = (WNDPROC)WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = LoadIcon(hInstance, (LPCTSTR)IDI_MY8QUEEN);
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = (LPCSTR)IDC_MY8QUEEN;
wcex.lpszClassName = szWindowClass;
wcex.hIconSm = LoadIcon(wcex.hInstance, (LPCTSTR)IDI_SMALL);

return RegisterClassEx(&wcex);
}

//
// FUNCTION: InitInstance(HANDLE, int)
//
// PURPOSE: Saves instance handle and creates main window
//
// COMMENTS:
//
// In this function, we save the instance handle in a global variable and
// create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HWND hWnd;

hInst = hInstance; // Store instance handle in our global variable

hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPED | WS_MINIMIZEBOX | WS_SYSMENU ,
CW_USEDEFAULT, CW_USEDEFAULT, WND_WIDTH, WND_HEIGHT, NULL, NULL, hInstance, NULL);

if (!hWnd)
{
return FALSE;
}

ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);

return TRUE;
}

//
// FUNCTION: WndProc(HWND, unsigned, WORD, LONG)
//
// PURPOSE: Processes messages for the main window.
//
// WM_COMMAND - process the application menu
// WM_PAINT - Paint the main window
// WM_DESTROY - post a quit message and return
//
//

unsigned __stdcall thread_fn(void *param)
{

MSG msg;

HWND hButton = CreateWindow("BUTTON", ">>",
BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE,
420, 510, 70, 30, (HWND)param, NULL,
(HINSTANCE)GetWindowLong((HWND)param, GWL_HINSTANCE), NULL);

// Main message loop:
while (GetMessage(&msg, hButton, 0, 0))
{
// if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
// {
//TranslateMessage(&msg);
//DispatchMessage(&msg);
SendMessage(GetParent(msg.hwnd), msg.message, msg.wParam, msg.lParam);

// }
}

return 0;

}

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
int wmId, wmEvent;
TCHAR szHello[MAX_LOADSTRING];
LoadString(hInst, IDS_HELLO, szHello, MAX_LOADSTRING);

static THREAD_DATA *td;
PAINTSTRUCT ps;
static HBITMAP hBitmap[2];
static SIZE BitmapSize;

static HWND hButton, hEdit;
static int Start_X, Start_Y;
char szCaption[16];
int i = 0;
static HANDLE hThread;

switch (message)
{
case WM_CREATE:
{

//load the bitmaps, create the button and static box
hBitmap[0] = LoadBitmap((HINSTANCE)GetWindowLong(hWnd, GWL_HINSTANCE),
MAKEINTRESOURCE(IDB_BITMAP1));

hBitmap[1] = LoadBitmap((HINSTANCE)GetWindowLong(hWnd, GWL_HINSTANCE),
MAKEINTRESOURCE(IDB_BITMAP2));

GetBitmapDimensionEx(hBitmap[0], &BitmapSize);

hButton = CreateWindow("BUTTON", ">>",
BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | BS_FLAT,
420, 510, 70, 30, hWnd, NULL,
(HINSTANCE)GetWindowLong(hWnd, GWL_HINSTANCE), NULL);

hEdit = CreateWindow("STATIC", "hello",
WS_CHILD | WS_VISIBLE | WS_BORDER | SS_BLACKFRAME,
10, 510, 70, 30, hWnd, NULL,
(HINSTANCE)GetWindowLong(hWnd, GWL_HINSTANCE), NULL);

//allocate memory
g_QueenArray = (BOOL**)calloc(g_BoardSize, sizeof(BOOL));
for(i = 0;i < g_BoardSize;i++)
{
*(g_QueenArray + i) = (BOOL*)calloc(g_BoardSize, sizeof(BOOL));
}

td = (THREAD_DATA*)malloc(sizeof(td));
}

case WM_COMMAND:
wmId = LOWORD(wParam);
wmEvent = HIWORD(wParam);
// Parse the menu selections:

if((HWND)lParam == hButton)
{
GetWindowText(hButton, szCaption, sizeof(szCaption));
if(!strcmp(szCaption, ">>"))
{
SetWindowText(hButton, "Stop");
for(i = 0;i < g_BoardSize;i++)
{
memset(*(g_QueenArray + i), 0, g_BoardSize * sizeof(BOOL));
}
InvalidateRect(hWnd, NULL, TRUE);

//EnableWindow(hButton, FALSE);
g_Stop = FALSE;

td->hWnd = hWnd;
td->Start_X = Start_X;
td->Start_Y = Start_Y;

DWORD idThread;
hThread = CreateThread(NULL, 0, &BacktrackingThread, (void*)td, 0, &idThread);

//Backtracking(hWnd, Start_X,Start_Y++);
(++Start_Y) %= g_BoardSize;

}
else
{
g_Stop = TRUE;
SetWindowText(hButton, ">>");
//wait untill thread stops
WaitForSingleObject(hThread, INFINITE );

}

}

switch (wmId)
{
case IDM_ABOUT:
DialogBox(hInst, (LPCTSTR)IDD_ABOUTBOX, hWnd, (DLGPROC)About);
break;

case IDM_EXIT:
DestroyWindow(hWnd);
break;

case MNU_SIZE:
DialogBox(hInst, (LPCTSTR)DLG_SIZE, GetDesktopWindow(), (DLGPROC)SizeProc);

//free and reallocate memory according to new size
g_QueenArray = (BOOL**)calloc(g_BoardSize, sizeof(BOOL));
for(i = 0;i < g_BoardSize;i++)
{
free(*(g_QueenArray + i));
*(g_QueenArray + i) = NULL;
}
free(g_QueenArray);
g_QueenArray = NULL;

g_QueenArray = (BOOL**)calloc(g_BoardSize, sizeof(BOOL));
for(i = 0;i < g_BoardSize;i++)
{
*(g_QueenArray + i) = (BOOL*)calloc(g_BoardSize, sizeof(BOOL));
}

Start_X = 0;
Start_Y = 0;
InvalidateRect(hWnd, NULL, TRUE);
break;

default:
return DefWindowProc(hWnd, message, wParam, lParam);
}

break;
case WM_PAINT:
BeginPaint(hWnd, &ps);
if(g_BoardSize)
DrawBoard(hWnd, g_BoardSize, ps, hBitmap, BitmapSize);

EndPaint(hWnd, &ps);
//UpdateWindow(hWnd);

break;

case WM_DESTROY:
//free memory
g_QueenArray = (BOOL**)calloc(g_BoardSize, sizeof(BOOL));
for(i = 0;i < g_BoardSize;i++)
{
free(*(g_QueenArray + i));
*(g_QueenArray + i) = NULL;
}
free(g_QueenArray);
g_QueenArray = NULL;
//free(td);
//td = NULL;

PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}

/**
given the size of the board, it draws the board
inside it, it calls the draw square which is responsible
for drawing the square, its color and queen inside it if it is required
*/

short DrawBoard(HWND hWnd, int BoardSize, PAINTSTRUCT ps, HBITMAP hQueenBitmap[2], SIZE QueenBitmapSize)
{
int OneBoxSize = WND_WIDTH / g_BoardSize;

for(int i = 0 ; i < BoardSize ; i++)
{
for(int j = 0 ; j < BoardSize ; j++)
{
//if i+j is even then its a white

if( (i+j)%2 == 0)
{
//it will be a white square.
DrawSquare(hWnd, (OneBoxSize * j), (OneBoxSize * i), WHITE, OneBoxSize, ps,
hQueenBitmap[0], QueenBitmapSize, *(*(g_QueenArray + i) + j));
}
else
{
//it will be a black square.
DrawSquare(hWnd, (OneBoxSize * j), (OneBoxSize * i), BLACK, OneBoxSize, ps,
hQueenBitmap[1], QueenBitmapSize, *(*(g_QueenArray + i) + j));
}
}
}

MoveToEx(ps.hdc, 0, (i * OneBoxSize), NULL);
LineTo(ps.hdc, WND_WIDTH, (i * OneBoxSize));

return SUCCESS_EXIT;
}

short DrawSquare(HWND hWnd, int Start_x, int Start_y, COLOR c, int OneBoxSize,
PAINTSTRUCT ps, HBITMAP hQueenBitmap, SIZE QueenBitmapSize, BOOL bQueenPresent)
{
RECT rect;

//Defining the dimensions of the box to be drawn...
rect.left = Start_x;
rect.top = Start_y;
rect.right = rect.left + OneBoxSize;
rect.bottom = rect.top + OneBoxSize;

HBRUSH MyBrush;

if(c == BLACK)
MyBrush = CreateSolidBrush(RGB(0,0,0));
else
MyBrush = CreateSolidBrush(RGB(255,255,255));

SelectObject(ps.hdc, MyBrush);

FillRect(ps.hdc, &rect, MyBrush);

DeleteObject(MyBrush);

//if queen is present in this square then draw the queen also.
if(bQueenPresent)
DrawQueen(hWnd, ps, rect, hQueenBitmap, QueenBitmapSize);

return SUCCESS_EXIT;
}

/**
Draws the queen inside @rect
*/
short DrawQueen(HWND hWnd, PAINTSTRUCT ps, RECT rect, HBITMAP hQueenBitmap, SIZE QueenBitmapSize)
{

if(hQueenBitmap == NULL || hWnd == NULL)
return ERROR_EXIT;

//bitmap is already loaded, just StretchBlt it on the square

HDC hdcSource = CreateCompatibleDC(NULL);
SelectObject(hdcSource, hQueenBitmap);

StretchBlt(ps.hdc,rect.left + 5, rect.top,rect.right - rect.left - 5, rect.bottom - rect.top,
hdcSource, 0, 0, 142, 284, SRCCOPY);

DeleteDC(hdcSource);

return SUCCESS_EXIT;
}

/**
tells if the queen is in danger at the current position
*/
bool IsQueenSafe(int CurrPosX, int CurrPosY)
{
int i, j;

//checking the horizontal line
for( i = 0 ; i < g_BoardSize ; i++ )
{
if( i != CurrPosY )
{
if( g_QueenArray[CurrPosX][i] == TRUE)
{
return false;
}
}
}

//checking the vertical line
for( i = 0 ; i < g_BoardSize ; i++ )
{
if( i != CurrPosX )
{
if( g_QueenArray[i][CurrPosY] == TRUE)
{
return false;
}
}
}

i = CurrPosX;
j = CurrPosY;
//Checking diagonally-down
while(!(i >= g_BoardSize-1 || j >= g_BoardSize-1))
{
if(g_QueenArray[++i][++j])
return false;
}

i = CurrPosX;
j = CurrPosY;
//Checking diagonally-up
while(!(i == 0 || j == 0))
{
if(g_QueenArray[--i][--j])
return false;
}

i = CurrPosX;
j = CurrPosY;
//Checking anti-diagonally-down
while(!(i >= g_BoardSize-1 || j == 0))
{
if(g_QueenArray[++i][--j])
return false;
}

i = CurrPosX;
j = CurrPosY;
//Checking anti-diagonally-up
while(!(i == 0 || j >= g_BoardSize-1))
{
if(g_QueenArray[--i][++j])
return false;
}

return true;
}

/**
this is the main recurssive backtracking function
it keeps on trying for new positions.
if the position is safe it tries for the next row
if no position is found in the current row which is safe then it backtracks
and try a different combination.
it keeps on trying untill it finds a solution.
this function is called in a thread so that the interface is responsive
*/
int Backtracking(HWND hWnd, int Pos_X, int Pos_Y)
{
int New_Y;
RECT rect;

if(g_BoardSize == 0)
return TRUE;

if(Pos_X == g_BoardSize)
return TRUE;

while(Pos_Y < g_BoardSize)
{
if(!SetNextQueen(Pos_X, Pos_Y, &New_Y))
return false;

int OneBoxSize = WND_WIDTH / g_BoardSize;

Pos_Y = New_Y;

rect.left = Pos_Y * OneBoxSize;
rect.right = (Pos_Y + 1) * (OneBoxSize);
rect.top = Pos_X * OneBoxSize;
rect.bottom = (Pos_X + 1) * OneBoxSize;

InvalidateRect(hWnd, &rect, TRUE);
//UpdateWindow(hWnd);
Sleep(400);
if(g_Stop)
{
g_Stop = FALSE;
return TRUE;
}

if(Backtracking(hWnd, Pos_X + 1, 0))
{
return TRUE;
}
else
{
rect.left = Pos_Y * OneBoxSize;
rect.right = (Pos_Y + 1) * (OneBoxSize);
rect.top = Pos_X * OneBoxSize;
rect.bottom = (Pos_X + 1) * OneBoxSize;

g_QueenArray[Pos_X][Pos_Y++] = FALSE;

InvalidateRect(hWnd, &rect, TRUE);
UpdateWindow(hWnd);
Sleep(400);

if(Pos_Y == g_BoardSize)
return false;
}
}

return TRUE;
}

/**
Set queen on a new square which is safe
*/
BOOL SetNextQueen(int Curr_X, int Curr_Y, int *New_Y)
{
//check if we can put a queen on the curr position
if(!g_QueenArray[Curr_X][Curr_Y])
{
g_QueenArray[Curr_X][Curr_Y] = TRUE;
if(IsQueenSafe(Curr_X, Curr_Y))
{
*New_Y = Curr_Y;
return TRUE;
}
else
{
g_QueenArray[Curr_X][Curr_Y] = FALSE;
}
}

while(1)
{

if(Curr_Y == g_BoardSize - 1)
return FALSE;

g_QueenArray[Curr_X][++Curr_Y] = TRUE;
if(IsQueenSafe(Curr_X, Curr_Y))
{
break;
}
else
{
g_QueenArray[Curr_X][Curr_Y] = FALSE;
}
}

*New_Y = Curr_Y;

return TRUE;
}

/**
Calls backtracking
*/
DWORD WINAPI BacktrackingThread(void *param)
{
THREAD_DATA *td = (THREAD_DATA*)param;

int retval = Backtracking(td->hWnd, td->Start_X,td->Start_Y++);

SetWindowText(FindWindowEx(td->hWnd, NULL, "BUTTON", "Stop"), ">>");

return(retval);
}

//Handler for size dialog
LRESULT CALLBACK SizeProc(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
int i;
char temp[16];

switch (message)
{
case WM_INITDIALOG:
{
HWND hList = GetDlgItem(hDlg, CMB_SIZE);

for(i = MIN_BOARD_SIZE - 1;i < MAX_BOARD_SIZE;i++)
{
sprintf(temp, "%d", i+1);
SendMessage(hList, CB_ADDSTRING, NULL, (LPARAM)temp);

}
SendMessage(hList, CB_SETCURSEL, TRUE, 0);

return TRUE;
}

case WM_COMMAND:
if (LOWORD(wParam) == IDOK)
{
HWND hList = GetDlgItem(hDlg, CMB_SIZE);

//find index and get the selection
int Index = SendMessage(hList, CB_GETCURSEL, 0,0);
SendMessage(hList, CB_GETLBTEXT, Index, (LPARAM)temp);
g_BoardSize = atoi(temp);
EndDialog(hDlg, LOWORD(wParam));
return TRUE;
}

if (LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return TRUE;
}

break;
}
return FALSE;

}

// Mesage handler for about box.
LRESULT CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
switch (message)
{
case WM_INITDIALOG:
//setting the about edit box
SetWindowText(GetDlgItem(hDlg, EDT_ABOUT),
"The program tries to put 'n' queens on a [n][n] chess board"
" so that no queen attacks any other queen on the board."
" The program uses brute force method and recursive backtracking to"
" put the queens and hence the time taken to place queen on the"
" board increases exponentially as 'n' increases.\r\n"
" ------------ V2.0 ------------\r\n"
" Backtracking is done in a thread so that the application is"
" responsive and is able to update the interface during the processing."
" ");
return TRUE;

case WM_COMMAND:
if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
{
EndDialog(hDlg, LOWORD(wParam));
return TRUE;
}
break;
}
return FALSE;
}