[SunRescue] Large scale parallel problems

[James Lockwood]

A few of you expressed interest in doing "interesting" computational work
with idle cycles a couple of weeks back.  This probably isn't the ideal
forum for this, but there are probably enough interested parties here to
make it worthwhile.

One of the (odd) problems a long time friend of mine and I have been
obsessed with is the "8 Queens" challenge.  Simply put, the goal is to
determine how many distinct permutations on N queens can fit on an NxN
chessboard such that none are aligned with any other on any row, column
or diagonal.

Using genetic algorithms it's trivial to get "some" solutions for boards
of any size (we've got some for 3000x3000 at the moment).  Unfortunately
finding the entire solution set is very computationally difficult, of the
rough order O(6^N) when branch elimination from backtracking is factored
in. The largest board size where the exhaustive solution is known is
23x23, this was generated by a French team using 200 processors for over 2
months.  They've generated solutions for 21x21, 22x22 and 23x23, these
have never been verified by another group as far as we know.  See:

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=170

http://www.research.att.com/~njas/sequences/eisBTfry00018.html
(sequence A000170)

We've come up with some optimizations that may give close to an order of
magnitude improvement in CPU time needed to solve large boards.  Part of
this is rethinking the algorithm (normally recursive backtracking) to use
set theory and part of it is taking advantage of vector bitwise operations
(great benefit for vector CPU's or those using VIS/MMX/Altivec/etc).

Sure, it's not as glamorous as Goldbach's Conjecture, but it's a chance to
explore a section of combinatorial mathematics where there are very few
data points at present.  We're currently cooking up a distributed client
which will be written in both Java and C.  The Java version is an applet
which communicates only with its server to help alleviate security
concerns, the C version will be more heavily optimized with bitfield
manipulation and can be vectorized (though maybe a FORTRAN port is
necessary to wring out more speed...  *shudder*).  Both communicate with a
server via vanilla HTTP requests.

So, I'd like to ask:

  How many people (and processors per person) are interested?

  How big are your caches (the set version probably needs tuning for
  small-cache boxes)?

  Would you prefer to be running a Java applet to help with security at
  the cost of some overhead? 

  Is it at all important to have a NiftySpiffy(tm) status
  display/screensaver for entertainment purposes?

  How long is it convenient for a "work unit" to take?

  Would it be nice to be able to crunch work units offline?

  Do people want source code (just kidding, I know they do)?

Please send any responses to me OFF-LIST (james at foonly.com).  I don't want
to clutter up Sun Rescue with this.

Hopefully we'll have something ready to hand out next week.

-James