我正在尝试解决方案中的n-皇后问题。教授告诉我，使用单个 vector 作为棋盘，其中 vector 的ith元素代表棋盘的第i列。该元素的值是其后放置一个皇后的行；如果该列为空，则为-1。因此，[0 1 2 -1 -1]有两列，没有皇后，三位皇后被非法放置。
当我运行以下代码时:(place-n-queens 0 4＃(-1 -1 -1 -1))我得到＃(0 1 2 3)，显然所有四个皇后都被非法放置了。我认为问题是我没有在con-queen-on-n中检查cond中足够多的内容，但是我不确定要添加什么来解决使皇后区位于同一对角线上的问题。
(define (return-row vector queen)
(vector-ref vector (return-col vector queen)))
(define (return-col vector queen)
(remainder queen (vector-length vector)))
(define (checkrow vector nq oq)
(cond
((= (vector-ref vector nq) -1) #f)
((= (vector-ref vector oq) -1) #f)
(else (= (return-row vector nq) (return-row vector oq)))))
(define (checkcol vector nq oq)
(= (return-col vector nq) (return-col vector oq)))
(define (checkdiagonal vector nq oq)
(cond
((= (vector-ref vector nq) -1) #f)
((= (vector-ref vector oq) -1) #f)
(else (= (abs (- (return-row vector nq) (return-row vector oq)))
(abs (- (return-col vector nq) (return-col vector oq)))))))
(define (checkdiagonalagain vector r c oq)
(= (abs (- r (return-row vector oq)))
(abs (- c (return-col vector oq)))) )
(define (checkrowagain vector r oq)
(= r (return-row vector oq)))
(define (checkinterference vector nq oq)
(or (checkrow vector nq oq) (checkcol vector nq oq) (checkdiagonal vector nq oq)))
(define (place-queen-on-n vector r c)
(local ((define (foo x)
(cond
((checkrowagain vector r x) -1)
((= c x) r)
((checkinterference vector c x) -1)
((map (lambda (y) (eq? (vector-ref vector x) y))
(build-list (vector-length vector) values)) (vector-ref vector x))
((eq? (vector-ref vector x) -1) -1)
(else -1))))
(build-vector (vector-length vector) foo)))
(define (place-a-queen vector)
(local ((define (place-queen collist rowlist)
(cond
((empty? collist) '())
((empty? rowlist) '())
(else (append (map (lambda (x) (place-queen-on-n vector x (car collist))) rowlist)
(try vector (cdr collist) rowlist)))
)))
(place-queen (get-possible-col vector) (get-possible-row (vector->list vector) vector))))
(define (try vector collist rowlist)
(cond
((empty? collist) '())
((empty? rowlist) '())
(else (append (map (lambda (x) (place-queen-on-n vector x (car collist))) rowlist)
(try vector (cdr collist) rowlist)))))
(define (get-possible-col vector)
(local ((define (get-ava index)
(cond
((= index (vector-length vector)) '())
((eq? (vector-ref vector index) -1)
(cons index (get-ava (add1 index))))
(else (get-ava (add1 index))))))
(get-ava 0)))
;list is just vector turned into a list
(define (get-possible-row list vector)
(filter positive? list)
(define (thislist) (build-list (vector-length vector) values))
(remove* list (build-list (vector-length vector) values))
)
(define (place-n-queens origination destination vector)
(cond
((= origination destination) vector)
(else (local ((define possible-steps
(place-n-queens/list (add1 origination)
destination
(place-a-queen vector))))
(cond
((boolean? possible-steps) #f)
(else possible-steps))))))
(define (place-n-queens/list origination destination boards)
(cond
((empty? boards) #f)
(else (local ((define possible-steps
(place-n-queens origination destination (car boards))))
(cond
((boolean? possible-steps) (place-n-queens/list origination destination (cdr boards)))
(else possible-steps))
))))
任何帮助表示感谢，以使这项工作正常!
最佳答案
这很难遵循。通常，n女王区通过某种回溯来完成，而我看不到您在哪里回溯。困难的部分是管理使用 vector 时的副作用。您必须将板设置为先前状态，然后再返回。
(define (n-queens size)
(let ((board (make-vector size -1)))
(let loop ((col 0) (row 0))
(cond ((= col size) board)
((= row size) ;;dead end
(if (= col 0) ;;if first collumn
#f ;;then no solutions
(begin (vector-set! board (- col 1) -1))
#f)))
;;else undo changes made by previous level and signal the error
((safe? col row board)
(vector-set! board col row)
(or (loop (+ col 1) 0)
;;only precede to next column if a safe position is found
(loop col (+ row 1))))
;; keep going if hit a dead end.
(else (loop col (+ row 1)))))))
写安全吗？取决于你。
也不确定为什么要从 vector 移到列表。这只是在阻塞逻辑，所以我很难理解。另外，您应该可以自行浏览 vector 。在
place-queen-on-n中，仅对 vector 使用构建列表，以便可以在其上进行映射。而某种 vector 折叠可能更合适。另外，该映射将始终返回一个列表，该列表始终不为false，这意味着cond之后的任何代码都不会被命中。那是你的问题，我不知道，但这是一个问题。