New J challenge
Author Message
New J challenge

This one is a hoary old chestnut.

We want to solve the "8 queens" puzzle (place 8 queens on a chessboard
so that none attacks another).  The naive search space is 8!64 = 4.4e9
possible positions.  An easy optimization allows you to search the space

of permutations of 8 (!8 = 40320) since you know ahead of time each
queen must be in a different row and column.

Representing such a permutation as an index list we can print a solution

with the function bd :

bd 0 4 7 5 2 6 1 3
Q _ _ _ _ _ _ _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
_ _ _ _ _ _ Q _
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _

(this just happens to be a solution)

Now, it occurred to me after thinking about RH's latest puzzle that
if you had a function f that told you whether a given permutation was
a solution, the whole problem could be solved with :

qn 8
0 4 7 5 2 6 1 3

Your mission, should you decide to accept it:  write f.
It can be done tacitly (with no parens!), one function,
about the length of qn.

-j

Sat, 21 Apr 2001 03:00:00 GMT
New J challenge

Quote:

> This one is a hoary old chestnut.

:

> -j

p:0 4 7 5 2 6 1 3

bd:`0:(8 16#"_ ").[;;:;"Q"]/(!8),'2*  / 8x8 board

bd
Q _ _ _ _ _ _ _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
_ _ _ _ _ _ Q _
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _

dc:{[p;i;j]|/p[i+j]=p[i]+j,-j}          / left or right diagonal capture?

sat:{[p]&/{&/~dc[p;x]'1_!(#p)-x}'!#p}   / is p a solution to n queens?

sat p
1

For each row i, test rows j > i.  See if p[i]=p[j]+m,-m where m = j-i.

There is also a tricky solution (akin to the classic APL implementation of
the game of life) which sums the set of diagonal board shifts, looking for
totals > 1.  I.e. 8=left[b]+right[b], where b is a boolean representation
of the board.

sa

Wed, 25 Apr 2001 03:00:00 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages