[comp.lang.functional] a trivial question about n-queens

torbenm@gere.diku.dk (Torben [gidius Mogensen) (05/03/90)

ghawkins@vax1.tcd.ie writes:

>okay this is a bit of a trivial request so i'll keep it short:

>the standard solution to the nqueens proplem is usually just straight forward
>brut force recursion.

>has anyone got any nice ideas to optimize the performance of an nqueens
>program (best guessing before going for straight no frills recursion, say).

I once tried the following idea for quickly finding all solutions to the
8-queens problem. It used the fact that 8 is a power of 2, and is propably
not easy to generalize to arbitrary numbers.

The idea is to first generate the list of possible placements of a single
queen on a single 8x1 row.

Then produce the list of 8x2 boards produced by taking any two rows from
the above list, and include the pair in the new list if no queen in one
row threathen a queen in the other row.

Repeat the process by pairing 8x2 boards into 8x4 boards and 8x4 boards
into 8x8 boards, at each step removing illegal positions.

Programmed in Scheme, this method found the set ofall solutions much
faster than the backtracking approach.

A possible way to extend this to other n's, is to use overlap when pairing
nxm boards, and testing for equality in the overlap. This might actually
be an improvement over the previous method (I haven't tried it).

The method would then go like this:

First generate the list of possible placements of a single queen on a
single nx1 row.

Then produce nx2 boards as above.

Then produce nx(m+1) boards by pairing any two nxm boards with m-1 rows
overlap, taking only the pairs which agree in the overlapping rows, and
where the queen in the extreme left row does not threathen the queen in
the extreme right row.

Repeat this until an nxn board is achieved.


Using list-comprehensions it can be expressed like this (using a
single number to describe a row):

n-queens n = nq n 1 (nlist n [])

nlist 0 l = l
nlist n+1 l = nlist n ([n+1] : l)

nq n m b = if n=m then b
	          else nq n (m+1) (extend m b)

extend m b = [(hd r1) : r2 | r1 <- b; r2 <- b;
		             (r11<>r2l and 
			      abs(r11-r2l)<>m and 
			      (tl r1)=(butlast r2))
				where r11 = hd r1, r2l = last r2]

Hope this helps

	Torben Mogensen (torbenm@diku.dk)