Click here to Skip to main content
Click here to Skip to main content

Graphical solution to eight queen problem

, 3 Oct 2005
Rate this:
Please Sign up or sign in to vote.
Provides a graphical solution to eight queen problem

Sample Image - EightQueen.jpg

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++) {
   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, 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.

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

About the Author

SChat
Web Developer
India India
No Biography provided

Comments and Discussions

 
QuestionRegarding the algorithm [modified] PinmemberPIEBALDconsult30-Dec-11 9:20 
QuestionHow about FINISHING the project? Pinmemberfwsouthern4-Oct-05 16:53 
AnswerRe: How about FINISHING the project? PinmemberSandyWhite904-Oct-05 17:33 
AnswerRe: How about FINISHING the project? PinmemberSChat4-Oct-05 18:13 
GeneralRe: How about FINISHING the project? Pinmemberfwsouthern5-Oct-05 17:59 
GeneralRe: How about FINISHING the project? PinmemberSChat5-Oct-05 18:16 
GeneralRe: How about FINISHING the project? Pinmembersadatisaeedeh12-Mar-11 1:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140721.1 | Last Updated 4 Oct 2005
Article Copyright 2005 by SChat
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid