13,090,426 members (49,477 online)
Add your own
alternative version

Stats

47.4K views
2.2K downloads
29 bookmarked
Posted 4 Jan 2009

Eight Queens Problem using VB.NET

, 4 Jan 2009
 Rate this:
Please Sign up or sign in to vote.
Backtracking solution approach to solve the eight queens problems and get all unique solutions

Introduction

The Eight Queens Problem is a famous problem in AI field and a famous example about AI algorithms used to solve such a problem using backtracking method.

Background

The solution shows all unique solutions to the eight queens problem which are exactly 92 solutions, 12 of which are distinct. The application also allows you to play the game yourself and try to find your own solution. The algorithm uses backtracking and depth first limited search to level 8 (8 queens) to find a solution.

Using the Code

The `Queen `class is the basic object used in the algorithm and all over the project for graphics display too. It's fairly simple:

```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	```

The `ChessBoard `user control draws the board and is actually where the algorithm of finding all solutions takes place. The function of interest is the `MoveQueen `function which moves a queen across the board, then checks if the new position is a good place or that the queen is attacked. The process is repeated recursively until all 8 queens are placed in a safe place.

```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
```

Finally, a call to `GetSolutions `will initiate the `MoveQueen `function starting from the first level, which is the depth of the current position in the depth tree. Reaching a level of 8 means we have found a solution. Otherwise, 1 level is decremented to the previous level and the search continues using different values. This process is called Backtracking.

```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
```

Points of Interest

What's interesting here is that the solutions are ordered according to the board from top-left to bottom-right so you can have all solutions by repeating click on solve button.

History

• 4th January, 2009: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

 Software Developer (Senior) Microgen Lebanon
For more articles and extreme topics please check out my personal website www.alitarhini.com

You may also be interested in...

 Pro Pro

Comments and Discussions

 First Prev Next
 ur coding is very well ganeskumar27-Jul-09 22:30 ganeskumar 27-Jul-09 22:30
 Good start... Dave Kreskowiak8-Jan-09 8:44 Dave Kreskowiak 8-Jan-09 8:44
 very interesting abou lwiss7-Jan-09 10:20 abou lwiss 7-Jan-09 10:20
 The code is nice, but the article needs...well...text Shane Story6-Jan-09 3:13 Shane Story 6-Jan-09 3:13
 Explanation Baconbutty5-Jan-09 21:23 Baconbutty 5-Jan-09 21:23
 Re: Explanation Invisionsoft6-Jan-09 6:52 Invisionsoft 6-Jan-09 6:52
 great article EngForce4-Jan-09 13:39 EngForce 4-Jan-09 13:39
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Aug-17 14:39 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170813.1 | Last Updated 4 Jan 2009
Article Copyright 2009 by Ali Tarhini
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid