使用 DFS 和 BFS 解决 N 皇后问题并在控件面板上显示目标

• 下载 N-Queen by BFS with show detail Steps - 66.5 KB
• 下载 N-Queen by DFS - 100.1 KB

引言

N 皇后问题是一个经典的难题，常用于讨论各种搜索策略。该问题通常定义在标准的 8x8 棋盘上，但也可以定义在任何 NxN 的棋盘上，并且对于 N ≥ 4 的情况都有解。

本文尝试使用深度优先搜索 (DFS) 算法解决 N 皇后问题，并在棋盘上直观地显示结果。

背景

正如所有这类问题一样，8 皇后问题被用作讨论搜索方法的示例，而不是一个本身有价值的问题。说实话，我们甚至没有八个皇后，为什么要担心如何摆放她们呢？

一般来说，问题是将皇后放置在棋盘上，使得任意两个皇后都不能互相攻击。解决问题的方法取决于对国际象棋中皇后移动规则的了解。具体来说，皇后可以沿着任何直线移动，无论是沿着行、列还是对角线。在 NxN 的棋盘上，每个皇后将位于恰好一行、一列和两条对角线上。

要求任意两个皇后不能放置在同一行，将 NxN 棋盘上可以放置的皇后数量限制为 N。因此，标准的 8x8 棋盘最多可以放置八个皇后。问题在于找到一种允许放置 N 个皇后的排列。

DFS 或深度优先搜索是一种搜索算法，它从树根到子树进行搜索，在达到非预期状态时从子树递归返回，或在找到目标时停止搜索。

DFS (input state)
{
 1- Check goal state
 2- Check problem conditions
 3-build new state and call recursive function with new states and get result
}

使用代码

首先，为了管理棋盘，创建一个 Board 类。

属性

N 属性用于表示尝试放置的皇后数量。每一行只能放置一个皇后，因此为了保存皇后的位置，我们必须知道它们在每一行中的列号。 board 向量有 N 个单元格用于保存棋盘中的皇后位置，在放置每个皇后后，我们必须保存放置在棋盘中的皇后数量，cnt 属性就是为此目的。

Board 类的属性

public int N;
int[] board;
public int cnt;

Board 类构造函数：

此方法用于初始化 Board 类的属性。

public Board(int n)
{
    N = n;
    board = new int[N];
    for (int i = 0; i < N; i++)
        board[i] = 0;
    cnt = 0;
}

bool isSafe(int Clm)

在放置下一个皇后之前，我们必须检查攻击限制。

当两个皇后在同一列或同一对角线（皇后在国际象棋游戏中移动）上时，它们可以互相攻击。以下方法检查新放置的皇后在 Clm 列号处是否攻击到之前的皇后（返回 true）或者不（返回 false）。

public bool isSafe(int Clm)
{
    for (int i = 0; i < cnt; i++)
    {

        if ((board[i] == Clm) || Math.Abs(Clm - board[i]) == (cnt - i)) 
            return false;
    }
    return true;
}

void Place(int Clm) 方法：

在 Clm 列号处放置下一个皇后。

public void Place(int Clm)
{
    if (Clm >= 0 && Clm < N)
    {
        board[cnt] = Clm;
        cnt++;
    }
    else
    {
        MessageBox.Show("Bad Column");
    }
}

bool IsGoal() 方法

如果放置在棋盘上的皇后数量等于 N，则表示已达到目标状态。

public bool IsGoal()
{
    if (cnt == N)
    {
        return true;
    }
    else
        return false;
}

void UnPlace() 方法

Board 类用于控制递归和从棋盘向量中获取最后一个皇后，调用此方法，通过将 cnt 属性减一即可实现。

public void UnPlace()
{
    if (cnt > 0)
    {
        cnt--;
    }
}

void ShowBoard(Panel pnl) 方法

此方法用于在输入的 Panel 控件上直观地显示棋盘。

NxN 棋盘格的宽度和高度通过将宽度和高度分成 N 段来计算（宽度除以 N 作为长度，高度除以 N 作为高度）。每个单元格都是一个 PictureBox 控件，其 BackColor 为白色或黑色。构建棋盘后，为了在棋盘上放置皇后，加载皇后图片并设置必要的 PictureBox 属性：

public void ShowBoard(Panel pnl)
{
    pnl.Controls.Clear();
    PictureBox[,] chess = new PictureBox[N, N];
    int w = 0, h = 0;
    w = pnl.Width;
    h = pnl.Height;
    int xs = (int) ((double)w / (double)N);
    int ys = (int)((double)h / (double)N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            chess[i, j] = new PictureBox();
            chess[i, j].BorderStyle = BorderStyle.FixedSingle;
            chess[i, j].Parent = pnl;
            chess[i, j].Location = new Point(j * xs + 1, i * ys + 1);
            chess[i, j].Size = new Size(xs, ys);
            if ((i + j) % 2 == 0)
                chess[i, j].BackColor = Color.White;
            else
                chess[i, j].BackColor = Color.Black;
        }
    for (int i = 0; i < cnt; i++)
    {
        chess[i, board[i]].Load(Application.StartupPath+"\\queen.jpg");
        chess[i, board[i]].SizeMode = PictureBoxSizeMode.StretchImage;
    }
}

重要的窗体方法

void btnSolve_Click(object sender, EventArgs e) 方法

此方法具有前端事件，用于获取输入并开始构建初始棋盘，然后调用递归方法 DFS 来解决问题。使用 System.Diagnostics.Stopwatch 类来测量时间。

private void btnSolve_Click(object sender, EventArgs e)
{
    try
    {
        pnlChess.Controls.Clear();
        if (txtN.Text != "")
        {
            int N = int.Parse(txtN.Text);
            Board board = new Board(N);
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            lblTime.Text = "";
            sw.Start();
            Board res = DFS(board);
            sw.Stop();
            lblTime.Text = sw.ElapsedMilliseconds.ToString()+"  MilliSecond";
            if ( res!= null)
            {
                res.ShowBoard(pnlChess);
            }
            else
            {
                MessageBox.Show("no Result");
            }
        }
    }
    catch
    {

    }
}

Board DFS(Board board) 方法：

此方法是解决 N 皇后问题的管理器方法，它实现 DFS 算法来找到目标状态。用一个空的棋盘（皇后数量=0）调用此方法。

DFS 方法体步骤

1. 如果当前状态是目标状态，则返回 Board。
2. 从列号零 (0) 到 N-1，检查是否是放置下一个皇后的安全位置，在該列放置下一个皇后，并为新状态调用 DFS 方法。
3. 如果从上一次调用返回的 Board 不是 null，则表示已找到目标状态，当前函数也返回该状态；否则，撤销放置最后一个皇后，并检查该行中的其他列。

Board DFS(Board board)
{
    if (board.IsGoal() == true)
    {
        return board;
    }
    else
    {
        for (int i = 0; i < board.N; i++)
        {
            if (board.isSafe(i))
            {
                board.Place(i);
                Board res= DFS(board);
                if (res != null)
                    return res;
                board.UnPlace();
            }
        }

    }
    return null;
}

在下载部分，提供了两种 N 皇后问题的实现：一种是使用 DFS 一次性显示最终目标状态，另一种是使用计时器和队列类通过 BFS 分步显示。

关注点

构建一个游戏，在特定时间内在棋盘上放置 N 个皇后。

历史

此代码实现于 2011 年。

参考文献

• N 皇后问题定义
• 维基百科上的 DFS