8 Queens 
Author Message
 8 Queens


Quote:



Elegant.

An improved K solution, with comparable execution time:

     f:{~|/,//x[i+j]=/:x[i]+/:(j;-j:|1+!:'i:!#x)}

Combinators have the advantage over lambdas here.



Wed, 25 Apr 2001 03:00:00 GMT  
 8 Queens
It was gratifying to see several responses to my 8 queens challenge.
The problem was to write f such that


   qn 8
0 4 7 5 2 6 1 3

The solution I had in mind when writing was


This has a running time of 109 seconds.  (It swaps horribly
(on 64 meg!) so it may be faster on a bigger system)
(I mean of course the time for qn 8 given that f)

I also got an email response from Mike Day.  He had a better
algorithm, if slightly longer, in


this runs in 24 seconds.  I though I might improve it, and came up with


which runs in under 5 seconds.

Moral: algorithm counts, even in tacit one-liners.  What's more,
implementation counts.  Mike's algorithm is linear where mine was,
in search of ultimate code compactness, quadratic.  I frankly don't
understand why the reimplementation was that much faster.  Boxing
shouldn't take *that* much overhead.

-j



Thu, 26 Apr 2001 03:00:00 GMT  
 8 Queens

...

Quote:
>Elegant.
>An improved K solution, with comparable execution time:

...

Thanks!

What actually bugs me slightly, is that elegance is misleading here.
As noted, that one ran in 5 seconds on my machine.  RH's
comparable algorithm, q1, ran in 10.  RH's second version, q2,
an iterative script 15 lines long, ran in 0.044 seconds, i.e.,
2 orders of magnitude faster (and returns all the solutions,
not just the first).

Oh well.

-j



Thu, 26 Apr 2001 03:00:00 GMT  
 8 Queens

Quote:


> ...
> >Elegant.

> >An improved K solution, with comparable execution time:
> ...

> Thanks!

> What actually bugs me slightly, is that elegance is misleading here.
> As noted, that one ran in 5 seconds on my machine.  RH's
> comparable algorithm, q1, ran in 10.  RH's second version, q2,
> an iterative script 15 lines long, ran in 0.044 seconds, i.e.,
> 2 orders of magnitude faster (and returns all the solutions,
> not just the first).

I'll have to study the algorithm.  I consider my approach "naive",
although it does generate all the solutions.

By the way, here's the "Game of Life" style approach I mentioned
earlier.  It takes about 15 seconds on my machine to generate all
solutions for n=8.

        b:{x=\:!#x}                     / board for permutation x
        d:1_-1_                         / 1 drop -1 drop of



        t:{~|/,//(x&y)|x&z}             / truth condition

        q'np 8                          / solve for n=8

K doesn't have a permutation primitive, so you need to write one
(np 8 runs in a couple of seconds -- I'm sure it can be improved).

Even with K's restricted composition facility (essentially, trains
of monads or trains of monads with a final dyad), the result is *nearly*
variable-free.

- Show quoted text -

Quote:

> Oh well.

> -j



Thu, 26 Apr 2001 03:00:00 GMT  
 8 Queens


Quote:
> understand why the reimplementation was that much faster.  Boxing
> shouldn't take *that* much overhead.

Well, in a non-compiled environment, it either DOES take that much
overhead (or the other implementors are keeping mum!) except in very
special cases. Each enclosed element requires its own descriptor,
memory management, and descriptor maintenance. Other choices
require lookahead, conservative design, or compilation techniques.

The problem is that lookahead is extremely expensive
in an interpreter ("Should I save this information because I might be
able to use it later?") and conservativism ("I'll save this information
because there might a chance that I can exploit it in the future.")
is even more expensive.  (See citations in my thesis if you want details on

this.)

I learned this the hard way when I first
designed and implemented support for enclosed (aka nested/boxed arrays
aka recursive data structures) in SHARP APL in the late 1970's).
At that time, I still thought that the performance of single primitives
on large arrays was material to the performance of entire applications.
It was only much later that measurements revealed that small array
performance was all.

I implemented enclose using a Patricia-like dictionary (denoted
coadunate representation) so that if you
did:   A  {is} ({enclose} 'abcd'),{enclose}  'abcd'
  you would end up with only one copy of  "abcd" in the dictionary,
  and A would comprise (essentially) a vector of two pointers to
  the same element: "abcd".

The design assumptions behind this decision were (at least) twofold:
   - storage was expensive, so saving workspace was A Good Idea.
     At the time, the IBM PC was not yet available, and memory probably
     cost at least a dollar a byte.
   - Perceived uses of enclosed arrays suggested that the performance of
     non-linear-when-implemented-poorly primitives (such as set membership
     and indexof) would be critical for many applications.

Hence, having a single place to store each array would map
set membership and indexof into integer-mode operations. Swell,
I thought!

However, measurements of real (although obviously naive and simple)
applications that grew out of this early implementation made it
apparent that the cost of coadunate representation was simply not
born out in reality. The best thing to do was to make enclose/disclose
and their friends as simple and fast as possible. You can see these
same criteria coming out in other areas in my thesis in work done
by researchers in several areas.

Compilation techniques offer a strong possibility here, IF we can
perform dataflow analysis and let static analysis determine the
type and rank of EACH enclosed element. This is why I keep harping
on the utility of declarations and Structs.

Bob-who-gave-up-on-trying-to-make-interpreters-compete-with-compilers



Thu, 26 Apr 2001 03:00:00 GMT  
 8 Queens

Quote:

> What actually bugs me slightly, is that elegance is misleading here.
> As noted, that one ran in 5 seconds on my machine.  RH's
> comparable algorithm, q1, ran in 10.  RH's second version, q2,
> an iterative script 15 lines long, ran in 0.044 seconds, i.e.,
> 2 orders of magnitude faster (and returns all the solutions,
> not just the first).

Thanks for pointing me in the right direction (or at least a better
one).  My strategy for generating exactly the set of solutions is:

        place a queen in column j of row 0
        in row 1, mark:
          vertical column j
          left diagonal column j-1
          right diagonal column j+1

        place a queen in an unmarked column k of row 1
        in row 2, mark:
          vertical columns j, k
          left diagonal columns j-2, k-1
          right diagonal colunms j+2, k+1

        etc.

Here is the code, generalized for n queens:

        qn:{[n],/nq'[n;w-1;w+1]w:!n}                    / base step

        nq:{[n;l;r;v]                                   / recursion step
         :[n=#v
          ,v
          ,/{nq[n;-1+l,x;1+r,x]v,x}'(!n)_dvl v,l,r]}

        m:qn 8                                          / all 8-queen solutions

        \t qn 8
      130

Quote:

> Oh well.

> -j



Sun, 29 Apr 2001 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Queens Problem -- A simple look

2. Queens Problem

3. Updating AST's in a functional language (was: 8-queens contest)

4. 8 queens: a little contest

5. eight queens

6. Updating AST's in a functional language (was: 8-queens contest)

7. a trivial question about n-queens

8. FUNNY Eight Co-Queens

9. n-queens non-isomorphic solutions.

10. N-queens problem

11. Non-working solution to the N-Queens problem

12. Urgent Help with N-Queens Problem

 

 
Powered by phpBB® Forum Software