Solved

# Queens and Knights Problem Using Simulated Annealing

Posted on 2006-05-15
480 Views
Hello all.
I have to provide a solution to the following problem using simulated annealing:
I must place an equal number of knights and queens on a chessboard such that no piece attacks any other piece. And I need to determine the maximum number of pieces I can place on the board + how many different ways I can do it (printing the board for each discovered solution).
My experience in this field of heuristics is relatively reduced and any help you can provide regarding the data structures required to store the solution plus a way of actually solving the problem would be very much welcome.
Many thanks.
0
Question by:nicolae_velciov

LVL 84

Accepted Solution

Simulated annealing may not be the best method for finding the how many different ways you  can do something.
It looks like 5 is possible and 6 is not,
but to discover that with simulated annealing you may want a data structure that lets you add and remove queens and knights, with a high cost for removing them.
0

Author Comment

Thank you for your answer. I am no expert in heuristics. So pretty much the question is: would there actually be an heuristic approach to solve this problem in an efficient way?
If I need to ask this question separately (so that you may get the points for it) please tell me. I'm new and this problem is very urgent for me.
Thank you again.
0

LVL 84

Expert Comment

simulated annealing uses a heuristic representing a cost that it seeks to minimize.
in this problem, the cost might be the number of attacks and the number of queens and knights short of the maximum.
0

Author Comment

I see. Could you possibly add some code so as to exemplify? I have read here: http://www.vector.org.uk/archive/v213/hui213.htm
that on a 8 x 8 board a maximum of 5 queens and 5 knights can be placed. Could you please provide some code (preferably in C/C++) so as to solve this particular problem (of Q and K placement) for this particular board size using SA?
Thank you.
0

Expert Comment

Can anybody provide code?
0

## Featured Post

### Suggested Solutions

This article is filled with multiple code samples and explanations for mathematical calculations. They are as follows: 1. General tips 2. Quadratic formula 3. Object collision 4. Projectile path General Tips       Here are some of my tips f…
Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

#### Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!