Arc Forumnew | comments | leaders | submitlogin
Arc challenge: 8 Queens Problem
10 points by lojic 4417 days ago | 40 comments
I'm curious how well Arc will fare (size, readability) on the "8 Queens" problem. For comparison, here's a naive version I coded in Ruby:

  def valid? stack
    q2 = stack.length - 1
    (0..stack.length-2).each do |q1|
      return false if stack[q1] == stack[q2] || (q1-q2).abs == (stack[q1]-stack[q2]).abs
    end
  end

  def queens stack, n
    if n == 8
      puts "[ #{stack.join(', ')} ]"
    else
      (1..8).each do |rank|
        stack.push(rank)
        queens(stack, n+1) if valid?(stack)
        stack.pop
      end
    end
  end

  queens [], 0
Which produces the output:

  [ 1, 5, 8, 6, 3, 7, 2, 4 ]
  [ 1, 6, 8, 3, 7, 4, 2, 5 ]
  [ 1, 7, 4, 6, 8, 2, 5, 3 ]
  [ 1, 7, 5, 8, 2, 4, 6, 3 ]
  [ 2, 4, 6, 8, 3, 1, 7, 5 ]
  ...
  [ 8, 3, 1, 6, 2, 5, 7, 4 ]
  [ 8, 4, 1, 3, 6, 2, 7, 5 ]


6 points by cchooper 4417 days ago | link

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 4416 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 4416 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 4416 days ago | link

This algorithm only finds one correct solution for each n.

-----

1 point by map 4416 days ago | link

The wikipedia algorithm only generates one solution.

-----

1 point by lojic 4416 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 4416 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 4416 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 4416 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 4416 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 4416 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 4416 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 4416 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 4416 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 4415 days ago | link

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

-----

1 point by map 4415 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.

-----

2 points by lojic 4416 days ago | link

I took sacado's code and tweaked it a bit (Ruby's push appends and Arc's push prepends). Here's the result. If someone can get rid of my joinstr function and make the prn line closer to the Ruby version in conciseness, then I think Arc does pretty well.

For this challenge, it's important to have the output match exactly - that's why the rev is necessary and the complicated print. I do string interpolation all the time in Ruby, so I wanted to see how easy/hard it was in Arc to produce lines such as [ 1, 5, 8, 6, 3, 7, 2, 4 ]

I might as well limit the code to ArcN also.

I think the following may be the only working version of Arc code that passes this challenge so far.

