Reader Level:
ARTICLE

Eight queens puzzle and its solution using C#.Net

Posted by Purushottam Rathore Articles | Visual C# January 23, 2009
In this article I am going to describe about Eight queens puzzle. and how to solve this puzzle.
  • 1
  • 0
  • 42378
Download Files:
 

What is Eight queens puzzle?

The eight queens puzzle is the problem of putting eight chess queens on an 8x8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an nxn chessboard, where solutions exist only for n = 1 or n >= 4.

Figure 1: 8x8 chessboard for 8 queen problem.

Solution of this problem:

Place eight queens on the chessboard such that no queen attacks any other one. A mouseclick on any empty field of the chessboard puts a queen into this field.

You can solve This puzzle by using Backtracking algorithm. Backtracking is a process where steps are taken towards the final solution and the details are recorded. If these steps do not lead to a solution some or all of them may have to be retraced and the relevant details discarded. In theses circumstances it is often necessary to search through a large number of possible situations in search of feasible solutions. This trial and error process is illustrated here by a discussion of a particular problem, that of the eight queens.

In the Eight Queens problem the challenge is to place eight queens pieces from the game of Chess on a chessboard so that no queen piece is threatening another queen on the board.  In the game of chess the queen is a powerful piece and has the ability to attack any other playing piece positioned anywhere else on the same row, column, or diagonals. This makes the challenge quite tricky for humans who often declare after several failed attempts "there can't be any solution!".

However There are 92 possible ways of arranging Eight Queens on an 8 x 8 ChessBoard such that none of them attacks another. Actually, the number of unique ways in 12, but by reflection/rotation/inversion, we get 92 possiblecases. A lot of the solutions are mirror images of each other.

All of the solutions can be found using a recursive backtracking algorithm. The algorithm works by placing queens on various positions, adding one at a time until either eight queens have been placed on the chess board or less than eight queens are on the board but there are no more safe positions left on the board. When the latter situation is reached the algorithm backtracks and tries another layout of queens.

Code to solve this Puzzle:

Step 1: First off all Create Open new project. Pick one panel, one button and one label on the form.

Step 2: Create the class for ChessBoard (See in the attechment).

Step 3: Crete the class for queens (See in the attechment).

Step 4: Write the following line of code on the form load.

private void Form1_Load(object sender, System.EventArgs e)
{
    this.Show();
    MessageBox.Show("Add 8 queens to the board so that no queen attacks the other");
    cb.Dock =
DockStyle.Fill;
    cb.GetSolutions();
    Panel1.Controls.Add(cb);
    Button1.BringToFront();
}

Step 5: Write the following line of code on the Button click event. this code is used to solve the puzzle.

private void Button1_Click(object sender, System.EventArgs e)
{
    Label1.Visible =
true;
    if (i < cb.Solutions.Count)
    {
        cb.Cells = cb.Solutions[i];
        cb.DrawBoard();
        i += 1;
    }
    else
    {
        i = 0;
    }
}

Step 6: Now debug the application.

 

Figure 2: 8x8 chessboard.

Step 7: Now mouseclick on any empty field of the chessboard to puts a queen into this field.

Figure 3: Yellow queens are placed on proper place rather red_blue queen is not.

If you are not eligible to solve this puzzle then click on solve button you will get 92 solutions and 12 distinct solutions like as follows:

Click on solve button to find new solution again and again up to 92 solutions.

COMMENT USING

Trending up