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...
Answering just the chess-player version of this problem, sure, easily.
Make them all white queens and put them anywhere you feel like.
:)
-lightnin
----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 Illinois State Geological Survey ro...@sparc1.isgs.uiuc.edu
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
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/.
> 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!