8Queen Problem

• Download source - 16.25 KB

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.

//load the bitmaps
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.

//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));
} 

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);
        //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;
} 

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);
    //UpdateWindow(hWnd);
            
    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;

    //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;
}

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

• 27^th August, 2008: Initial post