schemelispsicpn-queens

Solving Eight-queens in scheme


I'm starting to write a function to see if a queen is 'safe' from the other positions on the board, the board is in the form of (row col) and 1-indexed. Here is what I have thus far:

(define (get-row p) (car p))
(define (get-col p) (cadr p))
(define (is-equal p1 p2)
  (and (= (car p1) (car p2)) (= (cadr p1) (cadr p2))))

(define (safe? k positions)
  (filter
     (lambda (p) (not (and (is-equal p
                               (list (get-row p) k))
                     (is-equal p
                               (list (+ (get-row p) (- k (get-col p)))
                                     k
                                     ))
                     (is-equal p
                               (list (- (get-row p) (- k (get-col p)))
                                     k
                                     )))))
   positions))

I am trying to call it something like:

(safe? 4 '((3 1) (1 2) (4 3) (2 4)))

To see if the fourth queen (in the forth column) on the board with position (2 4) is safe.

enter image description here

However, what I have currently is wide of the mark and returns basically all the 'other' columns instead of the one I want. What would be a better way to do this?


Solution

  • There are many ways to solve this problem. For starters, I'd suggest a simpler representation for the board, I chose to use a list of numbers. The indexes in the list start from one and indicate the queen's column and the value its row (origin of coordinates is on the upper-left corner, new positions are adjoined at the end of the list); all the other positions are assumed to be empty. For instance, the following board:

    (. Q)
    (Q .)
    

    Would be represented by the list '(2 1). With my representation, the safe? procedure looks like this - and notice that the diagonals? check is a bit trickier to implement:

    ; a new queen is safe iff there are no other queens in the same
    ; row nor in any of the diagonals preceding its current position
    ; we don't need to check the column, this is the only queen on it
    
    (define (safe? col board)
      (let ((row (list-ref board (- col 1))))
        (and (<= (number-occurrences row board) 1)
             (diagonals? row board))))
    
    ; counts how many times an element appears on a list
    
    (define (number-occurrences e lst)
      (count (curry equal? e) lst))
    
    ; traverses the board looking for other queens
    ; located in one of the diagonals, going backwards
    ; starting from the location of the newest queen
    
    (define (diagonals? row board)
      (let loop ((lst   (cdr (reverse board)))
                 (upper (sub1 row))
                 (lower (add1 row)))
        (or (null? lst)
            (and (not (= (car lst) upper))
                 (not (= (car lst) lower))
                 (loop (cdr lst) (sub1 upper) (add1 lower))))))
    

    The result is as expected:

    (safe? 4 '(2 4 1 3))
    => #t
    

    You can adapt the above code to use a different origin of coordinates if you wish so, or to use pairs of coordinates to represent the queens.