Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

8 Queens

9 views
Skip to first unread message

Johne Tsau

unread,
Nov 7, 1991, 10:59:57 PM11/7/91
to
Many pardons if this has been recently posted:

Can you place eight queens on a chessboard such that no two queens
are attacking each other?

For non-chessplayers, this means: place eight pieces on an 8 x 8 board
such that no two pieces are in the same row, column, or diagnal.

I have found two solutions myself, one of which is not symmetric. I
heard there might be more solutions though.

REQUEST : Can someone post some riddles? Those are enjoyable...

Winner of the 1991 Wrath of God Award

unread,
Nov 13, 1991, 11:28:44 AM11/13/91
to
In article <1991Nov7.2...@doug.cae.wisc.edu> ts...@cae.wisc.edu (Johne Tsau) writes:
>Can you place eight queens on a chessboard such that no two queens
>are attacking each other?

Answering just the chess-player version of this problem, sure, easily.

Make them all white queens and put them anywhere you feel like.

:)

-lightnin

Michael Sander

unread,
Nov 14, 1991, 2:29:06 PM11/14/91
to
Being a chess player myself, I felt compelled to answer this question.
Anyway, instead of 2 unique answers, I found 14! They're presented in
graph form, so that anyone can understand them without having to know
chess notation.


----1--- ----2--- ---3---- ----4--- ---5---- ---6---- ---7----
Q....... Q....... Q....... Q....... .Q...... .Q...... .Q......
..Q.... .....Q.. ......Q. ......Q. ....Q... ....Q... .....Q..
......Q .......Q ...Q.... ....Q... ......Q. ......Q. Q.......
....Q.. ..Q..... .....Q.. .......Q Q....... ...Q.... ......Q.
.Q..... ......Q. .......Q .Q...... ..Q..... Q....... ...Q....
.....Q. ...Q.... .Q...... ...Q.... .......Q .......Q .......Q
Q...... .Q...... ....Q... .....Q.. .....Q.. .....Q.. ..Q.....
..Q.... ....Q... ..Q..... ..Q..... ...Q.... ..Q..... ....Q...

---1---- ---2---- ----3--- ----4--- ----5--- ----6--- ----7--- ---8----
Q....... Q....... Q....... Q....... .Q...... .Q...... .Q...... .Q......
...Q... .....Q.. ......Q. ......Q. ....Q... ....Q... .....Q.. .....Q..
......Q .......Q ...Q.... ....Q... ......Q. ......Q. Q....... .......Q
....Q.. ..Q..... .....Q.. .......Q Q....... ...Q.... ......Q. ..Q.....
.Q..... ......Q. .......Q .Q...... ..Q..... Q....... ...Q.... Q.......
.....Q. ...Q.... .Q...... ...Q.... .......Q .......Q .......Q ...Q....
Q...... .Q...... ....Q... .....Q.. .....Q.. .....Q.. ..Q..... ......Q.
..Q.... ....Q... ..Q..... ..Q..... ..Q..... ..Q..... ....Q... ....Q...

---8---- ----9--- ---10--- ---11--- ---12--- ---13--- ---14---
Q...... .Q...... .Q...... ..Q..... ..Q..... ...Q.... ..Q.....
....Q.. ......Q. ......Q. ....Q... ....Q... .....Q.. ......Q.
......Q ..Q..... ....Q... .Q...... .......Q .......Q .Q......
.Q..... .....Q.. .......Q .......Q ...Q.... Q....... .......Q
Q....... .......Q Q....... Q....... Q....... ....Q... ....Q...
..Q.... ....Q... ...Q.... ......Q. ......Q. ......Q. Q.......
.....Q. Q....... .....Q.. ...Q.... .Q...... .Q...... ...Q....
...Q... ...Q.... ..Q..... .....Q.. .....Q.. ...Q.... .....Q..

I believe (and hope) that these are all the answers, and that there are
no typing errors. The only problem may be readability-but it was either
this way or have a longer note. If it's really needed, I (guess I) could
type the boards with more spacing.

Mike Sander
344LWKC%CMUVM....@CUNYVM.CUNY.EDU

Rolf Wilson

unread,
Nov 15, 1991, 9:27:24 AM11/15/91
to
This is an old problem, and should be in the FAQ if it is not. There
are 92 solutions, of which 12 are unique once you consider rotations
and reflections. Finding the 92 solutions is given as a programming
example in "Algorithms + Structures = Programs".
--

Rolf Wilson Illinois State Geological Survey ro...@sparc1.isgs.uiuc.edu

Dave Seaman

unread,
Nov 15, 1991, 10:05:29 AM11/15/91
to
In article <91318.142...@CMUVM.BITNET> 344...@CMUVM.BITNET (Michael Sander) writes:
>Being a chess player myself, I felt compelled to answer this question.
>Anyway, instead of 2 unique answers, I found 14! They're presented in
>graph form, so that anyone can understand them without having to know
>chess notation.

Given one solution to the puzzle, you can produce as many as eight by
considering all the reflections and rotations of the original solution. The
puzzle actually has 12 solutions that are truly different, but 92 solutions if
you don't pay attention to reflections and rotations (11 of the 12 have eight
variations; one has only four because of symmetry about the center).

--
Dave Seaman
a...@seaman.cc.purdue.edu

Redmond English

unread,
Nov 15, 1991, 10:39:39 PM11/15/91
to
In article <91318.142...@CMUVM.BITNET> 344...@CMUVM.BITNET (Michael Sander) writes:
>Being a chess player myself, I felt compelled to answer this question.
>Anyway, instead of 2 unique answers, I found 14! They're presented in
>graph form, so that anyone can understand them without having to know
>chess notation.
>
[SOLUTIONS DELETED]

>
>I believe (and hope) that these are all the answers, and that there are
>no typing errors. The only problem may be readability-but it was either
>this way or have a longer note. If it's really needed, I (guess I) could
>type the boards with more spacing.
>
>Mike Sander


Sorry about posting, but I tried to e-mail, and it bounced.

I wrote a little C program a while ago, which after exhaustively testing
every position with exactly one queen on each rank (taking about 1 minute
on an 8MHz 68000 machine), came up with 92 solutions.

Red/.

Tony Lezard

unread,
Nov 18, 1991, 1:47:49 PM11/18/91
to
redm...@cs.cmu.edu (Redmond English) writes:

> I wrote a little C program a while ago, which after exhaustively testing
> every position with exactly one queen on each rank (taking about 1 minute
> on an 8MHz 68000 machine), came up with 92 solutions.

Erk. Exhaustive testing? Count me out on that. The following program,
written in ANSI C, uses a backtracking algorithm and gives the correct
answer instantaneously:

#include <stdio.h>

void try(int, int, int);
static int count = 0;

void main() {
try(0,0,0);
printf("There are %d solutions.\n", count);
}

void try(int row, int left, int right) {
int poss, place;
if (row == 0xFF) ++count;
else {
poss = ~(row|left|right) & 0xFF;
while (poss != 0) {
place = poss & -poss;
try(row|place, (left|place)<<1, (right|place)>>1);
poss &= ~place;
}
}
}


ObPuzzle: Generalize the above to n queens.

--
Tony Lezard IS to...@mantis.co.uk OR tony%mantis...@uknet.ac.uk
OR EVEN ar...@phx.cam.ac.uk if all else fails. Great! Kept my .sig down to two
lines!

0 new messages