How to solve n-queens in scheme

Question

I'm trying to solve the n-queens problem in scheme. I was told by my professor to use a single vector as the chess board where the ith element of the vector represents the ith column of the board. The value of that element is the row on which sits a queen, or -1 if the column is empty. So, [0 1 2 -1 -1] has two columns with no queen and three queens placed illegally. When I run this code: (place-n-queens 0 4 #(-1 -1 -1 -1)) I get #(0 1 2 3) which obviously has all four queens placed illegally. I think the issue is that I don't check enough things in the cond in place-queen-on-n but I'm not sure what to add to solve the issue of getting queens on the same diagonal.

(define (return-row vector queen) 
  (vector-ref vector (return-col vector queen)))
(define (return-col vector queen) 
  (remainder queen (vector-length vector)))

(define (checkrow vector nq oq) 
  (cond
   ((= (vector-ref vector nq) -1) #f)
   ((= (vector-ref vector oq) -1) #f)
   (else (= (return-row vector nq) (return-row vector oq)))))
(define (checkcol vector nq oq) 
  (= (return-col vector nq) (return-col vector oq)))
(define (checkdiagonal vector nq oq)
  (cond 
    ((= (vector-ref vector nq) -1) #f)
    ((= (vector-ref vector oq) -1) #f)
    (else (= (abs (- (return-row vector nq) (return-row vector oq)))
      (abs (- (return-col vector nq) (return-col vector oq)))))))

(define (checkdiagonalagain vector r c oq)
   (= (abs (- r (return-row vector oq)))
    (abs (- c (return-col vector oq)))) )
(define (checkrowagain vector r oq)
   (= r (return-row vector oq)))

(define (checkinterference vector nq oq)
   (or (checkrow vector nq oq) (checkcol vector nq oq) (checkdiagonal vector nq oq)))

(define (place-queen-on-n vector r c)
 (local ((define (foo x)
        (cond
          ((checkrowagain vector r x) -1)            
          ((= c x) r)
          ((checkinterference vector c x) -1)
          ((map (lambda (y) (eq? (vector-ref vector x) y)) 
                (build-list (vector-length vector) values)) (vector-ref vector x))
          ((eq? (vector-ref vector x) -1) -1)
          (else -1))))
 (build-vector (vector-length vector) foo)))

(define (place-a-queen vector)
 (local ((define (place-queen collist rowlist)
        (cond
          ((empty? collist) '())
          ((empty? rowlist) '())
          (else (append (map (lambda (x) (place-queen-on-n vector x (car collist))) rowlist)
                        (try vector (cdr collist) rowlist)))
          )))
 (place-queen (get-possible-col vector) (get-possible-row (vector->list vector) vector))))

(define (try vector collist rowlist)
 (cond
  ((empty? collist) '())
          ((empty? rowlist) '())
 (else (append (map (lambda (x) (place-queen-on-n vector x (car collist))) rowlist)
    (try vector (cdr collist) rowlist)))))

(define (get-possible-col vector)
 (local ((define (get-ava index)
        (cond
          ((= index (vector-length vector)) '())
          ((eq? (vector-ref vector index) -1)
           (cons index (get-ava (add1 index))))
          (else (get-ava (add1 index))))))
  (get-ava 0)))

;list is just vector turned into a list
(define (get-possible-row list vector)
  (filter positive? list)
  (define (thislist) (build-list (vector-length vector) values))
  (remove* list (build-list (vector-length vector) values))
)

(define (place-n-queens origination destination vector)
 (cond
  ((= origination destination) vector)
  (else (local ((define possible-steps
                (place-n-queens/list (add1 origination)
                                     destination
                                     (place-a-queen vector))))
        (cond
          ((boolean? possible-steps) #f)
          (else possible-steps))))))

(define (place-n-queens/list origination destination boards)
 (cond
  ((empty? boards) #f)
  (else (local ((define possible-steps 
                (place-n-queens origination destination (car boards))))         
        (cond
          ((boolean? possible-steps) (place-n-queens/list origination destination (cdr boards)))
          (else possible-steps))
        ))))

Any help is appreciated to get this working!!

Answer 1

That's hard to follow. Generally n-queens is done with some sort of backtracking and I'm not seeing where you backtrack. The hard part is managing the side effects when using a vector. You have to set the board the the previous state before going back.

(define (n-queens size)
 (let ((board (make-vector size -1)))
   (let loop ((col 0) (row 0))
     (cond ((= col size) board)
           ((= row size)    ;;dead end
            (if (= col 0)   ;;if first collumn
                #f          ;;then no solutions
                (begin (vector-set! board (- col 1) -1))
                       #f)))            
                  ;;else undo changes made by previous level and signal the error
           ((safe? col row board) 
            (vector-set! board col row) 
            (or (loop (+ col 1) 0) 
                   ;;only precede to next column if a safe position is found
                (loop col (+ row 1))))
                   ;; keep going if hit a dead end. 
           (else (loop col (+ row 1)))))))

Writing safe? is up to you though.

Also not sure why you are moving from vector to list. It's just really clogging up the logic so I'm having trouble following. Plus you should be comfortable moving through vectors on their own. In place-queen-on-n you use build-list on a vector just so you can map over it. Whereas a vector-fold of some sort may be more appropriate. Additionally that map will always return a list which is always not false, meaning any code after that in the cond will never get hit. Is that your problem, I don't know but it is a problem.