Having to use point is a bit awkward, but not too bad. I particularly like the function composition such as abs:- and the more concise len.stack notation. The [ string sep _ ] notation is definitely a winner also. I'm pretty pleased with the core language so far - kudos to pg & rm.

  (def valid? (stack)
    (let q2 0
      (point return
             (each q1 (range 1 (- len.stack 1))
                   (if (or (is stack.q1 stack.q2)
                           (is (abs:- q1 q2) (abs:- stack.q1 stack.q2)))
                       (return nil)))
             t)))

  (def joinstr (lst (o sep " "))
    (if lst
        (string (car lst) (apply string (map [string sep _] (cdr lst))))
        ""))

  (def queens (stack n)
    (if (is n 8)
        (prn "[ " (joinstr (rev stack) ", ") " ]")
        (each rank (range 1 8)
              (push rank stack)
              (if (valid? stack)
                  (queens stack (+ n 1)))
              (pop stack))))

  (queens '() 0)
---

  arc> (queens '() 0)
  [ 1, 5, 8, 6, 3, 7, 2, 4 ]
  [ 1, 6, 8, 3, 7, 4, 2, 5 ]
  [ 1, 7, 4, 6, 8, 2, 5, 3 ]
  [ 1, 7, 5, 8, 2, 4, 6, 3 ]
  [ 2, 4, 6, 8, 3, 1, 7, 5 ]
  ...
  [ 8, 3, 1, 6, 2, 5, 7, 4 ]
  [ 8, 4, 1, 3, 6, 2, 7, 5 ]

-----

2 points by map 4415 days ago | link

  (def valid? (stack)
    (let i 0
      (if (or (pos stack.0 cdr.stack)
              (some (fn(x)(++ i)(is i (abs:- x stack.0))) cdr.stack))
        nil
        t)))

  (def queens (stack n)
    (if (is n 8)
      (and (prall rev.stack "[ ") (prn " ]"))
      (for rank 1 8
        (push rank stack)
        (if (valid? stack)
            (queens stack (+ n 1)))
        (pop stack))))

  (queens '() 0)

-----

2 points by almkglor 4415 days ago | link

  (def valid? (stack)
    (let i 0
      (if (or (pos stack.0 cdr.stack)
              (some [do (++ i) (is i (abs:- _ stack.0))] cdr.stack))
        nil
        t)))

-----

1 point by map 4415 days ago | link

  (def valid? (stack)
    (let i 0
      (if (or (pos stack.0 cdr.stack)
              (some [is ++.i (abs:- stack.0 _)] cdr.stack))
        nil
        t)))

  (def queens (stack n)
    (if (is n 8)
      (do (prall rev.stack "[ ") (prn " ]"))
      (for rank 1 8
        (push rank stack)
        (if (valid? stack)
            (queens stack (+ n 1)))
        (pop stack))))

  (queens '() 0)

-----

1 point by lojic 4415 days ago | link

Nice job - thx.

-----

1 point by almkglor 4416 days ago | link

  arc> (help prall)
  (from "arc.arc")
  [fn]  (prall elts (o init ) (o sep , ))
   Prints several arguments with an initial header and separated by a
      given separator. 
Above function also exists in Arc2.

Instead of (point return ...(return ...)) try using (catch ...(throw ...)).

Final nitpick: I think it's rtm, not rm, although, well, I dunno. ^^

-----

1 point by lojic 4415 days ago | link

Have you tried prall to print the output in the OP? It's awkward.

-----

1 point by map 4415 days ago | link

  arc> (help prall)
  Error: "reference to undefined identifier: _help"

-----

1 point by nex3 4415 days ago | link

help is a macro defined on Anarki.

-----

2 points by partdavid 4416 days ago | link

I'm not thrilled with this escript (Erlang), namely because Erlang provides a perfectly nice way to format the resulting lists but lojic dictates the output must be exactly the same, thus the fairly ugly business in main():

  #!/usr/bin/env escript
  
  -import(lists, [seq/2, reverse/1]).
  
  main([]) ->
     lists:foreach(fun(L) ->
                         io:format("[ ~s ]~n",
                                   [string:join(
                                      [ integer_to_list(I)
                                        || I <- L ], ", ")])
                   end, queens([], 0)).
                         
  
  threatens(Q, _, [Q|_], _) -> true;
  threatens(_, _, [], 0) -> false;
  threatens(Q, I, [Q2|Queens], I2) ->
     if
        abs(I - I2) =:= abs(Q2 - Q) -> true;
        true -> threatens(Q, I, Queens, I2 - 1)
     end.
  
  is_valid([Q|Queens]) ->
     TL = length(Queens),
     not threatens(Q, TL + 1, Queens, TL).
  
  queens([], _) -> queens([ [X] || X <- seq(1, 8) ], 8);
  queens(Tree, 1) -> Tree;
  queens(Tree, Place) ->
     queens([ [N|Node] || N <- seq(1, 8),
                          Node <- Tree,
                          is_valid([N|Node]) ],
            Place - 1).
Note that threatens/4 there does short-circuit and avoids evaluating needless cases, without "return."

-----

2 points by lojic 4415 days ago | link

"but lojic dictates"

I prefer the word encourage :) I know it's nitpicky, but the idea was to not simply use a native print. Of course, had I required the 'pp' Ruby lib, I could have just said:

  pp stack   # => [ 1, 2, 3, ... , 8 ]

-----

2 points by partdavid 4415 days ago | link

I liked the pun in "lojic dictates", though :)

My point was more that having to put spaces in meant doing it myself rather than just io:format("~p~n", [Answer]).

-----

1 point by lojic 4415 days ago | link

Ah, I missed the pun - nice.

Your point is my point. I wanted to see how well Arc handles formatting something that didn't fit neatly into an expected pattern.

Ruby has several formatting techniques that are quite nice:

1) String interpolation. You can insert an expression into a spring by using #{expression}

2) String formatting. You can use sprintf style patterns in strings via format or the % operator. For example:

  puts "%4.1f hours" % hours
  puts "%4.1f hours and %4.1f minutes" % [hours, minutes]
