美文网首页
Scheme解八皇后问题

Scheme解八皇后问题

作者: ABleaf | 来源:发表于2019-12-15 22:53 被阅读0次

先实现一个产生特定顺序序列的库

(library (range)
  (export range make-range)
  (import (chezscheme))
  (define make-range
    (lambda (first last delta)
      (if (= delta 0)
          (error 'delta "make-range arg 3 must not be zero!"))
      (if (= first last)
          (list first)
          (let ([cmp (cond
                       [(< first last) >]
                       [(> first last) <])])
            (set! last (+ first (* (fx/ (- last first) delta) delta)))
            (if (cmp delta 0)
                (do ([last last (- last delta)]
                     [range '() (cons last range)])
                  [(cmp first last) range])
                '())))))
  ; 只适合用来产生一个序列,不适合用于循环的迭代
  (define range
    (case-lambda
      [(n) (make-range 0 n 1)]
      [(n1 n2) (make-range n1 n2 1)]
      [(n1 n2 delta) (if (= delta 0)
                         (error 'delta "range arg 3 must not be zero!")
                         (make-range n1 n2 delta))])))

定义一个高阶函数,将一个过程作用于一个序列,将产生的多个序列合并为一个序列。

(define (flatmap proc seq)
  (fold-right append '() (map proc seq)))

现在来实现求解n皇后问题的函数。

(import (range))

(define (queens board-size)
  (define col car)  ;取得当前位置的列数
  (define row cdr)  ;取得当前位置的行数
  (define (queen-cols k)
    (define (safe-range k k-1cols)
      (let ([r (range 1 board-size)])
        (for-each
          (lambda (pos)  ;移除对角线上的queens和已经存在的行数
            (let ([dx (- k (col pos))][y (row pos)])
              (set! r (remove! (- y dx) (remove! (+ y dx) (remove! y r))))))
          k-1cols)
        ; (printf "~a => ~a" k-1cols r)
        r))
    (if (= k 0)
        (list '())
        (flatmap (lambda (less-queens)
                   (map (lambda (new-row)  ;列在前,行在后
                          (cons (cons k new-row) less-queens))
                        (safe-range k less-queens)))
                 (queen-cols (- k 1)))))  ;递归生成前k-1列的所有不攻击的格局
  (map (lambda (x) (reverse (map row x))) (queen-cols board-size)))

打印结果,可以看到,8皇后问题有92个解。

(let ([queen8 (queens 8)])
  (pretty-print queen8)
  (printf "~a\n" (length queen8)))

相关文章

  • Scheme解八皇后问题

    先实现一个产生特定顺序序列的库 定义一个高阶函数,将一个过程作用于一个序列,将产生的多个序列合并为一个序列。 现在...

  • 递归解八皇后问题

    问题描述 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇...

  • 回溯法解八皇后问题

    问题介绍 摘自百度百科八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟...

  • 11.数据结构—八皇后问题(回溯法)

    11.1 八皇后问题 八皇后问题是以国际象棋为背景的问题:有八个皇后(可以当成八个棋子),如何在 88 的棋盘中放...

  • 算法(03)回溯

    八皇后问题

  • 八皇后问题(N皇后问题)

    八皇后问题是一个经典的递归回溯问题。 描述 八皇后问题是在一个 8*8 的棋盘上放置皇后,要求其放置后满足同一行,...

  • 八皇后问题

    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在...

  • 八皇后问题

    问题的类别是回溯(backtrace). 回溯通常用递归实现。回溯中注意边界问题,避免越界。同时,剪枝可以减少ca...

  • 八皇后问题

    课堂上老师讲了广度优先搜索算法后让课下实现下八皇后问题,就突发奇想了很多实现方法,这里只把我的实现方式和实现代码粘...

  • 八皇后问题

    问题 八皇后问题是一个古老而著名的问题,是试探法的典型例题。该问题由19世纪数学家高斯1850年手工解决。原题为在...

网友评论

      本文标题:Scheme解八皇后问题

      本文链接:https://www.haomeiwen.com/subject/udnlnctx.html