Fog Creek Software
Discussion Board




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)

Sanjeev Jahagirdar
Friday, July 12, 2002

this puzzle has been solved millions of times before,
but heres my go:

mm#mmmmm
mmmmm#mm
mmmmmmm#
#mmmmmmm
mmmm#mmm
mmmmmm#m
m#mmmmmm
mmm#mmmm

is there a right way to do this rather than guessing?

Cheradenine Zakalwe
Friday, July 12, 2002

There are 92 'right' ways if the goal is just to find one.
With symmetry, there are only 8 unique solutions.  I have a couple of favorites that are 'pretty':

mm#mmmmm
mmmm#mmm
m#mmmmmm
mmmmmmm#
#mmmmmmm
mmmmmm#m
mmm#mmmm
mmmmm#mm

and:

mmm#mmmm
mmmmm#mm
mm#mmmmm
mmmm#mmm
m#mmmmmm
mmmmmmm#
#mmmmmmm
mmmmmm#m

These are probably hard to stumble upon in an interview question - in fact I don't think I would expect anyone to find one except to mention that it might be possible.  I don't know, is there a better way to solve this that brute force backtracking?  Anyone?
I guess you could have them write code to solve it...

Paul Johnston
Saturday, July 13, 2002

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.

Number the squares sequentially starting in the upper left corner and proceed row by row.

Simply attempting every possible combination of 8 queens is horribly inefficient.  You know 1, 2, 3, 4, 5, 6, 7, 8 is not a solution.  As soon as you place a queen in the first square you've taken a row, column and diagonal out of the board.  You can exclude those as you place the remaining queens.

An efficient algorithm will place the first queen in square 1, cross out the appropriate rows, columns and diagonals, then place the next queen in the next available square (11).  If you run out of squares, then start over by moving the first queen from 1 to 2.  The next queen will go in 12 and so on.  This is an o(n) algorithm isn't it?  Trying every combination is o(n^2), I think.

Our prof. then arbitrarilly decided to try placing something like 16 queens in an 8x8x8 cube imagining that queens could move in 20 directions.  We wasted a lot of MIPS on a Sun to figure out that it couldn't be done.  Which begs the question, what is the most number of queens you can fit into a cube?

William Frantz
Tuesday, July 23, 2002

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):

http://www.codeexamples.org/cgi-bin/c2h/hl.cgi?filename=queens.lisp&type=HTML-detail

Note that the formatting is slightly fubar'ed and that the (define lines are placed one line up for some reason.

Daniel DiPaolo
Wednesday, July 24, 2002

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.

Brian Summers
Wednesday, July 24, 2002

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.

The constraint approach does not seem to be much different, although may be more generally applicable to other problems...?

Paul Johnston
Wednesday, July 31, 2002

*  Recent Topics

*  Fog Creek Home