1
$\begingroup$

A curious question.

a) How many different ways exists to put "n" queens on a chessboard and they all can't capture the others?

b)If you put one queen in the chess board knowing that exist one other queen there, what is the probability that the new can't be captured?

  • 0
    (b) seems much more possible that (a) also2012-11-04

6 Answers 6

4

This Python code from the wikipedia page of the eight queens problem mentioned in the comments above will give solutions for all n, but the algorithm is "intractable for n >= 20". A recode in Haskell would solve the problem of dealing with large numbers and would be significantly faster but still would quickly reach an upper limit.

from itertools import permutations  n = 8 cols = range(n) for vec in permutations(cols):     if (n == len(set(vec[i] + i for i in cols))           == len(set(vec[i] - i for i in cols))):         print vec 

This sequence shows the number of solutions for $n \in [1,26]$. For larger numbers the wikipedia page contains an "Exercise in algorithm design" section that should yield speedups, but perhaps none too significant (else the AES sequence would have more solutions).

Part $b$ might be analyzed as follows. Note that any rook on any square has access to $n - 1 + n - 1 = 2n - 1$ spaces (not including the space it is on). The bishop's movement is more difficult to analyze, but given coordinates $(x, y) \in [1,n] \times [1,n]$ there should emerge a movement pattern after a few examples (a proof of which should be pretty clear): concentric movement squares each increase in movement range by $2$ squares as they move in, with the outermost having range $n - 1$. Putting this together a queen at square $(x, y)$ in an $n$-sized grid, WLOG taking $x,y <= \frac{n}{2}$ (because of the concentric squares) has movement range $(2n - 2) + (n - 1) + (min(x, y) - 1) * 2$. From here on it's simple probability. Good luck on part $a$.

Edit: taking the minimum of x and y yields which concentric square it is in, exactly, which was the reason for taking $(x, y)$ in the lower left quadrant. For a sketch of the proof of why the concentric squares trick works, a bishop in the $(1,1)$ (lower left) position has $n - 1$ moves, so moving it out along the main diagonal increases its movement range by one in the top-left, bottom-right, and bottom-left diagonals (respective to the knight) and decreases its range by one in the top-right direction (as we moved it in that direction). This gives a net gain of two movement squares. Repeated application works until we reach the innermost concentric square, where the process begins to reverse. This only considered squares on the corners but squares on the edges work in exactly the same way and a quick example will convince you that the movement range of a bishop on the edge of the board is indeed $n - 1$.

  • 0
    @joriki, Thanks, done.2012-11-04
3

Before we get to the enumeration problem, we should probably consider the existence problem. This was studied by:

E.J. Hoffman, J.C. Loessi and R.C. Moore, Constructions for the Solution of the m Queens Problem, Mathematics Magazine (1969), 66-72. (pdf)

They found:

Theorem: For all $n \geq 4$ there exists a solution to the $n$-queens problem

Their proof goes as follows:

For $n=2m$ where $m \not\equiv 1 \pmod 3$ they gave the construction, e.g.:

.Q........ ...Q...... .....Q.... .......Q.. .........Q Q......... ..Q....... ....Q..... ......Q... ........Q. 

