Introduction
The program 8Queen tries to solve the famous chess queen problem. I started writing this program just for my own practice. After completion, I thought of uploading it on The Code Project. This is my first program here. I have learned a lot from The Code Project and hence thought of contributing something back so that someone can use this code and learn something.
The program can solve the queen problem for n = 5
to n = 15
. Though it is able to solve the problem for any value of 'n
', I took the upper range of 15
. It can be a good example to learn basic recursion, bitmap printing on the interface and a little bit of multi-threading.
Background
Most of the programmers must be knowing the chess queen problem because this is a famous problem in a data structures course. We have to put 'n
' queens on a n X n
board in such a way that each queen is safe. A queen in chess can move horizontally, vertically and diagonally to any length. So a queen should be placed in such a way that no other queen comes in the way. So the idea is to put the queens automatically on a chess board.
Using the Code
The code is very simple to use and understand. There is only one important file, 8Queen.cpp. There are no classes as the code is written using Win32
APIs.
There are two bitmaps of queens, one with white background and one with black background. In WM_CREATE
, it loads both the bitmaps using LoadBitmap
method and also saves the size of the bitmap using GetBitmapDimensionEx
. The size is taken because the queen bitmap is large and the chess board boxes are small. Now to fit the bitmap in the chess boxes, we need to adjust the size and hence we need the original size of the bitmap.
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);
The chess board data is stored in memory using a double dimension array of BOOL
. It is something like this:
BOOL **g_QueenArray;
A value of TRUE
tells that this square has queen and a value of FALSE
tells that this square is empty. Memory is allocated to the global variable.
g_QueenArray = (BOOL**)calloc(g_BoardSize, sizeof(BOOL));
for(i = 0;i < g_BoardSize;i++)
{
*(g_QueenArray + i) = (BOOL*)calloc(g_BoardSize, sizeof(BOOL));
}
A recursive backtracking function is written which keeps on calculating new positions and puts the queen on the positions. If it finds that there are no positions left on the chess board, it backtracks one row and checks for any new position for the queen. Now at this point, either it will find a new position and it will continue or else it will not find any position. If it does not find any new position, it again backtracks one row. The function returns when all the queens are placed.
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);
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;
}
The backtracking is done in a thread and the variable g_QueenArray
is updated accordingly. After updating, InvalidateRect
is called for the chess board. The WM_PAINT
calls DrawBoard()
which updates the chess board by reading g_QueenArray
. So, this way after every move which Backtracking()
calculates, the board updates itself.
case WM_PAINT:
BeginPaint(hWnd, &ps);
if(g_BoardSize)
DrawBoard(hWnd, g_BoardSize, ps, hBitmap, BitmapSize);
EndPaint(hWnd, &ps);
break;
The function DrawQueen()
is used to draw the queen on a square. It creates a region in memory using CreateCompatibleDC
and then selects the bitmap in this region using SelectObject
. Then it puts this bitmap on the chess board using StretchBlt
. The function can help in understanding how bitmaps are bitblt on a window.
short DrawQueen(HWND hWnd, PAINTSTRUCT ps, RECT rect,
HBITMAP hQueenBitmap, SIZE QueenBitmapSize)
{
if(hQueenBitmap == NULL || hWnd == NULL)
return ERROR_EXIT;
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;
}
Points of Interest
When I created the program without using the threads, it was not responding when I tried to stop it during the calculations. Whenever the window was minimized, it used to lose its interface. So I thought of putting the Backtracking
function in a thread. Now after this enhancement, the program is very responsive. It retains its interface when it is minimized and restored. So threads can be a good way to make your application responsive. There might be some bugs left in the program, but I think one can learn the basic ideas which I want to discuss.
History
- 27th August, 2008: Initial post