N queens

[Levente Mészáros]

Hi,

I'm looking for some tips for the following:

"
N Queens problem: consider an N by N chess board and print out the situatations where N queens on such a board cannot capture each other.

Here's my PLT scheme (swindle) program for this using swindle's 'amb' macros.

(define (queens n) 
  (print (queens-recursive n (list-of y [y <- '(amb) <- 1 .. n]) ())) (amb))

(define (queens-recursive n free-y-positions selected-positions)
  (if (= n 0) selected-positions 
      (let ((y (eval free-y-positions))) 
           (for-each (lambda (p) (amb-assert (not (or (= (- (car p) (cdr p)) (- n y)) (= (+ (car p) (cdr p)) (+ n y))))))
                 selected-positions)
           (queens-recursive (- n 1) (remove y free-y-positions) (append selected-positions (list (cons n y)))))))

(queens 6)

More info at http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html#node_chap_14.
"

"This would be a slate sketch to the problem, but I'm really unsure what is the nice way to solve it with slate?
Is there something for backtracking? Or is there another way to do it?"

"This would be the backtracking lib."
c@(Collection traits) amb
[...].

b@(Boolean traits) ambAssert
[
	b ifFalse: [{} amb.].
].

block ambCollect
[...].

"And the solution."
n@(Integer traits) queens
[
	(n queens: (1 numbersBetween: n) selectedPositions: {}) ambCollect.
].

x@(Integer traits) queens: freeYs@(Collection traits) selectedPositions: s@(Collection traits)
[| y |
	y: freeYs amb.
	s do: [| :each | (each ifCapture: {x y}) not ambAssert]
	(x - 1) queens: (freeYs copy remove: y) selectedPositions: (s copy append: {x y})
].

p1 ifCapture: p2
[].