Re: [MLUG] N-Queens Problem Solver

[Mike Miller <EMAIL:PROTECTED>]

Stephen Montgomery-Smith wrote:

> I was once involved in a programming competition related to this 
> problem:
>
> http://www.recmath.org/contest/AttackingQueens/Description.html

I was just thinking ... one of the little parts of the puzzle is to figure 
out how many different possible directions a queen can move in N 
dimensions.  She can move one way in one dimension, four ways in two 
dimensions (east-west, north-south, northeast-southwest, 
northwest-southeast), 13 ways in three dimensions and 40 ways in four 
dimensions, or so says the web page.  What about in 5 dimensions or in 20 
dimensions?  I am assuming the queen is not against an edge.

This is what I get:

 N
Sum  (N choose i) [2^(i-1)]
i=1

(But I now realize that adds up to half of one less than 3^N ; see below.)

> From that you can produce something that looks kinda like Pascal's 
triangle and where the sum for every row tells you the number of possible 
movement directions for that dimension.  Here's the triangle for the first 
twenty rows (but it will probably wrap for most of you and you also need a 
fixed-width font for it to look right):

 1
 2   2
 3   6    4
 4  12   16     8
 5  20   40    40     16
 6  30   80   120     96      32
 7  42  140   280    336     224      64
 8  56  224   560    896     896     512      128
 9  72  336  1008   2016    2688    2304     1152      256
10  90  480  1680   4032    6720    7680     5760     2560      512
11 110  660  2640   7392   14784   21120    21120    14080     5632      1024
12 132  880  3960  12672   29568   50688    63360    56320    33792     12288      2048
13 156 1144  5720  20592   54912  109824   164736   183040   146432     79872     26624      4096
14 182 1456  8008  32032   96096  219648   384384   512512   512512    372736    186368     57344      8192
15 210 1820 10920  48048  160160  411840   823680  1281280  1537536   1397760    931840    430080    122880     16384
16 240 2240 14560  69888  256256  732160  1647360  2928640  4100096   4472832   3727360   2293760    983040    262144     32768
17 272 2720 19040  99008  396032 1244672  3111680  6223360  9957376  12673024  12673024   9748480   5570560   2228224    557056    65536
18 306 3264 24480 137088  594048 2036736  5601024 12446720 22404096  32587776  38019072  35094528  25067520  13369344   5013504  1179648   131072
19 342 3876 31008 186048  868224 3224832  9674496 23648768 47297536  77395968 103194624 111132672  95256576  63504384  31752192 11206656  2490368  262144
20 380 4560 38760 248064 1240320 4961280 16124160 42997760 94595072 171991040 257986560 317521920 317521920 254017536 158760960 74711040 24903680 5242880 524288

In each column you have counts for different kinds of moves -- first 
single dimensional, then 2-d diagonal, 3-d "diagonal," etc.  So in 10 
dimensions there are 90 possible 2-d diagonal directions because there are 
45 possible pairs of dimensions with two diagonals in each.

Then you add up the rows you get these numbers:

 1          1
 2          4
 3         13
 4         40
 5        121
 6        364
 7       1093
 8       3280
 9       9841
10      29524
11      88573
12     265720
13     797161
14    2391484
15    7174453
16   21523360
17   64570081
18  193710244
19  581130733
20 1743392200

So there are 1,743,392,200 possible movement directions for a queen in 20 
dimensions -- that's more than a billion possibilities!  At 51 dimensions, 
you exceed Avogadro's number.

Now, after all that playing around, I find that these numbers also are 
exactly (3^N-1)/2, that is, half of one less than three to the N.  This 
also is similar to Pascal's triangle where the sum of a row is always 
2^(N-1).  I also now see why the answer is (3^N-1)/2 and can explain it to 
anyone who is interested -- it has to do with the fact that there are 
three movement directions per dimension: "up," "down," and "still," and we 
must combine N dimesions to make a move.

Some Octave code:

x = 1; for i=2:20, x=[(x*i)./[(i-1):-1:1] , 2^(i-1)]; disp(x), end
x = 1; for i=2:20, x=[(x*i)./[(i-1):-1:1] , 2^(i-1)]; disp([i, sum(x)/3^i]), end
x = 1; for i=2:20, x=[(x*i)./[(i-1):-1:1] , 2^(i-1)]; disp([i, 2*sum(x)/(3^i-1)]), end
or:
(3^N-1)/2

Mike

_______________________________________________
members mailing list
EMAIL:PROTECTED
http://mlug.missouri.edu/mailman/listinfo/members