(Hopefully here, and with the subsequent constructions, it's clear from the picture how this generalises; if not, the full details are in the above paper.)

For $n=2m$ where $m \not\equiv 0 \pmod 3$ they gave, e.g.:

......Q....... ........Q..... ..........Q... ............Q. Q............. ..Q........... ....Q......... .........Q.... ...........Q.. .............Q .Q............ ...Q.......... .....Q........ .......Q...... 

Finally, for odd $n$, we just take one of the above constructions for $n-1$, add a new row (at the bottom) and column (on the right hand size) and place the new queen in the bottom-right. E.g.

......Q........ ........Q...... ..........Q.... ............Q.. Q.............. ..Q............ ....Q.......... .........Q..... ...........Q... .............Q. .Q............. ...Q........... .....Q......... .......Q....... ..............Q 
2

A nice (IMHO) introduction is Rivin/Vardi/Zimmerman

  • 0
    This is a very nice survey indeed. Upvoted.2014-01-03
0

Here is a program in Perl for the curious that can compute solutions even for $n\times n$ boards that are quite large. It can count all solutions and output them if desired.

 #! /usr/bin/perl -w  sub compute {     my ($n, $placed, $pf, $cref) = @_;      my $sofar = scalar(@$placed);     if($sofar == $n){       if(defined($pf)){           for(my $rind=0; $rind<$n; $rind++){             for(my $cind=0; $cind<$n; $cind++){                 my $m = ($placed->[$cind] == $rind ?                         "*" : ".");                 print "$m";             }             print "\n";           }            print "\n";       }        $$cref++;       return;     }      for(my $nxt=0; $nxt<$n; $nxt++){       my $admit = 1;        for(my $cind=0; $cind<$sofar; $cind++){           $admit = undef if $placed->[$cind] == $nxt;           $admit = undef if              $placed->[$cind]+$cind == $nxt+$sofar;           $admit = undef if              $placed->[$cind]-$cind == $nxt-$sofar;       }        if(defined($admit)){           push @$placed, $nxt;           compute($n, $placed, $pf, $cref);           pop @$placed;       }     } }   MAIN: {     my $n = shift || 8;     my $printflag = shift || undef;      my $count = 0;     compute($n, [], $printflag, \$count);      print "total $count solutions\n"; } 

The sequence of the count of all solutions as computed by this program is $1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680,\ldots$ which points to OEIS A000170.

This program computed the following solution to a $24\times 24$ board:

 *....................... ...*.................... .*...................... ....*................... ..*..................... ................*....... ...................*.... .................*...... .....*.................. ..............*......... ......*................. .......................* ....................*... .......*................ .....................*.. ..................*..... ......................*. ............*........... ..........*............. ........*............... ...........*............ .........*.............. ...............*........ .............*.......... 

Here is a solution for the $27\times 27.$

 *.......................... ...*....................... .*......................... ....*...................... ..*........................ ................*.......... ..................*........ ......................*.... .....*..................... .................*......... ......*.................... .....................*..... .......*................... ....................*...... ........*.................. ...................*....... .........*................. ..........................* .......................*... .........................*. ..........*................ ........................*.. .............*............. ...............*........... ............*.............. ..............*............ ...........*............... 
0

The above Perl program quickly reaches its limits. We can do a little better by using C as our programming language. This gives the following program.

 #include  #include  #include   #define MAXDIM 64  typedef struct {   int n;   int placed[MAXDIM];   int col; } state, *stateptr;  void compute(stateptr st, int pf, int *cptr) {   if(st->col == st->n){     if(pf){       for(int rind=0; rind < st->n; rind++){         for(int cind=0; cind < st->n; cind++){           char m = (st->placed[cind] == rind ? '*' : '.');           putchar(m);         }         putchar('\n');       }       putchar('\n');     }      (*cptr)++;     return;   }    for(int nxt=0; nxt< st->n; nxt++){     int admit = 1;      for(int cind=0; cind < st->col; cind++){       if(st->placed[cind] == nxt) admit = 0;       if(st->placed[cind] + cind == nxt + st->col) admit = 0;       if(st->placed[cind] - cind == nxt - st->col) admit = 0;     }      if(admit){       st->placed[st->col] = nxt;        st->col++;       compute(st, pf, cptr);       st->col--;     }   } }  int main(int argc, char **argv) {   int n = 8;   int print = 0;    if(argc>=2){     sscanf(argv[1], "%d", &n);     if(n<1 || n>MAXDIM){       fprintf(stderr, "dims out of range, got %d\n", n);       exit(-1);     }   }    if(argc>=3){     if(!strcmp(argv[2], "yes")){       print = 1;     }     else if(!strcmp(argv[2], "no")){       print = 0;     }     else{       fprintf(stderr, "print flag either yes/no\n");       exit(-2);     }   }    if(argc>=4){     fprintf(stderr, "usage: %s  \n", argv[0]);     exit(-3);   }    state st; st.n = n; st.col = 0;    int count = 0;   compute(&st, print, &count);    printf("total %d solutions found\n", count); } 

The C program produces the following solution for a $31\times 31$ board:

 *.............................. ...*........................... .*............................. ....*.......................... ..*............................ .........*..................... ....................*.......... ..................*............ .....*......................... .....................*......... ......*........................ ..........................*.... .......*....................... ......................*........ ........*...................... ............................*.. .......................*....... ..........*.................... ........................*...... ...........................*... ..............................* ............*.................. .........................*..... ...............*............... .............................*. ...........*................... ..............*................ .................*............. .............*................. ................*.............. ...................*........... 

And for a $30\times 30$ board we get the solution (one of many that are produced):

 *............................. ...*.......................... .*............................ ....*......................... ..*........................... .......................*...... .........*.................... ......................*....... .....*........................ .....................*........ ......*....................... ....................*......... .......*...................... ...........................*.. ........*..................... ...................*.......... ..........................*... ........................*..... .............................* .........................*.... ............................*. ..............*............... ..........*................... ...............*.............. .............*................ ...........*.................. .................*............ ............*................. ..................*........... ................*............. 
0

If we are interested in calculating solutions of large dimensions we can use the following randomized algorithm.

 #include  #include  #include   #define MAXDIM 128  typedef struct {   int n;   int placed[MAXDIM];   int seq[MAXDIM];   int col; } state, *stateptr;  void compute(stateptr st, int pf, int *cptr) {   if(st->col == st->n){     if(pf){       for(int rind=0; rind < st->n; rind++){         for(int cind=0; cind < st->n; cind++){           char m = (st->placed[cind] == rind ? '*' : '.');           putchar(m);         }         putchar('\n');       }       putchar('\n');     }      (*cptr)++;     return;   }    for(int nxt=0; nxt< st->n; nxt++){     int admit = 1;      for(int cind=0; cind < st->col; cind++){       if(st->placed[st->seq[cind]] == nxt)          admit = 0;       if(st->placed[st->seq[cind]] + st->seq[cind] ==           nxt + st->seq[st->col])          admit = 0;       if(st->placed[st->seq[cind]] - st->seq[cind] ==           nxt - st->seq[st->col])          admit = 0;     }      if(admit){       st->placed[st->seq[st->col]] = nxt;        st->col++;       compute(st, pf, cptr);       st->col--;     }   } }  int main(int argc, char **argv) {   unsigned int seed = 0;   int n = 8;   int print = 0;    if(argc>=2){     sscanf(argv[1], "%d", &n);     if(n<1 || n>MAXDIM){       fprintf(stderr, "dims out of range, got %d\n", n);       exit(-1);     }   }    if(argc>=3){     if(!strcmp(argv[2], "yes")){       print = 1;     }     else if(!strcmp(argv[2], "no")){       print = 0;     }     else{       fprintf(stderr, "print flag either yes/no\n");       exit(-2);     }   }    if(argc>=4){     sscanf(argv[3], "%d", &seed);   }    if(argc>=5){     fprintf(stderr, "usage: %s   \n", argv[0]);     exit(-3);   }    srand(seed);    state st; st.n = n; st.col = 0;    int pos;   for(pos=0; pos0; pos--){     int exch = rand() % (pos+1);      int tmp = st.seq[pos];     st.seq[pos] = st.seq[exch];     st.seq[exch] = tmp;   }    for(pos=0; pos0) putchar(' ');     printf("%d", st.seq[pos]);   }   putchar('\n');    int count = 0;   compute(&st, print, &count);    printf("total %d solutions found\n", count); }  

This will find e.g. the following $48\times 48$ board:

 .....*.......................................... ..................................*............. ...............................*................ .................................*.............. .......*........................................ .............*.................................. ....*........................................... ........................*....................... .............................*.................. ..............................................*. .....................................*.......... .......................................*........ ..............*................................. .................*.............................. ..........*..................................... ........*....................................... ...........*.................................... ...........................*.................... .*.............................................. .........................................*...... ................................*............... ....................................*........... ...................*............................ ..............................*................. ...........................................*.... ..........................*..................... ....................*........................... ...............................................* ............................................*... ........................................*....... ..................*............................. .............................................*.. ......................*......................... ......*......................................... .........................*...................... ...................................*............ ..........................................*..... ............*................................... ..*............................................. ......................................*......... ...*............................................ .......................*........................ ................*............................... ............................*................... .....................*.......................... *............................................... ...............*................................ .........*...................................... 

Here is a $64\times 64$ board:

 .*.............................................................. .......................................................*........ ...............................................*................ ..........................*..................................... ..............*................................................. .......*........................................................ .............................................*.................. ......*......................................................... ..............................................*................. ...............*................................................ .............................................................*.. .........................................................*...... ..*............................................................. ..................*............................................. .................................................*.............. .............*.................................................. .........*...................................................... .....................*.......................................... ................................*............................... ................*............................................... ...*............................................................ ..................................*............................. ......................*......................................... ..............................*................................. ...................................*............................ ....................*........................................... .................*.............................................. ...........................................*.................... ..................................................*............. ......................................*......................... ............................................................*... ...................................................*............ ........................................*....................... ....................................................*........... .......................*........................................ .....................................................*.......... ............*................................................... ....*........................................................... ..............................................................*. ...................*............................................ *............................................................... ............................*................................... ...............................................................* ...............................*................................ ...........................................................*.... .......................................*........................ ..........................................................*..... .................................*.............................. ............................................*................... ...........................*.................................... ...........*.................................................... ........................*....................................... ........*....................................................... ........................................................*....... .............................*.................................. ....................................*........................... ..........*..................................................... .........................................*...................... .....................................*.......................... .....*.......................................................... ..........................................*..................... .........................*...................................... ......................................................*......... ................................................*............... 

And to conclude, an example of a $100\times 100$ board:

 ...........................................................*........................................ .........................................................................................*.......... ..................................................................................................*. ......................................................................*............................. ...............................................*.................................................... .............*...................................................................................... ....................*............................................................................... ...................................................................*................................ ...........*........................................................................................ ...............*.................................................................................... ....................................................*............................................... .....................*.............................................................................. .................*.................................................................................. ..................................................*................................................. ..........................................................................................*......... ......................................................*............................................. ..................*................................................................................. ........*........................................................................................... .....*.............................................................................................. ..........................*......................................................................... ....................................*............................................................... .......................................................................*............................ ..........................................*......................................................... ................................................................*................................... .......*............................................................................................ ...*................................................................................................ .....................................................*.............................................. .................................................................................................*.. .............................................................*...................................... ...................................................................................*................ .........................*.......................................................................... ..................................................................................*................. .................................*.................................................................. ..............*..................................................................................... ........................................................................*........................... ....................................................................................*............... ................................*................................................................... .........................................................................*.......................... ...........................................................................................*........ ......................................*............................................................. .....................................................................*.............................. ..................................*................................................................. ........................*........................................................................... ............................................................*....................................... .........................................................*.......................................... ................*................................................................................... ....*............................................................................................... .......................................................................................*............ ..............................................*..................................................... .....................................*.............................................................. ..............................................................................*..................... ...................................................................................................* ...........................................................................*........................ ........................................................................................*........... ..................................................................*................................. ...........................*........................................................................ ................................................................................*................... ...................................................*................................................ ......................*............................................................................. ........................................................*........................................... ............................................................................................*....... ............................................................................*....................... .............................................................................................*...... .........*.......................................................................................... ......*............................................................................................. ........................................*........................................................... .............................................*...................................................... ...................................*................................................................ ...............................................................................*.................... ...............................................................................................*.... ..............................................................*..................................... .......................................................*............................................ .................................................*.................................................. ...........................................*........................................................ ..........................................................................*......................... ................................................*................................................... .....................................................................................*.............. ................................................................................................*... ............................................*....................................................... ............................*....................................................................... ...................*................................................................................ ..........*......................................................................................... ..........................................................*......................................... ...............................................................*.................................... .*.................................................................................................. ............*....................................................................................... ..*................................................................................................. ..............................*..................................................................... .............................................................................*...................... .............................*...................................................................... ..............................................................................................*..... .......................*............................................................................ .......................................*............................................................ *................................................................................................... ...............................*.................................................................... .................................................................................*.................. ......................................................................................*............. .........................................*.......................................................... .................................................................*.................................. ....................................................................*...............................