12,824,299 members (43,301 online)
alternative version

#### Stats

70.8K views
12 bookmarked
Posted 4 Oct 2005

# Graphical solution to eight queen problem

, 4 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...

 First Prev Next
 only 91 Member 96797928-Oct-14 3:21 Member 9679792 8-Oct-14 3:21
 Regarding the algorithm PIEBALDconsult30-Dec-11 10:20 PIEBALDconsult 30-Dec-11 10:20
 How about FINISHING the project? fwsouthern4-Oct-05 17:53 fwsouthern 4-Oct-05 17:53
 Re: How about FINISHING the project? SandyWhite904-Oct-05 18:33 SandyWhite90 4-Oct-05 18:33
 Re: How about FINISHING the project? SChat4-Oct-05 19:13 SChat 4-Oct-05 19:13
 Definitely there are 12 unique solutions.....but I never intended to show them distinctively.....may be sometimes later I will incorporate that. As I mentioned there are many optimizations to the algorithm and I have used perhaps the easiest one. Now about submitting the code in Java....does the language actually matters today?
 Re: How about FINISHING the project? fwsouthern5-Oct-05 18:59 fwsouthern 5-Oct-05 18:59
 Re: How about FINISHING the project? SChat5-Oct-05 19:16 SChat 5-Oct-05 19:16
 Last Visit: 31-Dec-99 19:00     Last Update: 27-Mar-17 20:41 Refresh 1

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

Web02 | 2.8.170308.1 | Last Updated 4 Oct 2005