How to Solve N-Queens Problem in Scheme?
- by Philip
Hi, I'm stuck on the extended exercise 28.2 of How to Design Programs.
Here is the link to the question: http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-35.html#node_chap_28
I used a vector of true or false values to represent the board instead of using a list.
This is what I've got which doesn't work:
#lang Scheme
(define-struct posn (i j))
;takes in a position in i, j form and a board and returns a natural number that represents the position in index form
;example for board xxx
; xxx
; xxx
;(0, 1) - 1
;(2, 1) - 7
(define (board-ref a-posn a-board)
(+ (* (sqrt (vector-length a-board)) (posn-i a-posn))
(posn-j a-posn)))
;reverse of the above function
;1 - (0, 1)
;7 - (2, 1)
(define (get-posn n a-board)
(local ((define board-length (sqrt (vector-length a-board))))
(make-posn (floor (/ n board-length))
(remainder n board-length))))
;determines if posn1 threatens posn2
;true if they are on the same row/column/diagonal
(define (threatened? posn1 posn2)
(cond
((= (posn-i posn1) (posn-i posn2)) #t)
((= (posn-j posn1) (posn-j posn2)) #t)
((= (abs (- (posn-i posn1)
(posn-i posn2)))
(abs (- (posn-j posn1)
(posn-j posn2)))) #t)
(else #f)))
;returns a list of positions that are not threatened or occupied by queens
;basically any position with the value true
(define (get-available-posn a-board)
(local ((define (get-ava index)
(cond
((= index (vector-length a-board)) '())
((vector-ref a-board index)
(cons index (get-ava (add1 index))))
(else (get-ava (add1 index))))))
(get-ava 0)))
;consume a position in the form of a natural number and a board
;returns a board after placing a queen on the position of the board
(define (place n a-board)
(local ((define (foo x)
(cond
((not (board-ref (get-posn x a-board) a-board)) #f)
((threatened? (get-posn x a-board) (get-posn n a-board)) #f)
(else #t))))
(build-vector (vector-length a-board) foo)))
;consume a list of positions in the form of natural number and consumes a board
;returns a list of boards after placing queens on each of the positions on the board
(define (place/list alop a-board)
(cond
((empty? alop) '())
(else (cons (place (first alop) a-board)
(place/list (rest alop) a-board)))))
;returns a possible board after placing n queens on a-board
;returns false if impossible
(define (placement n a-board)
(cond
((zero? n) a-board)
(else (local ((define available-posn (get-available-posn a-board)))
(cond
((empty? available-posn) #f)
(else (or (placement (sub1 n) (place (first available-posn) a-board))
(placement/list (sub1 n) (place/list (rest available-posn) a-board)))))))))
;returns a possible board after placing n queens on a list of boards
;returns false if all the boards are not valid
(define (placement/list n boards)
(cond
((empty? boards) #f)
((zero? n) (first boards))
((not (boolean? (placement n (first boards)))) (first boards))
(else (placement/list n (rest boards)))))
