How many ways can eight queens be placed so that they control the board?
competition/games/chess/queens Added material
Problem
How many ways can eight queens be placed so that they control the board?
Show solution
92. The following program uses a backtracking algorithm to count positions:
#include <stdio.h>
static int count = 0;
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;
}
}
}
void main() {
try(0,0,0);
printf("There are %d solutions.\n", count);
}
--
Tony Lezard IS tony@mantis.co.uk OR tony%mantis.co.uk@uknet.ac.uk
OR EVEN arl10@phx.cam.ac.uk if all else fails.
Additional material
[ Editor: "queens - N-Queens Chess Solver", posted to comp.sources.misc
(volume 40, issue 3), October 1993. ]
I'm sure that there are a bazillion solutions to the Eight Queens
chess problem floating around on the net, but I'm still quite
proud of the solution I came up with way back in '84. I can't
resist showing it off to everyone. Amazingly, it still works!! ;-)
The Eight Queens problem, for those who don't know, involves
finding all the ways that you can place 8 queens on a chess board
so that no queen can capture any other -- that is, no more than
a single queen appears on any rank, file or diagonal. Try to
do it yourself -- it's *really* hard.
On a Sun or Mac, my program will find all 92 8x8 solutions
in a fraction of a second. OK -- so there are actually only
23 unique solutions -- my program doesn't exploit rotational
symmetries to report only unique solutions. If you have an
ANSI C compiler, you should be able to get it up and running
in minutes. Instructions are included in the source code.
The heart of the code is a recursive pruning algorithm that
zeros in on solutions quickly without wasting a lot of time.
I've found that it's an excellent way to teach recursive
programming techniques to people. Also, great care has
been taking to minimize the amount of time it takes to
detect when queens lie on the same rank, file or diagonal.
I'm particularly proud of how I did that.
I recently dug up the code to solve another unrelated
problem, ANSI-fied it in the process, and decided that
it was about time I posted it for all to see.
Have fun with it!!
some examples...
$ Queens 8 ## Nearly instantaneous
8 queens on a 8x8 board...
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
$ Queens -c 8 ## Count all 8x8 solutions. <1 second.
8 queens on a 8x8 board...
...there are 92 solutions
$ Queens -c 12 ## Count all 12x12 solutions. About 20 seconds.
12 queens on a 12x12 board...
...there are 14200 solutions
[ Editor: the 92 solutions fall into 12 classes under rotation and
reflection (11 classes of 8 and one symmetric class of 4: 11*8 + 4 =
92), not 23. ]
[ Editor: the program, Queens.c, follows. It was posted as a shell
archive, with each line prefixed by "X"; the archive wrapper and the
README file (which repeats the text above) are omitted. ]
/*
** Queens.c -- Find solutions to the Eight-Queens chess problem.
** Roberto Sierra 3/19/84 Version 1.1
**
** Description:
** This program finds all the possible ways that N queens can
** be placed on an NxN chessboard so that the queens cannot
** capture one another -- that is, so that no rank, file or
** diagonal is occupied by more than one queen. By default,
** the program prints the first solution it finds. You can
** use the -a option to print all solutions, or the -c option
** just to count them. The program allows the chess board
** to be from 1x1 (trivial case) to 100x100. Warning: the
** larger the chess board, the longer it typically takes to
** find each solution, even though there may be more of them.
**
** This is a terrific example of the utility of recursion. The
** algorithm uses recursion to drastically limit the number
** of board positions that are tested. The program is able
** to find all 8x8 queen solutions in a fraction of a second
** (not counting print time). The code makes no attempt to
** eliminate symmetrical solutions, so the number of solutions
** reported will always be higher than the actual number of
** distinct solutions.
**
**
** Usage:
** Queens [-ac] n
**
** n number of queens (rows and columns).
** An integer from 1 to 100.
** -a Find (and print) all solutions.
** -c Count all solutions, but do not print them.
**
** The output is sent to stdout. All errors messages are
** sent to stderr. If a problem arises, the return code is -1.
**
**
** Examples:
**
** Queens 8 ## Show an 8x8 solution
** 8 queens on a 8x8 board...
** Q - - - - - - -
** - - - - Q - - -
** - - - - - - - Q
** - - - - - Q - -
** - - Q - - - - -
** - - - - - - Q -
** - Q - - - - - -
** - - - Q - - - -
**
** Queens -c 8 ## Count all 8x8 solutions
** 8 queens on a 8x8 board...
** ...there are 92 solutions.
**
** Queens -a 4 ## Show all 4x4 solutions
** 4 queens on a 4x4 board...
**
** Solution #1:
** - Q - -
** - - - Q
** Q - - -
** - - Q -
**
** Solution #2:
** - - Q -
** Q - - -
** - - - Q
** - Q - -
**
** ...there are 2 solutions.
**
**
** Build Instructions:
** You'll need an ANSI C compiler (or the willingness to edit
** the program a bit). If you've got Gnu C, then you can
** compile and load the program as follows:
**
** gcc Queens.c -ansi -o Queens
**
** [If you're using MPW on the Mac, define '-d MPW' on the
** compile line so that background processing will occur.]
**
**
** Algorithm:
** In a 1984 Byte article, I ran across an interesting letter
** from a high school student who was attempting to solve the
** Eight Queens problem using a BASIC interpreter. He had
** developed a program which placed eight queens successively
** on all sixty-four squares, testing for conflicts at each
** iteration. Of course, such a program would require 64^8
** iterations (about 2.8x10^14 iterations). Even in C on a,
** fast CPU, this could take months or years. Byte's answer was
** to alter the loops so that the queens resided on separate
** ranks, thereby reducing the number of iterations required
** to find all solutions to 8^8 iterations (about 16 million).
** More reasonable, but still requiring a chunk of CPU time.
**
** I puzzled about this problem a bit, and came to realize that
** this was still wasting a lot of CPU cycles. Though I'm sure
** others have come up with good algorithms, I decided to come
** up with my own, with a particular eye on efficiency. The
** resulting algorithm finds all 8x8 solutions in a fraction
** of a second (there are 92 solutions, including rotations).
** On a Sun 4, it'll find all 365,596 solutions on a 14x14 board
** in a bit over 2 minutes (printing them out requires extra
** time, of course). Even Byte's solution would require 14^14
** iterations (about 10^16) which would take aeons.
**
** My algorithm works as follows:
** (1) Place a queen in the top left corner.
** (2) Place another queen immediately below.
** (3) Test for conflicts. If the second queen conflicts (it
** does at first), then move it one square to the right.
** (4) Loop step 3 until there are no conflicts. Place
** the next queen on the board and recurse.
** (5) If any queen reaches the right edge of the board,
** remove it and 'pop' to the previous recursion level.
** (6) Now repeat these steps recursively until all eight
** queens (or however many) have been placed without
** conflict -- the result is a solution to the problem,
** which is counted and optionally printed.
**
** Because conflicts are tested as the recursion proceeds,
** this has the effect of 'pruning' the recursion so that
** a large number of board positions are not even attempted.
** The result is that the algorithm runs in reasonable time.
**
** I used a few tricks to make the test-for-conflict code
** extremely efficient -- there is no 'inner' loop to search
** along ranks, files, or diagonals. A series of arrays are
** maintained instead which indicate which queen currently
** 'owns' each rank, file or diagonal. This makes the
** algorithm really fly, though the code is a little hard to
** read. Lastly, pointer arithmetic is used to reduce the
** number of implicit multiplications used in array addressing.
**
**
** Contact:
** For queries regarding this program, contact Roberto Sierra
** at any of the following addresses:
**
** Roberto Sierra
** bert@netcom.com (preferred address)
** 73557.2101@compuserve.com
**
** Tempered MicroDesigns
** P.O. Box 170638
** San Francisco, CA 94117
**
**
** Fine Print:
** This program is in the public domain and can be used for
** any purpose whatsoever, including commercial application.
** [I'd like to hear what you do with it, though.]
** Absolutely no warranty or liability is implied or extended
** by the author.
**
**
** Modification History:
** PRS 3/19/84 v1.0 -- Original version.
** PRS 7/25/93 v1.1 -- ANSIfied the code. More efficient pointers.
**
*/
#include <stdio.h> /* Need standard I/O functions */
#include <stdlib.h> /* Need exit() routine interface */
#include <string.h> /* Need strcmp() interface */
#ifdef MPW /* Macintosh MPW ONLY */
#include <CursorCtl.h> /* Need cursor control interfaces */
#endif
#define MAXQUEENS 100 /* Maximum number of queens */
#define MAXRANKS MAXQUEENS /* Maximum number of ranks (rows) */
#define MAXFILES MAXQUEENS /* Maximum number of files (columns) */
#define MAXDIAGS (MAXRANKS+MAXFILES-1) /* Maximum number of diagonals */
#define EMPTY (MAXQUEENS+1) /* Marks unoccupied file or diagonal */
/* GLOBAL VARIABLES */
int queens; /* Number of queens to place */
int ranks; /* Number of ranks (rows) */
int files; /* Number of files (columns) */
int printing = 1; /* TRUE if printing positions */
int findall = 0; /* TRUE if finding all solutions */
unsigned long solutions = 0; /* Number of solutions found */
int queen[MAXRANKS]; /* File on which each queen is located */
int file[MAXFILES]; /* Which queen 'owns' each file */
int fordiag[MAXDIAGS]; /* Which queen 'owns' forward diagonals */
int bakdiag[MAXDIAGS]; /* Which queen 'owns' reverse diagonals */
char *progname = 0; /* The name of this program */
/***********************/
/**** ROUTINES ****/
/***********************/
/* Internal prototypes */
void main(int argc,char **argv); /* Main program */
void find(int level); /* Algorithm to find solutions */
void pboard(void); /* Print a solution */
/*---------------------- main() ---------------------------
** MAIN program. The main purpose of this routine is
** to deal with decoding the command line arguments,
** initializing the various arrays, and starting the
** recursive search routine.
*/
void main(int argc,char **argv)
{
register int i; /* Loop variable */
register char *p; /* Pointer to argument */
#ifdef MPW /* Macintosh MPW ONLY */
InitCursorCtl(0); /* Enable cursor control */
#endif
progname = argv[0]; /* The name of the program */
/**** DECODE COMMAND LINE ARGUMENTS ****/
for (i=1; i<argc; ++i) { /* Scan through arguments */
p = argv[i]; /* Pointer to base of argument */
if (*p == '-') { /* Command line option? */
while (*++p) { /* Loop through characters */
switch (*p) { /* What is the character */
case 'a': /* '-a' option */
findall = 1; /* Set flag to find all solutions */
break;
case 'c': /* '-c' option */
printing = 0; /* Counting, not printing */
findall = 1; /* Also forces findall option */
break;
default: /* Illegal option */
fprintf(stderr,"%s: Illegal option '%s'\n",progname,argv[i]);
fprintf(stderr,"usage: %s [-ac] queens\n",progname);
exit(-1);
} /* End of switch */
} /* End of loop */
} else { /* End of option test */
if (sscanf(p,"%d",&queens) != 1) { /* Read integer argument */
fprintf(stderr,"%s: non-integer argument '%s'\n",progname,p);
exit(-1);
}
if (queens <= 0) { /* N must be positive */
fprintf(stderr,"%s: queens must be positive integer\n",progname);
exit(-1);
}
if (queens > MAXQUEENS) { /* N can't be too large */
fprintf(stderr,"%s: can't have more than %d queens\n",
progname, MAXQUEENS);
exit(-1);
}
} /* End of argument test */
} /* End of argument scan loop */
if (queens == 0) {
fprintf(stderr,"%s: missing queens argument\n",progname);
fprintf(stderr,"usage: %s [-ac] queens\n",progname);
exit(-1);
}
ranks = files = queens; /* NxN board for N queens */
printf("%d queen%s on a %dx%d board...\n",
queens, queens>1? "s" : "", ranks, files);
fflush(stdout);
/* Initialization */
solutions = 0; /* No solutions yet */
for (i=0; i<MAXFILES; ++i) file[i] = EMPTY;
for (i=0; i<MAXDIAGS; ++i) fordiag[i] = bakdiag[i] = EMPTY;
/* Find all solutions (begin recursion) */
find(0);
if (printing && solutions) putchar('\n');
/* Report results */
if (solutions == 1) {
printf("...there is 1 solution\n");
} else {
printf("...there are %ld solutions\n", solutions);
}
exit(0); /* No errors */
} /* End of main() */
/*-------------------------- find() ----------------------------
** FIND is the recursive heart of the program, and finds all
** solutions given a set of level-1 fixed queen positions.
** The routine moves a single queen through all files (columns)
** at the current rank (recursion level). As the queen is moved,
** conflict tests are made. If the queen can be placed without
** conflict, then the routine recurses to the next level. When
** all queens have been placed without conflict, a solution is
** counted and reported.
*/
void find(register int level)
{
register int f; /* Indexes through files */
register int *fp,*fdp,*bdp; /* Ptrs to file/diagonal entries */
#ifdef MPW /* Macintosh MPW ONLY */
if (level & 7 == 0) { /* Periodically break for... */
SpinCursor(1); /* background processing */
}
#endif
if (level == queens) { /* Placed all queens? Stop. */
++solutions; /* Congrats, this is a solution! */
if (printing) pboard(); /* Print board if printing */
if (!findall) exit(0); /* May stop after first solution */
#ifdef MPW /* Macintosh MPW ONLY */
SpinCursor(1); /* Allow background processing */
#endif
} else { /* Not at final level yet */
for ( /* MOVE QUEEN THROUGH ALL FILES */
f = 0, /* Queen starts at left (file 0) */
fp = file, /* Ptr to base of file array */
fdp = &fordiag[level], /* Ptr to first fwd diag entry */
bdp = &bakdiag[level+files-1] /* Ptr to first bak diag entry */
;
f < files /* Loop through all files */
;
++f, /* Advance index */
++fp, ++fdp, --bdp /* Advance pointers */
) {
if (*fp >= level && /* No queen on the file? */
*fdp >= level && *bdp >= level /* No queens on diagonals? */
) {
queen[level] = f; /* Note new position of queen */
*fp = *fdp = *bdp = level; /* Place queen on file & diags */
find(level+1); /* This level OK, recurse to next */
*fp = *fdp = *bdp = EMPTY; /* Remove queen from file & diags */
} /* End of conflict test */
} /* End of file loop */
} /* End if (level == queens) */
} /* End of find() */
/*------------------------- pboard() -----------------------
** This routines prints the board for a particular solution.
** The output is sent to stdout.
*/
void pboard(void)
{
register int i,j; /* Rank/File indices */
if (findall) { /* Only if searching for all */
printf("\nSolution #%lu:\n",solutions); /* Print solution number */
}
for (i=0; i<ranks; ++i) { /* Loop through all ranks */
for (j=0; j<files; ++j) { /* Loop through all files */
putchar(' '); /* Output a space */
if (j==queen[i]) putchar('Q'); /* Output Q for queen... */
else putchar('-'); /* or '-' if empty */
}
putchar('\n'); /* Break line */
}
fflush(stdout); /* Flush solution to output */
} /* End of pboard() */
/**** End of Queens.c ****/
-- Roberto Sierra <bert@netcom.com>
[ Editor: a mail of October 1994 to Michael Trick <trick@cmu.edu>,
copied to Chris Cole for this entry: ]
Question:
Can N solutions to the standard N queen problem be superimposed
to fill the NxN board?
Answer:
Amazingly, the answer is yes iff N is not divisible by 2 or 3.
So for N=5 a solution exists, viz.
ADBEC
BECAD
CADBE
DBECA
ECADB
For N=6, 8, 9, 10, 12, ... no solutions exist.
Martin Gardner in "The Unexpected Hanging", Simon and Schuster, 1969,
on pages 191-195 discusses the problem and also gives a relatively
simple proof that N=8 has no solution.
-- Myron P. Souris <souris@ug.eds.com>
[ Editor: from a December 1994 rec.puzzles thread: ]
Andrew Hogg <AHogg@mertcplc.demon.co.uk> wrote:
>The functional programming language Gofer, contains this problem in
>one of it's example pieces of code. (Solves it in about 7 lines).
>The 92 solutions can be done in reasonable time (on a fast machine.)
The 92 solutions can be done in cut time with the 24-line C program by
Tony Lezard in the archive. John Tromp posted a 5-liner from the 1990
Obfuscated C contest for the general N queens problem: you run it and
give it the size of the square in standard input, and it displays all
the configurations. I don't know if he's the original author, but I
do know he's clever enough to have been. Here's the program; I brutalized
it by wrapping it into 7 lines so that it won't overflow the 80-character
normal screen width. This one's also very fast -- I don't know what Gofer is
doing with all its time. Tony's is clearer, but that's rather the idea, eh?
_______________________________________________________________________
v,i,j,k,l,s,a[99];
main()
{
for(scanf("%d",&s);*a-s;v=a[j*=v]-a[i],k=i<s,j+=(v=j<s&&(!k&&!!
printf(2+"\n\n%c"-(!l<<!j)," #Q"[l^v?(l^j)&1:2])&&++l||a[i]<s&&
v&&v-i+j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0:++a[i])>=s*k&&++a[--i]);
}
_______________________________________________________________________
--
-- Jim Gillogly <jim@acm.org>