Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Perhaps you would like to say what progress you have made so far, and what exactly is causing you problems? –  Old John Nov 4 '12 at 18:19
    
I could not develop almost nothing because the diagonals, they are variables and left me not knowing what to do. –  John Smith Nov 4 '12 at 18:21
6  
(a) is the eight queens puzzle. –  Brian M. Scott Nov 4 '12 at 18:21
1  
For part (b) you could examine what happens when the first queen has been placed on different "types" of initial square depending on the number of other squares that the initial queen attacks. It looks like a lot of separate cases need to be considered, unless someone finds a neat solution. –  Old John Nov 4 '12 at 18:24
1  
@JohnSmith: if you read the Wikipedia article, you'll see that it mentions not just $n = 8$, but does consider all $n$ in general. In particular, the section about the number of solutions is en.wikipedia.org/wiki/Eight_queens_puzzle#Counting_solutions and it mentions that there is no known formula for the exact number of solutions. (The numbers are OEIS sequence A000170.) Your question (b) seems a separate question altogether. –  ShreevatsaR Nov 4 '12 at 18:26

6 Answers 6

up vote 4 down vote accepted

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

share|improve this answer
    
People will usually read the answer first and then the comments, so adding a correction in a comment isn't likely to significantly reduce their confusion by this error; it would be much preferable to edit the answer accordingly. –  joriki Nov 4 '12 at 20:09
    
@joriki, Thanks, done. –  Julien Clancy Nov 4 '12 at 20:22

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
share|improve this answer

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

share|improve this answer
    
This is a very nice survey indeed. Upvoted. –  Marko Riedel Jan 3 at 4:01

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

*..........................
...*.......................
.*.........................
....*......................
..*........................
................*..........
..................*........
......................*....
.....*.....................
.................*.........
......*....................
.....................*.....
.......*...................
....................*......
........*..................
...................*.......
.........*.................
..........................*
.......................*...
.........................*.
..........*................
........................*..
.............*.............
...............*...........
............*..............
..............*............
...........*...............
share|improve this answer

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#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> <yes/no> <seed>\n", argv[0]);
    exit(-3);
  }

  srand(seed);

  state st; st.n = n; st.col = 0;

  int pos;
  for(pos=0; pos<n; pos++){
    st.seq[pos] = pos;
  }

  for(pos=n-1; pos>0; pos--){
    int exch = rand() % (pos+1);

    int tmp = st.seq[pos];
    st.seq[pos] = st.seq[exch];
    st.seq[exch] = tmp;
  }

  for(pos=0; pos<n; pos++){
    if(pos>0) 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:

...........................................................*........................................
.........................................................................................*..........
..................................................................................................*.
......................................................................*.............................
...............................................*....................................................
.............*......................................................................................
....................*...............................................................................
...................................................................*................................
...........*........................................................................................
...............*....................................................................................
....................................................*...............................................
.....................*..............................................................................
.................*..................................................................................
..................................................*.................................................
..........................................................................................*.........
......................................................*.............................................
..................*.................................................................................
........*...........................................................................................
.....*..............................................................................................
..........................*.........................................................................
....................................*...............................................................
.......................................................................*............................
..........................................*.........................................................
................................................................*...................................
.......*............................................................................................
...*................................................................................................
.....................................................*..............................................
.................................................................................................*..
.............................................................*......................................
...................................................................................*................
.........................*..........................................................................
..................................................................................*.................
.................................*..................................................................
..............*.....................................................................................
........................................................................*...........................
....................................................................................*...............
................................*...................................................................
.........................................................................*..........................
...........................................................................................*........
......................................*.............................................................
.....................................................................*..............................
..................................*.................................................................
........................*...........................................................................
............................................................*.......................................
.........................................................*..........................................
................*...................................................................................
....*...............................................................................................
.......................................................................................*............
..............................................*.....................................................
.....................................*..............................................................
..............................................................................*.....................
...................................................................................................*
...........................................................................*........................
........................................................................................*...........
..................................................................*.................................
...........................*........................................................................
................................................................................*...................
...................................................*................................................
......................*.............................................................................
........................................................*...........................................
............................................................................................*.......
............................................................................*.......................
.............................................................................................*......
.........*..........................................................................................
......*.............................................................................................
........................................*...........................................................
.............................................*......................................................
...................................*................................................................
...............................................................................*....................
...............................................................................................*....
..............................................................*.....................................
.......................................................*............................................
.................................................*..................................................
...........................................*........................................................
..........................................................................*.........................
................................................*...................................................
.....................................................................................*..............
................................................................................................*...
............................................*.......................................................
............................*.......................................................................
...................*................................................................................
..........*.........................................................................................
..........................................................*.........................................
...............................................................*....................................
.*..................................................................................................
............*.......................................................................................
..*.................................................................................................
..............................*.....................................................................
.............................................................................*......................
.............................*......................................................................
..............................................................................................*.....
.......................*............................................................................
.......................................*............................................................
*...................................................................................................
...............................*....................................................................
.................................................................................*..................
......................................................................................*.............
.........................................*..........................................................
.................................................................*..................................
....................................................................*...............................
share|improve this answer

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 <stdio.h>
#include <stdlib.h>
#include <string.h>

#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> <yes/no>\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):

*.............................
...*..........................
.*............................
....*.........................
..*...........................
.......................*......
.........*....................
......................*.......
.....*........................
.....................*........
......*.......................
....................*.........
.......*......................
...........................*..
........*.....................
...................*..........
..........................*...
........................*.....
.............................*
.........................*....
............................*.
..............*...............
..........*...................
...............*..............
.............*................
...........*..................
.................*............
............*.................
..................*...........
................*.............
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.