0 Replies - 1180 Views - Last Post: 14 March 2010 - 04:09 PM

#1 Locke   User is offline

  • Sarcasm Extraordinaire!
  • member icon

Reputation: 550
  • View blog
  • Posts: 5,624
  • Joined: 20-March 08

[Scheme] N-Queens Problem in Scheme

Posted 14 March 2010 - 04:09 PM

Description: All you need is PLT Scheme and some way to run it. I used version 4.2.1 (if I remember correctly). I think the current version is 4.2.4.This set of functions produces the list containing the sets of ways to place N queens on an NxN chess board without any of them being able to attack one another. The lists within the lists represent the squares in the columns to place the queen. For instance, if we have (3 1 4 2), you'd place the first queen in the first column in the 3rd square from the top. The second queen would go in the second column, in the 1st square from the top, and so on.
(define (enumerate-interval to from) ; build a list with "to" to "from" as the elements (numbers, more specifically)
  (if (> to from) '()
      (cons to (enumerate-interval(+ to 1) from))
   )
 )

(define (diagonal-below? pos list) ; test for diagonal going downward
  (cond((null? list) #f)
         ((= (+ pos 1) (list-ref list 0)) #t)
         (else (diagonal-below? (+ pos 1) (cdr list)))
   )
 )

(define (diagonal-above? pos list) ; test for diagonal going upward
  (cond((null? list) #f)
         ((= (- pos 1) (list-ref list 0)) #t)
         (else (diagonal-above? (- pos 1) (cdr list)))
   )
 )

(define (diagonal? pos list) ; test for diagonal conflict, returns #t if there is a conflict, #f if not
   (cond((null? list) #f)
          ((diagonal-above? pos list) #t)
          ((diagonal-below? pos list) #t)
          (else #f)
   )
)

(define (permute board perms)
   (if (null? board)
         (list perms)
         (append-map (lambda(x)
                     (if (diagonal? x perms) '()
                          (permute (remove x board) (cons x perms)))
                      )
          board)
    )
 )

(define (queen n)
  (permute (enumerate-interval 1 n) '())
)

;-------------------------------------------------------------------------
;------------------------------EXAMPLE USAGE------------------------------
;-------------------------------------------------------------------------

(print (queen 4)) ; print the 4x4 solutions.

; if you just want to print the number of ways, use the following

(print (length (queen 4))) ; will print the # of solutions for 4x4.


Is This A Good Question/Topic? 0
  • +

Page 1 of 1