在方案中解决八皇后 [英] Solving Eight-queens in scheme
问题描述
我开始编写一个函数来查看一个皇后是否从棋盘上的其他位置安全",棋盘采用 (row col)
和 1-indexed 的形式.这是我迄今为止所拥有的:
I'm starting to write a function to see if a queen is 'safe' from the other positions on the board, the board is in the form of (row col)
and 1-indexed. Here is what I have thus far:
(define (get-row p) (car p))
(define (get-col p) (cadr p))
(define (is-equal p1 p2)
(and (= (car p1) (car p2)) (= (cadr p1) (cadr p2))))
(define (safe? k positions)
(filter
(lambda (p) (not (and (is-equal p
(list (get-row p) k))
(is-equal p
(list (+ (get-row p) (- k (get-col p)))
k
))
(is-equal p
(list (- (get-row p) (- k (get-col p)))
k
)))))
positions))
我想这样称呼它:
(safe? 4 '((3 1) (1 2) (4 3) (2 4)))
查看棋盘上位置为 (2 4)
的第四个皇后(在第四列中)是否安全.
To see if the fourth queen (in the forth column) on the board with position (2 4)
is safe.
但是,我目前所拥有的范围很广,并且基本上返回了所有其他"列,而不是我想要的列.有什么更好的方法可以做到这一点?
However, what I have currently is wide of the mark and returns basically all the 'other' columns instead of the one I want. What would be a better way to do this?
推荐答案
有很多方法可以解决这个问题.对于初学者,我建议使用更简单的电路板表示法,我选择使用数字列表.列表中的索引从1开始,表示皇后的列及其行的值(坐标原点在左上角,新位置在列表末尾相邻);所有其他位置都假定为空.例如,以下板:
There are many ways to solve this problem. For starters, I'd suggest a simpler representation for the board, I chose to use a list of numbers. The indexes in the list start from one and indicate the queen's column and the value its row (origin of coordinates is on the upper-left corner, new positions are adjoined at the end of the list); all the other positions are assumed to be empty. For instance, the following board:
(. Q)
(Q .)
将由列表 '(2 1)
表示.在我的表示中,safe?
过程看起来像这样 - 请注意 diagonals?
检查实现起来有点棘手:
Would be represented by the list '(2 1)
. With my representation, the safe?
procedure looks like this - and notice that the diagonals?
check is a bit trickier to implement:
; a new queen is safe iff there are no other queens in the same
; row nor in any of the diagonals preceding its current position
; we don't need to check the column, this is the only queen on it
(define (safe? col board)
(let ((row (list-ref board (- col 1))))
(and (<= (number-occurrences row board) 1)
(diagonals? row board))))
; counts how many times an element appears on a list
(define (number-occurrences e lst)
(count (curry equal? e) lst))
; traverses the board looking for other queens
; located in one of the diagonals, going backwards
; starting from the location of the newest queen
(define (diagonals? row board)
(let loop ((lst (cdr (reverse board)))
(upper (sub1 row))
(lower (add1 row)))
(or (null? lst)
(and (not (= (car lst) upper))
(not (= (car lst) lower))
(loop (cdr lst) (sub1 upper) (add1 lower))))))
结果如预期:
(safe? 4 '(2 4 1 3))
=> #t
如果您愿意,您可以修改上述代码以使用不同的坐标原点,或者使用坐标对来表示皇后.
You can adapt the above code to use a different origin of coordinates if you wish so, or to use pairs of coordinates to represent the queens.
这篇关于在方案中解决八皇后的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!