Nqueens with threads

[Zosden]

If your not familiar with nqueens then wiki it. What if you made a class that implmented runnable and had a thread in it then us used that class to work as a layer of the nqueens problem this class would in turn call another class that would work on the next level. Would this make the solution even faster or what. If yes then why not use such solutions in advanced algorithms today. If not then why isn't it faster.

[Nicholas Jordan]

This is called parallelization, to do that - you have to be able to split the problem in divisional aspects such that no two threads are trying to "work on the same part of the problem" .. trying to dissect exactly what that means is how one would parallelize N-Queens or Ant Colony Optomization or any of a broad class of problems that can be sifted on the single factor of the ability to compartmetnalize the logic.

Java has built in synchronization primitives, and in general they are implemented well except that the HotSpot has one or two misplaced register stores that cross subtle boundaries because of the wording in the Spec.

Google for Java Real Time Specification, your work would be welcome.

[Fubarable]

Wouldn't this also depend upon whether or not the computer running the code had multiple processors, and whether or not the JVM would split the different threads amongst the different processors. If all done on one processor, I don't see how multiple threads would give you any gain at all.

[Nicholas Jordan]

Threading on uniprocessor machines has proven gains in io, otherwise it is as you state. Technically, due to L-2 writebacks there may be minor gains avaliable, in a core loop for a heavy load, the gain may be measurable ~ but it would depend totally on a JVM implementation on a paticular hardware and OS and ( not to dismiss the depth of your observation ) also depend on weather patterns, operator luck and so on.

If the N-Queens has a layerable aspect, I would naturally have a Threading solution as a goal, but making a single class Runnable then getting layers out of it does not sound to me like an effective approach. We could consider making a class that takes an OrderedPair then doing a foreach{new Runnable();} as todays machines have ablilities to do deep branch prediction and speculative instruction execution that could outrun L-2.

Mind Boggling to say the least. I like to have my mind boggled.