SICP Exercise 2.42: Eight queens puzzle
2021-10-29
Categories: Programming
Exercise 2.42: The “eight-queens puzzle” asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal).
One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed
k - 1
queens, we must place thek
th queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to placek - 1
queens in the firstk - 1
columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of thek
th column. Now filter these, keeping only the positions for which the queen in thek
th column is safe with respect to the other queens. This produces the sequence of all ways to placek
queens in the firstk
columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.We implement this solution as a procedure
queens
, which returns a sequence of all solutions to the problem of placingn
queens on ann×n
chessboard. Queens has an internal procedurequeen-cols
that returns the sequence of all ways to place queens in the firstk
columns of the board.1(define (queen board-size) 2 (define (queen-cols k) 3 (if (= k 0) 4 (list empty-board) 5 (filter 6 (lambda (positions) (safe? k positions)) 7 (flatmap 8 (lambda (rest-of-queens) 9 (map (lambda (new-row) 10 (adjoin-position new-row k rest-of-queens)) 11 (enumerate-interval 1 board-size))) 12 (queen-cols (- k 1)))))) 13 (queen-cols board-size))In this procedure
rest-of-queens
is a way to placek - 1
queens in the firstk - 1
columns, andnew-row
is a proposed row in which to place the queen for thek
th column. Complete the program by implementing the representation for sets of board positions, including the procedureadjoin-position
, which adjoins a new row-column position to a set of positions, andempty-board
, which represents an empty set of positions. You must also write the proceduresafe?
, which determines for a set of positions, whether the queen in thek
th column is safe with respect to the others. (Note that we need only check whether the new queen is safe – the other queens are already guaranteed safe with respect to each other.)
I will try to implement the simpler procedures first.
empty-board
represents an empty set of positions:
1(define empty-board '())
adjoin-position
adjoins a new row-column position to a set of positions:
1(define (adjoin-position row col rest-of-queens) 2 (cons (list row col) rest-of-queens))
attack?
checks if two queens are in the same row, column, or diagonal:
1(define (attack? q1 q2) 2 (or (= (row q1) (row q2)) 3 (= (abs (- (row q1) (row q2))) 4 (abs (- (col q1) (col q2)))))) 5 6(define (row position) 7 (car position)) 8 9(define (col position) 10 (cadr position))
(No need to check if they are in the same column)
The most difficult procedure is safe?
: which determines for a set of positions, whether the queen in the k
th column is safe with respect to the others.
The steps should be something like this:
- get the queen in the
k
th column - get the first element of the
rest-of-queens
- check if two queens are under attack
- if yes, return
#f
(false) - else: remove the first element from
rest-of-queens
and do the same with the remaining elements
- if yes, return
Here’s the code:
1(define (safe? k positions) 2 (if (= (length positions) 1) 3 #t 4 (if (attack? (k-queen positions) (first-queen positions)) 5 #f 6 (safe? k (remove (first-queen positions) positions))))) 7 8(define (k-queen positions) 9 (car positions)) 10 11(define (first-queen positions) 12 (cadr positions))
The remove
procedure is similar to the one at the end of Nested Mappings section but uses equals?
to compare list:
1(trace-define (remove item sequence) 2 (filter (lambda (x) (not (equal? x item))) 3 sequence))
The completed program:
1(trace-define (queen board-size) 2 (define (queen-cols k) 3 (if (= k 0) 4 (list empty-board) 5 (filter 6 (lambda (positions) (safe? k positions)) 7 (flatmap 8 (lambda (rest-of-queens) 9 (map (lambda (new-row) 10 (adjoin-position new-row k rest-of-queens)) 11 (enumerate-interval 1 board-size))) 12 (queen-cols (- k 1)))))) 13 (trace queen-cols) 14 (queen-cols board-size)) 15 16(define empty-board '()) 17 18(define (adjoin-position row col rest-of-queens) 19 (cons (list row col) rest-of-queens)) 20 21(define (safe? k positions) 22 (if (= (length positions) 1) 23 #t 24 (if (attack? (k-queen positions) (first-queen positions)) 25 #f 26 (safe? k (remove (first-queen positions) positions))))) 27 28(define (k-queen positions) 29 (car positions)) 30 31(define (first-queen positions) 32 (cadr positions)) 33 34(define (attack? q1 q2) 35 (or (= (row q1) (row q2)) 36 (= (abs (- (row q1) (row q2))) 37 (abs (- (col q1) (col q2)))))) 38 39(define (row position) 40 (car position)) 41 42(define (col position) 43 (cadr position)) 44 45(define (remove item sequence) 46 (filter (lambda (x) (not (equal? x item))) 47 sequence))
Test:
1$ racket 2.42-eight-queens.rkt 2>(queen 4) 3>(queen-cols 4) 4> (queen-cols 3) 5> >(queen-cols 2) 6> > (queen-cols 1) 7> > >(queen-cols 0) 8< < <'(()) 9< < '(((1 1)) ((2 1)) ((3 1)) ((4 1))) 10< <'(((3 2) (1 1)) 11 ((4 2) (1 1)) 12 ((4 2) (2 1)) 13 ((1 2) (3 1)) 14 ((1 2) (4 1)) 15 ((2 2) (4 1))) 16< '(((2 3) (4 2) (1 1)) 17 ((1 3) (4 2) (2 1)) 18 ((4 3) (1 2) (3 1)) 19 ((3 3) (1 2) (4 1))) 20<'(((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1))) 21'(((3 4) (1 3) (4 2) (2 1)) ((2 4) (4 3) (1 2) (3 1)))
1|---|---|---|---| 2| | | X | | 3|---|---|---|---| 4| X | | | | 5|---|---|---|---| 6| | | | X | 7|---|---|---|---| 8| | X | | | 9|---|---|---|---|
1|---|---|---|---| 2| | X | | | 3|---|---|---|---| 4| | | | X | 5|---|---|---|---| 6| X | | | | 7|---|---|---|---| 8| | | X | | 9|---|---|---|---|
Related Posts:
- SICP Exercise 2.77: expected a procedure that can be applied to arguments, given #f
- SICP Exercise 2.43: Eight queens: interchange the order of the nested mappings
- SICP Exercise 2.41: Triple sum
- SICP Exercise 2.35: Counting leaves of a tree
- SICP Exercise 2.27: Reversing nested lists