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  
 
 [ 2 post ] 

 Relevant Pages 

1. JS-EAI with *JS*-callback

2. js.exception 3279.js

3. New J Challenge

4. SmallTalk vs C++ Challenge! 8/17/95 New York City

5. a new challenge

6. New Nudds Challenge: Write PASM

7. new challenge in prolog

8. NB. gray.js: a J verb that generates a grayscale postscript image from a 2d array

9. lapackTest.js

10. profile.js

11. J script file profile.js

12. JS valueOf() in RB ?

 

 
Powered by phpBB® Forum Software