13,196,946 members (73,633 online)
alternative version

#### Stats

72.6K views
12 bookmarked
Posted 3 Oct 2005

# Graphical solution to eight queen problem

, 3 Oct 2005
 Rate this:
Provides a graphical solution to eight queen problem

## Introduction

Eight queen problem is one of those many classical problems that has aroused interests of many. The problem is to place 8 non-attacking queens on the chess board. There are various algorithms proposed of which Writh's algorithm is perhaps the best (taking into account its time complexity). In my application, however, I have used the old algorithm from Horowitz-Sahani. The difference in time complexity is not very great in case of the two algorithms, at least when the purpose of the application is to present a graphical solution to the user. This application is inspired from the article of Timothy Rolfe published in Dr. Dobb's Journal. Anyone interested in the study of the algorithms in detail can have a look at the article.

## The Algorithm

For solving this problem, an integer array is used such that each element of the array will represent a row on the board. For e.g. board[0] will represent the 0th row (i.e. the first row) on the board. The value of each array element will represent the column where the queen can be placed. For e.g. board[2] = 6 signifies the queen is placed at 3rd row 7th column. The advantage of such an arrangement is obvious. At once, you can check for an attack vertically. For this you just need to check for duplicate values in the array. If board[2] = board[6], then the queens at 3rd row and 7th row, are both in the same column. The checking for diagonal attack is a little bit tricky. For e.g. board[0]=0 and board[4]=1. This position is obviously not valid as there is a diagonal attack. The following
code snippet check for that:

```  for (int i = 0; i < row; i++) {<BR>   if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) {<BR>    return false;<BR>   }<BR>  }
<P></P>```

Here row = 1. The fist condition checks for vertical attack and is definitely false. The second condition which checks for diagonal attack evaluates true. The point is to check each column of the last row (where the queen should be placed) and see whether `Math.abs(board[row] - board[i]) == (row - i) `satisfies or not. If satisfies, then there must be a diagonal attack and hence backtrack. The rest of the algorithm is pretty simple. Start by trying to place the queen in the first row, first column. Then start placing one queen per row, in such a position that there is no attack. If you can't find any such position in a particular row, then the positioning of the queen in the earlier row must have been wrong. Hence backtrack to find a new position for the queen.

## The Application

The application, although a single file, have four classes.
EightQueenFrame
EightQueen
MyCanvas
Solution
It displays all the 92 solutions. The user can navigate through different solutions by pressing the up and down arrow. The EightQueen is the class responsible for implementing the algorithm. The class can solve the problem of N queen, the argument in the constructor controlling the size. However the graphics solution is for 8 queen only. Hence the argument in the constructor of the class is 8. The Solution class wraps each board configuration. The solutions are added to an Arraylist to facilitate navigation through solutions. The EightQueenFrame is the main class responsible for drawing. It captures the keystroke for navigation purpose.

A list of licenses authors might use can be found here

## Share

 Web Developer India
No Biography provided

## You may also be interested in...

 Pro Pro

 First Prev Next
 only 91 Member 96797928-Oct-14 2:21 Member 9679792 8-Oct-14 2:21
 Regarding the algorithm PIEBALDconsult30-Dec-11 9:20 PIEBALDconsult 30-Dec-11 9:20
 How about FINISHING the project? fwsouthern4-Oct-05 16:53 fwsouthern 4-Oct-05 16:53
 You stopped at the sophomore level -- 92 solutions is the WRONG answer -- you should be looking for the unique solutions of which there are only 12. Your code is incomplete as it does not compare solutions for duplicates -- you need to include mirroring and rotation of the board to determine if a solution is in fact unique. Now about submitting the code in Java .....
 Re: How about FINISHING the project? SandyWhite904-Oct-05 17:33 SandyWhite90 4-Oct-05 17:33
 Re: How about FINISHING the project? SChat4-Oct-05 18:13 SChat 4-Oct-05 18:13
 Re: How about FINISHING the project? fwsouthern5-Oct-05 17:59 fwsouthern 5-Oct-05 17:59
 Re: How about FINISHING the project? SChat5-Oct-05 18:16 SChat 5-Oct-05 18:16