Arc Forumnew | comments | leaders | submitlogin
6 points by cchooper 6105 days ago | link | parent

Here's an implementation of the n queens algorithm in the wikipedia article:

  (def rot ((x . y)) (join y `(,x)))

  (def nqueens (n)
    (withs (m (mod n 12) r (range 1 n) od (keep odd r) cod (cddr od) s '(1 3) cods (join cod s) ev (keep even r))
      (join (if (pos m '(3 9)) (rot ev) ev)
            (case m
              8 (apply join (map rev (pair od)))
              2 (join (rev s) (rot cod))
              3 cods
              9 cods
              od))))
Arc makes it very nice to implement, although it still bugs me that you can't use join to add a single item to the end of a list (which I've wanted to do a few times already). My preferred semantics:

  (join 1 '(2 3 4) 5 '(6 7 8) 9)
  => (1 2 3 4 5 6 7 8 9)
Edit: made it slightly shorter.


3 points by map 6105 days ago | link

To simulate

  (join 1 '(2 3 4) 5 '(6 7 8) 9)
one could do

  (flat:list 1 '(2 3 4) 5 '(6 7 8) 9)
Of course, you're out of luck if you have nested lists.

-----

1 point by lojic 6104 days ago | link

When I run this via (nqueens 8), I only get one output:

  arc> (nqueens 8)
  (2 4 6 8 3 1 7 5)  
  arc>
There should be 92 solutions displayed.

-----

1 point by cchooper 6104 days ago | link

This algorithm only finds one correct solution for each n.

-----

1 point by map 6104 days ago | link

The wikipedia algorithm only generates one solution.

-----

1 point by lojic 6104 days ago | link

The challenge is to produce all 92 solutions as the Ruby code does in the OP. I linked to wikipedia for the description of the problem, not the algorithm.

I also showed the ellided output for clarification.

-----

1 point by cchooper 6104 days ago | link

I was doing the n queens challenge on Wikipedia because someone had already posted a solution to your challenge.

-----

1 point by map 6105 days ago | link

Ruby version of the wikipedia algorithm.

  class Array
    def rot
      push( shift )
    end
  end

  nqueens = proc{|n|
    odds, evens = (1..n).partition{|x| x % 2 > 0 }
    case n % 12
      when 2
        odds = [3,1] + odds[3..-1] + [5]
      when 3, 9
        odds.rot.rot
        evens.rot
      when 8
        d = -2
        odds.map!{|x| d *= -1; x + d}
    end
    p evens + odds
  }

  nqueens[8]

-----

2 points by map 6104 days ago | link

Shorter:

  class Array
    def rot
      push( shift )
    end
  end

  proc{|n| p ((1..n).partition{|x|x%2>0}.inject{|o,e|
    e + case n % 12
      when 2
        [3,1]+o[3..-1]+[5]
      when 3,9
        o.rot.rot;e.rot;o
      when 8
        d=-2;o.map{|x| x + d*=-1} end})}[ 8 ]

-----

1 point by cchooper 6104 days ago | link

Getting shorter:

  (def rot ((x . y)) (join y `(,x)))

  (def nqueens (n)
    (withs (m (mod n 12) r (range 1 n) od (keep odd r) cod (cddr od) s '(1 3) ev (keep even r))
           (if (join (pos m '(3 9)) (rot ev) (join cod s))
               (join ev (case m 8 (apply join (map rev (pair od)))
                                2 (join (rev s) (rot cod))
                                od)))))
The things Arc is missing from Ruby are partition and testing against multiple objects in a case. With those it would become:

  (def rot ((x . y)) (join y `(,x)))

  (def nqueens (n)
    (withs ((od ev) (part odd (range 1 n)) cod (cddr od) s '(1 3))
           (join ev (case (mod n 12) 8    (apply join (map rev (pair od)))
                                     2    (join (rev s) (rot cod))
                                     3, 9 (do (zap (rot ev)) (join cod s))
                                     od))))

-----

1 point by map 6104 days ago | link

Oops. Both of my Ruby programs above lack a default for the case statement. E.g., the shorter program needs after the last "when":

      else
       o

-----

1 point by map 6104 days ago | link

  (def rot ((x . y)) (join y `(,x)))


  (def nqueens (n)
    (withs (r (range 1 n) o (keep odd r) e (keep even r) m (mod n 12))
      (if (pos m '(3 9)) (= m -1))
      (join (if (is m -1) (rot e) e)
        (case m
          2 (join '(3 1) (cut o 3 -1) '(5))
          8 (flat:map rev (pair o))
          -1 (rot:rot o)
          o))))

-----

2 points by cchooper 6104 days ago | link

Instead of (= m -1) you could use (nil! m) and then test it with (no m). That's 2 fewer atoms!

-----

2 points by kens1 6104 days ago | link

Is nil! an Anarki thing? (wipe m) is the Arc expression to set m to nil. (And (assert m) sets m to t. Assert tops my list of confusingly named functions.)

-----

2 points by nex3 6104 days ago | link

No, nil! was just the old name for wipe.

-----

1 point by map 6104 days ago | link

Good idea. But "(nil! m)" gives me an error. After making the other changes you suggested, it occurred to me to combine the two "if" clauses into one.

  (def rot ((x . y)) (join y `(,x)))
  (def nqueens (n)
    (withs (r (range 1 n) o (keep odd r) e (keep even r) m (mod n 12))
      (join (if (pos m '(3 9))(or wipe.m rot.e) e)
        (case m
          2 (flat:list 3 1 (cut o 3 -1) 5)
          8 (flat:map rev pair.o)
          nil (rot:rot o)
          o))))
Edit: used "wipe" as suggested below.

Edit: using "flat:list" for case 2.

Edit: replaced (wipe m) with wipe.m, etc.

-----