八皇后之谜 |
您所在的位置：网站首页 › 八云橙风 › 八皇后之谜 |
八皇后之谜
 图2.8:八皇后之谜的解决方案。“八皇后之谜”询问如何将八皇后放在棋盘上，这样就不会有任何皇后从其他棋盘上被检查(也就是说，没有两个皇后在同一排、一列或对角线上)。图2.8显示了一个可能的解决方案。解决这一难题的一种方法是全面工作，在每一列中放置一位女王。一旦我们放置了k-1皇后，我们必须把kth女王放在一个位置，它不检查任何女王已经在董事会。我们可以递归地表述这个方法:假设我们已经生成了将k-1皇后放在板的第一列中的所有可能方法的序列。对于这些方法中的每一种，通过在kth列的每一行放置一个皇后来生成一组扩展的位置。现在过滤这些，只保留女王在kth列的位置相对于其他女王是安全的。这产生了在第一个k列中放置k皇后的所有方法的顺序。通过继续这一进程，我们将不仅提出一个解决方案，而且将提出解决这个难题的所有办法。我们把这个解作为一个过程皇后来实现，它返回n个皇后在n×n棋盘上的所有解的序列。皇后区有一个内部程序皇后学院，返回在董事会的第一个k列的所有方法的顺序。 (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))在此过程中，皇后休息是将k-1皇后放置在第一k-1列中的一种方式，而新行则是将女王放置在kth列中的建议行。通过实现董事会职位集的表示来完成程序，包括过程相邻位置(它将一个新的行列位置与一组位置相邻)和空板(表示一组空的位置)。您还必须编写过程安全？，该过程确定一组位置，kth列中的女王相对于其他位置是否安全。(请注意，我们只需检查新女王是否安全-其他女王之间的安全已经得到保证。) 我发现这项任务特别困难。我想我有一个可行的答案，但我相信还有更好的方法。我目前的解决方案就像一座用胶带连接在一起的冰棒桥，随时都会崩溃。我知道这很乱，所以我必须事先道歉。如果你听不懂的话，让我知道，如果可能的话，我会试着重写一下。不过，现在我需要休息一下！如何改进我的代码？ (define (enumerate-interval i j) (if (= i j) (list j) (cons i (enumerate-interval (+ i 1) j)))) (define (filter f seq) (if (null? seq) null (if (f (car seq)) (cons (car seq) (filter f (cdr seq))) (filter f (cdr seq))))) (define (flatmap op seq) (foldr append null (map op seq))) (define (queens board-size) (define (empty-board) (map (lambda (row) (map (lambda (col) 0) (enumerate-interval 1 board-size))) (enumerate-interval 1 board-size))) (define (adjoin-position new-row k rest-of-queens) (cond ((and (= new-row 1) (= k 1)) (cons (cons 1 (cdar rest-of-queens)) (cdr rest-of-queens))) ((> k 1) (cons (car rest-of-queens) (adjoin-position new-row (- k 1) (cdr rest-of-queens)))) (else (let ((adjoined (adjoin-position (- new-row 1) k (cons (cdar rest-of-queens) (cdr rest-of-queens))))) (cons (cons (caar rest-of-queens) (car adjoined)) (cdr adjoined)))))) (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)) (define col car) (define row cdr) (define (indexOf x seq) (define (rec i remains) (cond ((null? remains) (error "No x found in seq." x seq)) ((= (car remains) x) i) (else (rec (+ i 1) (cdr remains))))) (rec 0 seq)) (define (nth n seq) (cond ((null? seq) (error "Sequence shorter than n" seq n)) ((= n 1) (car seq)) (else (nth (- n 1) (cdr seq))))) (define (all-true seq) (cond ((null? seq) true) ((car seq) (all-true (cdr seq))) (else false))) (define (upto k rows) (if (or (= k 0) (null? rows)) null (cons (car rows) (upto (- k 1) (cdr rows))))) (define (safe? k positions) (let ((uptok-positions (upto (- k 1) positions)) (kth-position (nth k positions))) (define (col-row-coords pos) (define (process-row rownum rows) (define (process-col colnum row) (cond ((null? row) null) ((= (car row) 1) (cons rownum colnum)) (else (process-col (+ colnum 1) (cdr row))))) (if (null? rows) null (cons (process-col 1 (car rows)) (process-row (+ rownum 1) (cdr rows))))) (process-row 1 pos)) (let ((col-and-row (filter (lambda (x) (not (null? x))) (col-row-coords uptok-positions))) (k-coord (cons k (indexOf 1 kth-position)))) (define (diagonal? p1 p2) (= (abs (- (col p1) (col p2))) (abs (- (row p1) (row p2))))) (all-true (map (lambda (pos) (and (not (= (col k-coord) (col pos))) (not (= (row k-coord) (row pos))) (not (diagonal? k-coord pos)))) col-and-row)))))编辑:谢谢你的反馈！我这里有个新版本。如果你有任何反馈，我将不胜感激。 (define (enumerate-interval i j) (if (> i j) null (cons i (enumerate-interval (+ i 1) j)))) (define (filter f seq) (if (null? seq) null (if (f (car seq)) (cons (car seq) (filter f (cdr seq))) (filter f (cdr seq))))) (define (flatmap op seq) (foldr append null (map op seq))) (define (queens board-size) (define (empty-board) '()) (define (adjoin-position new-row k rest-of-queens) (append rest-of-queens (list (cons new-row k)))) (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)) (define col car) (define row cdr) (define (threatens? q1 q2) (define (diagonal? q1 q2) (= (abs (- (col q1) (col q2))) (abs (- (row q1) (row q2))))) (or (= (col q1) (col q2)) (= (row q1) (row q2)) (diagonal? q1 q2))) (define (nth n seq) (if (= n 1) (car seq) (nth (- n 1) (cdr seq)))) (define (except-nth n seq) (cond ((null? seq) '()) ((= n 1) (cdr seq)) (else (cons (car seq) (except-nth (- n 1) (cdr seq)))))) (define (safe? k positions) (define (rec me threats) (or (null? threats) (and (not (threatens? me (car threats))) (rec me (cdr threats))))) (rec (nth k positions) (except-nth k positions))) |
【本文地址】
今日新闻 |
推荐新闻 |