Placing 8 Queen's on Chess Board without killing e
Place 8 queen's on chess board with out killing each other. Apply the standard rules for Queen's movement (i.e Horzontal /Vertical /Diagonal)
this puzzle has been solved millions of times before,
There are 92 'right' ways if the goal is just to find one.
This was a question in my Analysis of Algorithms class. Forget about finding a solution, the real question is what is an efficient algorithm that will find a solution.
Here's my solution in Scheme for the n-queens problem (i.e., on any n-by-n board, what are the solutions for placing n queens on the board without killing any):
Yes there is a better way then brute force and backtracking. Create a Constraint Straint Problem (CSP) and use a forward-looking algorithm. Basically, when you create the CSP, you create all the rules for the way the queens interact, thus giving you a method to find a correct solution (pretty much the same as brut force), but by using forward checking (i.e. after you place a queen on the board in the first column, check that a queen can still be placed on the board in all the columns to the right of it (assuming you place queens in a left to right fashion), and if that world state does not have a space for a queen still in any column to the right, do not put that node-state back in the search algorithm as no solution is possible with that node). This will dramatically limit the search tree to nodes only to nodes that have possible solutions. No compilcated search algorithm is required with this type of checking, a depth-first search will work nicely as we know by the nature of the problem that all solutions are at depth 8 (or the number of queens). This is simply just a regular "stack" of nodes and very easy to implement.
I was assuming by 'brute force backtracking' that you check each successive state in a forward-looking manner and back-track as soon as you hit a dead-end. I put the word 'backtracking' in there to contrast from 'brute-force exhaustive search', which would not try to back-track but would continue setting each 8^8 combination and testing it for violation. I would assume that the algorithm "place the next queen, test for violation" would be nearly equivalent to marking and following constraints, since the cost of placing a single queen and testing only it for violation would be very cheap (I have implemented this for 8x8 and it's snappy). 40320 (8!) (much less actually because of the many illegal single queen placements before placing all 8), versus 16777216 (8^8) plus we're only checking one queen for violation per iteration versus all 8.
Fog Creek Home