AT> I had to do this problem in class.  My solution for N queens was 
recursive 
AT> boolian.  One of my friends did it in a similar way, yet his returns n=15 
i
AT> under 1 second (on a pentium200) and mine (on an identical LabPC) took 1
AT> minute.  
AT> 
AT> Please give this program a try (I used a matrix... int Board [n][n]={0}; 

AT> and e-mail me your solution.  I want one that will Beat ChuckyZ's.
    You need a leason in tree pruning. You can cut down time tremendously
    if you don't make any uneeded recursive calls.
    EG:
    void print_tree(node* n) {
      if (n==0) return;
      cout string << endl;
      print_tree(n->left);
      print_tree(n->right);
    }
    This is a _bad_ recursive procedure: why?  A binary tree has at any
    level has twice as many nodes as the one above it.
           .
        .     .
       . .   . .
      . .. .. .. .
    
    
    At level 4 (8 nodes), print_tree make 2 calls at his level even
    though they are null calls - this means 16 un-needed calls.
    A total of 31 calls.
    void print_tree(node* n) {
      cout string << endl;
      
      if (n->left  != 0) print_tree(n->left);
      if (n->right != 0) print_tree(n->right);
    }
************************
    This function will only be called 15 times with the same 4 level
    binary tree.
    NOW the tree pruning. You cannot place a queen on the same horizontal
    line as another queen. You cannot place a queen on the same diagnal
    as another queen.
    Don't calculate any further once a queen is placed on a common horizontal
    or diagonal.
    The first queen goes on the first line first column. Try the second queen
    starting on the second line but not the first column nor the second 
lumn
    Q........
    XX.......
    The X represent a queen on a horizontal or diagonal with another 
    queen and should be skipped.
    The math is as follows. IF you have X squares you have X posible moves
    on the first try. You have X-1 moves left on the second try (because
    one quen takes up one spot). The formula is as follows:
     X*(X-1)*(X-2)*.....(X-(X-2))* (X-(X-1);
    15*14*13*12*...*1  = 15! 
    If you don't play on horizontals having a queen on them,
    pretending we have an 8x8 board
    Q.......
    ..
    . .
    .  .
    .   .
    .    .
    .     .
    .      .
    q.......
    .......q
    . .   ..
    .  . . .
    .   .  .
    .  . . .
    . .   ..
    ..     .
    After the first Q is played 21 other spots cannot be played on
    64 * (64-21) * (64-(21-(21-4)) * ....
    (notice that 4 "."'s are shared with the first play)
    64         = 64
    64-21      = 43
    64-21-21-4 = 18
    This will come out to be a few thousand instead of a few million.
    Any questions?
--- GEcho 1.00
---------------