12,951,983 members (64,969 online)
alternative version

Stats

33.2K views
17 bookmarked
Posted 26 Aug 2008

8Queen Problem

, 26 Aug 2008 GPL3
 Rate this:
Tries to solve the queen problem using backtracking

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
MAKEINTRESOURCE(IDB_BITMAP1));

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;

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

Share

 Software Developer (Senior) FIS India
No Biography provided

You may also be interested in...

 First Prev Next
 Same without threading [modified] Guillaume Geffard27-Aug-08 4:17 Guillaume Geffard 27-Aug-08 4:17
 Re: Same without threading bling27-Aug-08 5:26 bling 27-Aug-08 5:26
 Re: Same without threading Guillaume Geffard27-Aug-08 6:00 Guillaume Geffard 27-Aug-08 6:00
 Re: Same without threading ima_c++_programmer28-Aug-08 20:45 ima_c++_programmer 28-Aug-08 20:45
 Re: Same without threading ima_c++_programmer28-Aug-08 21:04 ima_c++_programmer 28-Aug-08 21:04
 Re: Same without threading Philippe Mori15-Dec-12 13:05 Philippe Mori 15-Dec-12 13:05
 Last Visit: 31-Dec-99 18:00     Last Update: 26-May-17 11:26 Refresh 1