Q Solutions

The N-Queens Puzzle

This puzzle has validity in CSP research for two reasons:

  1. It has a large graph space.
  2. It has a large number of possible solutions.
To find one solution is easy, to efficiently find all solutions for a given 'n' is much harder.
Ideally the search needs to be O(logN) rather than exponential.

The goal is to find a way of getting TCL to find solutions for N > 1000 efficiently. As well as research new search strategies to compute all solutions efficiently.

I wrote the Original n-Queens puzzle puzzle as a comparison to the original that I wrote many years ago in C to compare the two languages.

In this next version n-Queens puzzle using propagators, I used propagators to try and speed up the search. Unfortunately the time spent propagating is as long as the original search so there is not much speed up to be gained even though it tries only half the number of nodes as the original.
To get an extra speed up I added a random search order to each rank.

Compared with the C version that can use bitmaps to represent the available choices, TCL's use of lists is much slower, although the C versoin is limited to the number of bits in a word.
Tcl could use wide integers to do this, but this cannot be applied to values of N greater than 64.

Another algorithm needs to be found to improve the propagation of moves.

Note
The standard solution for large N is to start with the middle of the board and work outwards. This is too much like cheeting so has not been implemented in these versions.
It would also be good to test the original plus random positioning vs the propagotor version to see if there is much gained in the propagator.

In conclusion

Tcls lack of datastructures other than lists and associate arrays limits the speed of processing this type of problem.