Solutions to 8 Queens Problem

Replies

• 

  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.
  so "CAN I MAKE IT BETTER"
  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.
  CAN THIS BE MADE ANY BETTER??
  -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.