Arc Forumnew | comments | leaders | submitlogin
2 points by jsgrahamus 3118 days ago | link | parent

Here is the whole program. I still need to check for reflections [if I already have (2 4 1 3), do not allow (3 1 4 2)].

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)


2 points by zck 3117 days ago | link

> I still need to check for reflections [if I already have (2 4 1 3), do not allow (3 1 4 2)].

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.

.

.

.

Sort them, then check for equality! I learned this when reading about anagrams.

-----

3 points by jsgrahamus 3117 days ago | link

So if two results were (2 4 1 3) and (3 1 2 4), both of them sort to (1 2 3 4) so delete one of them? Of course all of the results will sort to (1 2 3 4) for a 4x4 board.

Not sure I understand.

-----

2 points by zck 3117 days ago | link

Oh, you're right. I misunderstood what you meant by "reflections".

-----

2 points by akkartik 3118 days ago | link

Thanks! I think I'll try to solve it on my own without looking at yours in depth first. That might take me a few days. But feel free to keep asking questions in the meantime.

-----

2 points by jsgrahamus 3118 days ago | link

Thanks.

-----