Arc Forumnew | comments | leaders | submitlogin
2 points by akkartik 3148 days ago | link | parent

After an hour of working on it and fixing 2 bugs:

  (def nqueens (n (o queens))
    (if (< len.queens n)
      (let row (if queens (+ 1 queens.0.0) 0)
        (up col 0 n
          (let new-queens (cons (list row col) queens)
            (if (no conflicts.new-queens)
              (nqueens n new-queens)))))
      (prn queens)))

  ; check if the first queen in 'queens' lies on the same column or diagonal as
  ; any of the others
  (def conflicts (queens)
    (let (curr . rest) queens
      (or (let curr-column curr.1
            (some curr-column (map [_ 1] rest)))  ; columns
          (some [diagonal-match curr _] rest))))

  (def diagonal-match (curr other)
    (is (abs (- curr.0 other.0))
        (abs (- curr.1 other.1))))
The first 9 elements of http://oeis.org/A000170 match. 8 queens takes 1.5s; 9 queens takes 7s.

Woohoo, I am smarter than I was 20 years ago :) Though it does help to have a better language..



2 points by jsgrahamus 3148 days ago | link

Wow, that was quick: Time and lines of code.

Can you explain how it works?

I believe len.queens is (len queens).

What is:

  - (n (o queens))
  - queens.0.0
  - col
  - curr
  - some
  - (no [ is this the same as (~?]
When I ran it, I got

  arc> (nqueens 4)
  ((3 2) (2 0) (1 3) (0 1))
  ((3 1) (2 3) (1 0) (0 2))
  nil
  arc>
Is this in the form of ((col row) (col row) (col row) (col row))?

Thanks so much.

Steve

-----

1 point by akkartik 3148 days ago | link

Yeah, I should have explained more. I'd planned the results to be in the form:

  ((row col) (row col) (row col) ...)
Your version works just as well :) but the variable names might make a little more sense this way.

a) (o queens) means that queens is an optional argument. If I don't pass in a value it's nil by default. I could also have given it an explicit default by saying (o queens 42). You can read more about this in the tutorial: http://www.arclanguage.org/tut.txt. Worth a reread if it's been a while.

b) queens.0.0 expands to ((queens 0) 0). Which is the same as (car (car queens)). Just a quick way to pull out the first row, the row of the most recently added queen (since I'm adding queens on the left using cons).

c) col is just a variable name for the column in the above representation of queens. But perhaps you were asking about up. Try this out at your Anarki prompt:

  arc> (help up)  ; only in Anarki
  arc> (up col 0 8 (prn col))
d) some takes a predicate (function) and a list, and returns true if any of the elements of the list is satisfied by the predicate (function returns true). Check out (help some), as well as the tutorial above. One twist is that you can pass in any number/character/boolean as a predicate, and it's as if you're comparing with it. So I'm asking "have we already seen this column?" in this line:

  (some curr-column (map [_ 1] rest))
e) Yes, no is like ~ though not quite the same. It's just simple boolean negation. (no nil) is t, no on anything else is nil. ~ (complement) is slightly different, it operates on functions and makes them return their negation. So this relation always holds:

   (no f.x) <=> (~f x)
I could have written (no conflicts.new-queens) as (~conflicts new-queens).

Thanks for asking!

-----

2 points by jsgrahamus 3148 days ago | link

Thanks. Quite the learning experience for me.

-----

1 point by akkartik 3148 days ago | link

Oh, I missed a question.

curr in conflicts contains the first or most recently added queen. So in this line I'm 'unpacking' the list of queens into the first and the rest.

  (let (curr . rest)  queens
    ..)
Try it out for yourself at the arc prompt. Compare these two:

  (let (a b) '(1 2 3) b)
  (let (a . b) '(1 2 3) b)

-----