## 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.