From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Newsgroups: rec.puzzles
Subject: Re: 8-queen problems (revisited?)
Date: 17 Dec 92 09:01:22 GMT
Organization: McGill Research Centre for Intelligent Machines

In article <BzAJMJ.DB2@unccsun.uncc.edu>, sbardhan@uncc.edu (Soumendu Bardhan) writes:

> The eight Queen Problem:

> Arrange eight queens in a chess board such that no queen attacks
> another queen

> It is a still a unsolved problem .

Huh?  It's been completely solved.  You even say you've solved it (and
give a solution count that agrees with mine, making me think you
probably have).  Even computers now considered toys (eg, an original
IBM PeeCee) will have no trouble at all.

In what sense is it still unsolved?

> The total number of possible positions is 92.
> [eightfold symmetry, from rotation & reflection]
> But the question is then, the total number of solutions should be a
> multiple of 8.
> Actually 4 mirror images coincides.

They do?  I didn't see any that were mirror-symmetric; what I did see
was one pattern that had 180-degree *rotational* symmetry, and thus
generated only four solutions instead of eight.

In case anyone would rather be lazy, here are the 12 basic patterns:

 . . . 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 . . . . . .
-----------------------------------------------------------------------
 . . 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 . . . . .

Each of these generates eight solutions, except for the rotationally
symmetric one, which generates only four, for the total of 92.

The analogous problem of placing N queens on an NxN board, has no
solutions for N=2 or N=3 and only the one trivial solution for N=1.
Solution counts for higher values of N are as follows.  Two counts are
given for each value of N, one counting rotations and reflections as
different, the other not.

N
4	1	2
5	2	10
6	1	4
7	6	40
8	12	92
9	46	352
10	92	724

The list of rotationally symmetric patterns includes some interesting
ones...I think I smell a game lurking in the N=9 patterns.

					der Mouse

			    mouse@larry.mcrcim.mcgill.edu