Consider this code:

    arc> (let result 0 (let result 2 (= result 3)) result)
    0

  (let (diagonals result row) (get-next-row board-size diagonals result)
    ..)

  (= x 3 y 4)
  (+ x y)

  (let (x y) '(3 4)
    (+ x y))

Ideas?

Thanks, Steve

---

  (def nqueens (board-size)
    (with (diagonals nil finished nil jsg 0 result '(0) row nil total 0)
	  (while (~ finished)
	         (let (diagonals2 result2 row2 total2)
		   (get-next-row board-size diagonals result total)
	           (if row2
		      (if (is (len result2) board-size)
                        (do
			  (let (diagonals3 result3 total3)
			    (print-result diagonals2 result2 total2)
			    (do
			      (= diagonals2 diagonals3)
			      (= result2 result3)
			      (= total2 total3))))
		        (= result2 (goto-next-column result2)))
		      (if (is (len result2) 1)
		        (= finished t)
		        (let (diagonals3 result3) 
		          (goto-previous-column diagonals2 result2)
			  (= diagonals2 diagonals3)
	  		  (= result2 result3))))
		   (= diagonals diagonals2)
		   (= result result2)
		   (= row row2)
		   (= total total2)))
	  (string "Number of results: " total)))

   (do
     (let (diagonals2 result2 total2)
  	(print-result diagonals2 result2 total2)
  	(= diagonals diagonals2 result result2 total total2)))

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

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 (~?]

  arc> (nqueens 4)
  ((3 2) (2 0) (1 3) (0 1))
  ((3 1) (2 3) (1 0) (0 2))
  nil
  arc>

Thanks so much.

  ((row col) (row col) (row col) ...)

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

  (some curr-column (map [_ 1] rest))

   (no f.x) <=> (~f x)

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

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

  (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 queens2 (max size stack)
    (if (is size max)
      (and (prall rev.stack "[ ") (prn " ]"))
      (for rank 1 max
        (push rank stack)
        (if (valid? stack)
            (queens2 max (+ size 1) stack))
        (pop stack))))

  (def queens (max)
     (with (size 0 stack nil)
        (queens2 max size stack)))

  arc> (queens 4)
  Error: "_R: undefined;\n cannot reference undefined identifier"
  arc>

Also, what's that i variable doing in valid?? I don't understand how valid? works..

  (def get-next-row (board-size diagonals result total)
       (with (column (len result) finished nil new-diagonals nil row (car (rev result)))
         (while (and (~ finished) (~ (> (++ row) board-size)))
	        (if (~ (mem row result))
	  	  (do
		    (= new-diagonals (calculate-diagonals board-size column row))
		    (if (and (~ (mem (car new-diagonals) diagonals))
			     (~ (mem (car (rev new-diagonals)) diagonals)))
		      (do
		        (= finished t)
		        (= result (rev (cons row (cdr (rev result)))))
		        (for i 1 2 (push (pop new-diagonals) diagonals)))))))
         (list diagonals result (if finished row nil) total)))

As I said, I'm using this to learn arc. So if y'all have any suggestions, I'm all ears :-)

  ;; nqueens - Solve n queens problem
  ;;
  (def calculate-diagonals (board-size column row)
       (let new-diagonals nil
         (if (is row 1)
  	   (push column new-diagonals)
  	   (if (is column 1)
  	     (push row new-diagonals)
  	     (push (+ column row -1) new-diagonals)))
         (if (is row 1)
  	   (push (- column board-size 1) new-diagonals)
  	   (if (is column 1)
  	     (push (- 1 board-size row) new-diagonals)
  	       (push (- column board-size row) new-diagonals)))
         new-diagonals))
  
  (def get-next-row (board-size diagonals result total)
       (with (column (len result) finished nil new-diagonals nil row (car (rev result)))
         (while (and (~ finished) (~ (> (++ row) board-size)))
  	      (if (~ (mem row result))
  		(do
  		  (= new-diagonals (calculate-diagonals board-size column row))
  		  (if (and (~ (mem (car new-diagonals) diagonals))
  			   (~ (mem (car (rev new-diagonals)) diagonals)))
  		    (do
  		      (= finished t)
  		      (= result (rev (cons row (cdr (rev result)))))
  		      (for i 1 2 (push (pop new-diagonals) diagonals)))))))
         (list diagonals result (if finished row nil) total)))
  
  (def goto-previous-column (diagonals result)
       (list (cdr (cdr diagonals)) (rev (cdr (rev result)))))
  
  (def goto-next-column (result)
     (rev (cons 0 (rev result))))
  
  (def print-result (diagonals result total)
       (prn result)
       (let (diagonals result) (goto-previous-column diagonals result)
         (list (cdr (cdr diagonals)) result (++ total))))
  
  (def nqueens (board-size)
    (with (diagonals nil finished nil jsg 0 result '(0) row nil total 0)
  	(while (~ finished)
  	       (let (diagonals2 result2 row2 total2)
  		 (get-next-row board-size diagonals result total)
  		 (= diagonals diagonals2 result result2 row row2 total total2)
  		 (if row
  		    (if (is (len result) board-size)
                      (do
  			(let (diagonals2 result2 total2)
  			  (print-result diagonals2 result2 total2)
  			  (= diagonals diagonals2 result result2 total total2)))
  		      (= result (goto-next-column result)))
  		    (if (is (len result) 1)
  		      (= finished t)
  		      (let (diagonals2 result2) 
  		        (goto-previous-column diagonals result)
  			(= diagonals diagonals2 result result2))))))
  	(prn "Number of results: " total))
    nil)

There's a cool technique I read about to solve problems like this. I'll put it a few lines down in case you want to think about it yourself.

.

.

.