Queens and Knights Problem Using Simulated Annealing

Posted on 2006-05-15
Last Modified: 2012-05-07
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.
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.

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

    Author Comment

    I see. Could you possibly add some code so as to exemplify? I have read here:
    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.

    Expert Comment

    Can anybody provide code?

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Highfive Gives IT Their Time Back

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    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 …

    759 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    13 Experts available now in Live!

    Get 1:1 Help Now