8 皇后问题

• 下载源代码 - 16.25 KB

引言

8Queen 程序试图解决著名的国际象棋皇后问题。我开始编写这个程序只是为了练习。完成之后，我想把它上传到 Code Project。这是我的第一个程序。我从 Code Project 学到了很多，因此想贡献一些东西，以便其他人可以使用此代码并学习一些东西。

该程序可以解决 n = 5 到 n = 15 的皇后问题。虽然它能够解决 'n' 的任何值的问题，但我采用了 15 的上限范围。它可以成为学习基本递归，在界面上进行位图打印以及一点多线程的一个很好的例子。

背景

大多数程序员肯定都知道国际象棋皇后问题，因为这是数据结构课程中的一个著名问题。我们必须将 'n' 个皇后放在 n X n 的棋盘上，使得每个皇后都是安全的。国际象棋中的皇后可以水平，垂直和对角线移动到任何长度。因此，皇后的放置方式应使其不阻碍其他皇后。因此，想法是自动将皇后放在棋盘上。

Using the Code

该代码非常易于使用和理解。只有一个重要的文件，8Queen.cpp。由于代码是使用 Win32 API 编写的，因此没有类。

有两个皇后的位图，一个带有白色背景，一个带有黑色背景。在 WM_CREATE 中，它使用 LoadBitmap 方法加载两个位图，并使用 GetBitmapDimensionEx 保存位图的大小。之所以获取该大小，是因为皇后位图很大，而棋盘方格很小。现在，要将位图放入棋盘方格中，我们需要调整大小，因此我们需要位图的原始大小。

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

棋盘数据使用 BOOL 的二维数组存储在内存中。它看起来像这样

BOOL **g_QueenArray; 

TRUE 值表示该方格有皇后，FALSE 值表示该方格为空。内存已分配给全局变量。

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

编写了一个递归回溯函数，该函数不断计算新位置并将皇后放在这些位置上。如果发现棋盘上没有剩余位置，它将回溯一行并检查皇后是否有任何新位置。现在，在这一点上，它要么会找到一个新位置并继续前进，要么找不到任何位置。如果找不到任何新位置，它将再次回溯一行。当所有皇后都放置好时，该函数返回。

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

回溯在一个线程中完成，并且相应地更新变量 g_QueenArray 。更新后，为棋盘调用 InvalidateRect 。WM_PAINT 调用 DrawBoard()，后者通过读取 g_QueenArray 来更新棋盘。因此，通过这种方式，在 Backtracking() 计算的每次移动之后，棋盘都会自行更新。

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

函数 DrawQueen() 用于在正方形上绘制皇后。它使用 CreateCompatibleDC 在内存中创建一个区域，然后使用 SelectObject 在该区域中选择位图。然后，它使用 StretchBlt 将此位图放置在棋盘上。该函数可以帮助理解如何在窗口上 bitblt 位图。

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

关注点

当我创建程序而没有使用线程时，当我想在计算过程中停止它时，它没有响应。每当窗口最小化时，它都会丢失其界面。因此，我考虑将 Backtracking 函数放入线程中。现在，经过此增强之后，该程序非常灵敏。当最小化并恢复时，它会保留其界面。因此，线程可能是使您的应用程序响应更快的好方法。程序中可能还存在一些错误，但是我认为可以学习我想讨论的基本思想。

历史

• 2008 年 8 月 27 日：初始发布