Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

Queens and Knights Problem Using Simulated Annealing

Posted on 2006-05-15
Medium Priority
504 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
• 2
• 2

LVL 85

Accepted Solution

ozo earned 1500 total points
ID: 16685045
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

ID: 16685316
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 85

Expert Comment

ID: 16685566
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

ID: 16685652
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

ID: 26140616
Can anybody provide code?
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn different types of Android Layout and some basics of an Android App.
No other job is as rewarding and demanding as building an iPhone app is. It is not really in the hands of the developer for the success of an iPhone app. Many factors operate jointly for every iOS application's success in the market.
Introduction to Processes
Starting up a Project
Suggested Courses
Course of the Month14 days, 17 hours left to enroll