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-----