使用 VB.NET 的八皇后问题

• 下载源代码 - 44.96 KB

引言

八皇后问题是人工智能领域的一个著名问题，也是一个关于使用回溯法解决此类问题的 AI 算法的著名例子。

背景

该解决方案显示了八皇后问题的所有唯一解，总共有 92 个解，其中 12 个是不同的。该应用程序还允许您自己玩游戏并尝试找到自己的解决方案。该算法使用回溯和深度优先有限搜索，深度为 8（8 个皇后）来找到解决方案。

Using the Code

Queen 类是算法中使用的基本对象，并且在整个项目中也用于图形显示。它非常简单。

Public Class Queen
    Private mRow As Integer
    Private mColumn As Integer

    Public Sub New()
        mRow = 0
        mColumn = 0
    End Sub

    Public Sub New(ByVal Row As Byte, ByVal Column As Byte)
        mRow = Row
        mColumn = Column
    End Sub

    Public Property Row() As Integer
        Get
            Return mRow
        End Get
        Set(ByVal value As Integer)
            mRow = value
        End Set
    End Property

    Public Property Column() As Integer
        Get
            Return mColumn
        End Get
        Set(ByVal value As Integer)
            mColumn = value
        End Set
    End Property
End Class	

ChessBoard 用户控件绘制棋盘，实际上是寻找所有解决方案的算法发生的地方。感兴趣的函数是 MoveQueen 函数，它将一个皇后在棋盘上移动，然后检查新位置是否是一个好的位置，或者该皇后是否受到攻击。该过程递归重复，直到所有 8 个皇后都放置在安全的位置。

    Private Sub MoveQueen(ByVal Level As Integer)
        If Level > 7 Then
            For j As Integer = 0 To 7
                For i As Integer = 0 To 7
                    If (Queens(j).Row = j) And (Queens(j).Column = i) Then
                        mCells(i, j) = True
                    Else
                        mCells(i, j) = False
                    End If
                Next
            Next
            Solutions.Add(mCells.Clone)
            Exit Sub
        End If
        For j As Integer = 0 To 7
            If Level < 8 Then
                Queens(Level).Row = Level
                Queens(Level).Column = j
                If CheckAll(Level) Then MoveQueen(Level + 1)
            End If
        Next
    End Sub	 

最后，调用 GetSolutions 将从第一层开始启动 MoveQueen 函数，即深度树中当前位置的深度。达到第 8 层意味着我们找到了一个解决方案。否则，将 1 层递减到上一层，并继续使用不同的值进行搜索。这个过程称为回溯。

    Public Sub GetSolutions()
        mUserPlay = False
        Playing = False
        Queens.Clear()
        ResetCells()
        DrawBoard()
        For j As Integer = 0 To 7
            Queens.Add(New Queen)
        Next
        For i As Integer = 0 To 7
            Queens(0).Row = 0
            Queens(0).Column = i
            MoveQueen(1)
        Next
    End Sub 

兴趣点 

有趣的是，这些解决方案是按照从左上到右下的棋盘顺序排列的，因此您可以重复点击“解决”按钮来获得所有解决方案。

历史

• 2009年1月4日：初始发布