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 example, board[0]=0 and board[4]=1. This position is obviously not valid as there is a diagonal attack. The following code snippet checks for that:
for (int i = 0; i < row; i++) {
if ((board[i] == board[row]) || Math.abs(board[row] - board[i]) == (row - i)) {
return false;
}
}
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, has four classes:
EightQueenFrameEightQueenMyCanvasSolution
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 purposes.
History
- 4th October, 2005: Initial version
License
This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below.
A list of licenses authors might use can be found here.
