Solutions to 8 Queens Problem

The 8 queens problem is a situation where we have to place 8 chess queens on an 8×8 chessboard such that no two queens attack each other i.e. no two queens should lie in the same row, same column or same diagonal.

The 8 queens puzzle is just a part of the general n-queens problem of placing n queens on an n×n chessboard.

How many unique solutions do this problem exists?
What is algorithm to find a solution to this problem?

Let's discuss.


  • simplycoder
    @AbraKadabra:If I were suppose to program for this problem, then I would opt for recursion, then try to optimize the code.
    I am unaware of the fact how good you are in coding,especially in recursion(no offense intended).
    It would be better if we can discuss more on how to code magic squares in recursion or how to find anagrams or permutation and combinations of given sequence, I think that might be a better way to start off than directly attacking n-Queens problem.
    Let me know what is your take on this, will get back to you tomorrow.
  • slinky773
    According to wikipedia, there are 4,426,165,368 ways to place 8 queens on the board, but only 92 unique solutions.

    And also according to wikipedia, this brute-force method in python should do it:

    from itertools import permutations
    n = 8
    cols = range(n)
    for vec in permutations(cols):
        if (n == len(set(vec[i]+i for i in cols))
              == len(set(vec[i]-i for i in cols))):
            print vec
    However, there are other, better ways to do this, I'm sure.
  • simplycoder
    @Slinky: I am not quiet sure about those numbers that you have posted.
    Basically this problem is included in CS courses,is to understand the concept of 'back-tracking'.
    back-tracking is where the things are carried in step by step,if at a particular point, the criteria is not met, at that step is taken aback and in its case something else is tried, if all possibilities for current node fails, then we go to its parent node and repeat the same thing.

    If members reading this thread are new to computing, I shall suggest that they take a simpler but time consuming routine which I will describe now.
    Brute-Force method:
    This method is simplest of all. In simple terms, brute force means trying out all the possibilites.
    Try placing all the queens and then check if it satisfies the criteria.Very Highy Inefficent(VHI) algorithm, but it works.(Now a days the hardware is very fast, which wasnt true in yester years).
    8x8 chess-board will have 64 squares and 8 Queens can be placed in [SUP]64[/SUP]P[SUB]8[/SUB] ways. = 178462987637760 This is a huge number. But can be done on a modern CPU with decent RAM.
    One draw back of this program is, it will keep on doing the same kinds of positions with permutation again and again.

    Now once this program is implemented, we have to ask ourselves.. "CAN I MAKE IT BETTER".
    We all know that Queens on same row will attack each other, so we can modify the algorithm in such a way that it puts the queens on different rows.
    So we can have 8[SUP]8[/SUP] = 16777216 placements in such cases. big number but then manageable, we have cut down the size of the space by whooping 99%.

    So are we satisfied with the algorithm which is faster than previous? A good programmer(who had a good sleep) will always say no.A good programer is never satisfied.
    One thing that we can do to improve the efficency is to place queen on the board using the indices of the permutations.
    there would be maximum of 8! = 40320 permutations for digits from 0..7. and reject everything that generates column,diagonal attacks.
    Now we have cut down the size of space by 99% as compared to previous.

    Further we can try to optimize the code by using early cut-offs on partial boards.
    This can be done as follows: Place one queen, place another queen,check, if they dnt attack, place third queen, check and so on. If they attack, then choose another spot. If for a particular root node, all possibilites fail, then go to its parents node and try a new position.(This is called as Back-Tracking).

    If its an even sized board, you can half the search space and multiply by 2 as there are going to be symmetries.
    -Thank you.
  • slinky773
    Well, that's just what was on wikipedia. I guess that just proves not to trust wikipedia! 😀

    And anyways, I couldn't have come up with that on my own anyways. I'm 12.

    Off topic: Is everyone in this forum NOT in the USA? Because everyone seems to post when I'm asleep. lol.

You are reading an archived discussion.

Related Posts

currently,im doing 2nd year in electrial engineering...... plz give some key areas which i need to concentrate the most and which have more scope in future thanq.... P.S: im new...
NP-hard or Non Deterministic Polynomial Time Hard problem is a situation where an algorithm that solves it can be converted to one for solving other NP-Problems. It's also written that...
CrazyEngineers Free Mock Aptitude Test - 5 On 21st August (Sunday) at 10:00 am NOTICE: You must be CrazyEngineers Forum Member to participate in test. Those who do not have...
A B+ tree or "B plus tree" is a data structure used as an index to facilitate fast access of different entries in a database. Each object/node is associated with...
If you get some news about job openings for instrumentation engineers in your city, please post it here. It will be useful for many engineers around.