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:
- implementing the representation of board positions and define
empty-board
. - writing the function definitions for
adjoin-position
andsafe?
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)))
list-ref
,every
, andany
. Your particular dialect of scheme may also provide them without having to require them specifically. \$\endgroup\$ – Marty Neal May 16 '12 at 20:28