1
\$\begingroup\$

The problem can be found online here.

In short, we're given the following function definition, that will recursively generate all the possible solutions for the "eight-queen-problem".

(define (queens board-size)
  (define (queen-cols k)  
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

The problem consists of:

  1. implementing the representation of board positions and define empty-board.
  2. writing the function definitions for adjoin-position and safe?

The two following functions have already been defined in previous exercises:

(define (enumerate-interval low high)
  (if (> low high)
      '()
      (cons low
        (enumerate-interval (+ low 1) high))))

(define (flatmap proc seq)
  (fold-rigth append '() (map proc seq)))

Here's my commented working solution. You'll find I express my ideas in Python a lot, because it's practically like writing pseudo-code and, sadly, it still governs pretty much the way I think of code. I'm looking for any kind of feedback, from how to improve execution time, to how to make it more readable or any Scheme good practice you may mention. I don't know anybody in real-life who codes in Scheme, so I seek feedback from the next best place :)

;; A set of position is a list of pairs. 
;; The pairs are cons where the car is the value of the row and the cdr is the column.
;; Since we're recursively iterating through the board horizontally, the cdr can be seen as the index.

(define empty-board '())

(define (adjoin-position row col board)
  (append board (list (cons row col))))

;; in python there's the bracket syntax to return an element from a list: 
;; f[3] returns the 4th element of f. I could not find such a thing in Scheme, so I wrote this function.
(define (getposval pos idx)
  (caar (filter (lambda (pair) (= (cdr pair) idx))
        pos)))

;; any/all (say it quickly it sounds like Annie Hall) are inspired by their Python equivalent. 
;; Is there something similar in Scheme?
(define (any? seq)
  (fold-right (lambda (x y) (or x y)) #f seq))

(define (all? seq)
  (fold-right (lambda (x y) (and x y)) #t seq))

;; A position set is not safe if there exist i such as:
;;    - pos[col] == pos[i] # they're on the same row
;;    or
;;    - abs(pos[col] - pos[i]) == col - i # they're on a diagonal
(define (safe? col positions)
    (all? (map (lambda (x)
            (or (= col (cdr x))
                    ;; I should not write (getposval positions) so often
                    ;; maybe replace it with a let?
            (not (or (= (getposval positions col)
                    (getposval positions (cdr x)))
                 (= (abs (- (getposval positions col)
                        (getposval positions (cdr x))))
                    (- col (cdr x)))))))
           positions)))
\$\endgroup\$
  • 1
    \$\begingroup\$ srfi-1 provides some of the utility functions you define. Look at list-ref, every, and any. Your particular dialect of scheme may also provide them without having to require them specifically. \$\endgroup\$ – Marty Neal May 16 '12 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.