問題 2.43

#|
(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))
|#

;mapの中に(queen-cols (- k 1))があるので、そこでboard-size分
;queen-colsがかかる。

;最初の回は無視できるので、board-size^(board-size-1)回queen-colsが呼ばれる。
;速いほうでも、board-size回は呼ばれるので、結局
;(board-size^(board-size-1))/board-size倍の時間がかかると予想される。

(define (runtime) (current-milliseconds))

(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))

;slow-queensとしてつくる
(define (slow-queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (new-row)
            (map (lambda (rest-of-queens)
                   (adjoin-position new-row k rest-of-queens))
                 (queen-cols (- k 1))))
          (enumerate-interval 1 board-size)))))
  (queen-cols board-size))

(define (timed-queens-test n)
  (define f (runtime))
  (queens n)
  (display "queens : ")
  (display (- (runtime) f))
  (newline))
(define (timed-slow-queens-test n)
  (define f (runtime))
  (slow-queens n)
  (display "slow-queens : ")
  (display (- (runtime) f))
  (newline))


(timed-queens-test 8)
(timed-slow-queens-test 8)

;テスト1回目
;queens : 47
;slow-queens : 6421

;テスト2回目
;queens : 47
;slow-queens : 6406

;テスト3回目
;queens : 47
;slow-queensslow-queens : 6453

;平均
;queens : 47
;slow-queens : 6426.667


;47*(7^6)/7 = 789929
;全然違う…なんでだ…。

;ちなみに6×6では
;queens : 16
;slow-queens : 390

;8×8では
;queens : 203
;slow-queens : 待てない!