So, does Arc have format now?

-----

2 points by sacado 4417 days ago | link

  (def valid (stack)
    (with (q2 (- len.stack 1)
           result t)
      (each q1 (range 0 (- len.stack 2))
        (= result (and result
                       (isnt stack.q1 stack.q2)
                       (isnt (abs:- q1 q2) (abs:- stack.q1 stack.q2))))))

  (def queens (stack n)
    (if (is n 8)
      (prn stack)
      (each rank (range 1 8)
        (push rank stack)
        (if (valid stack)
          (queens stack (+ n 1)))
        (pop stack))))

  (queens '() 0)
It's a naïve implementation of what you wrote in Ruby. It should work, however I didn't try it. It is not really optimal, as there is no return in my code. Anyway, it's quick and dirty...

-----

2 points by almkglor 4416 days ago | link

If you're on arc-wiki, you can use the breakable: modifier to create a breakable with/let:

  (def valid (stack)
    (breakable:let q2 (- len.stack 1)
      (each q1 (range 0 (- len.stack 2))
        (if (or (is stack.q1 stack.q2) (is (abs:- q1 q2) (abs:- stack.q1 stack.q2)))
          (break nil)))
      (break t)))
edit: BTW, your 'valid function didn't actually return the result ^^

-----

1 point by sacado 4416 days ago | link

oh, right, each returns nil...

Thks for the "breakable" info

-----

2 points by lojic 4416 days ago | link

Is there a way to return in Arc?

-----

2 points by sacado 4416 days ago | link

Sure, ccc is here for that. Let's say we want the equivalent of this Python code :

  def a:
    for i in (1, 2, 3):
      if i < 2:
        return i

    return None
It can be written this way in Arc :

  (def a (return)
    (each i '(1 2 3)
      (if (< i 2)
        (return i)))
    nil)

  arc> (ccc a)
  1
To those who don't know ccc : in this code, return is not a defined macro or function, it is the current continuation, waiting for a value. We could have called it another way, k for example.

Once you "throw" it a value (i in this case), it's happy and goes on to the next calculation. (ccc a) thus tells to perform a and, once the return parameter is called, exit a and go back to the REPL (with the specified value).

-----

2 points by lojic 4416 days ago | link

Thanks for the quick reply. That seems like an awkward way to accomplish a simple thing - Python & Ruby win on this IMO.

I submitted a new article ( http://arclanguage.com/item?id=4431 ) on the topic. It might be good to re-post your comment there and have followups on that thread.

-----

2 points by almkglor 4416 days ago | link

better is point:

  (def a ()
    (point return
      (each i '(1 2 3)
        (if (< i 2)
          (return i)))
      nil)))
That said, the breakable: macro simply compiles down to (point break ...)

-----

1 point by lojic 4416 days ago | link

My apologies.

Apparently folks have fixated on a particular algorithm in the wikipedia article. I only linked there for a general description of the problem. Instead, I should have simply said, "write a program that produces all the solutions to the problem of placing 8 queens on a chess board so that no queen is attacking any other queen and prints the solutions as follows (i.e. the output in the OP)"

I'm not too excited about an algorithm that only finds one solution, although it is clever.

-----

2 points by lojic 4417 days ago | link

Here's a description of the problem:

http://en.wikipedia.org/wiki/Eight_queens_puzzle

-----

1 point by map 4416 days ago | link

A bit shorter:

  def valid? stack
    q2 = stack.size - 1
    q2.times { |q1|
      return nil if stack[q1] == stack[q2] or (q1-q2).abs == (stack[q1]-stack[q2]).abs
    }
  end

  def queens stack, n
    if n == 8
      p stack
    else
      (1..8).each do |rank|
        stack.push(rank)
        queens(stack, n+1) if valid?(stack)
        stack.pop
      end
    end
  end

  queens [], 0

-----

2 points by mcoles 4416 days ago | link

Does anyone know why that optimised heuristic/algorithm actually works? i.e. n mod 12 and all that

-----