<jupyter_start><jupyter_text>練習問題2.42"8クイーンパズル"とは、どのクイーンもほかのクイーンの利き筋に⼊らない  (つまり、同じ⾏・列・対⾓線の上に⼆つのクイーンがあるということがないようにする)ように  8個のクイーンをチェス盤の上に置く⽅法を問うものである。  図2.8に考えられる解のひとつを⽰す。  このパズルを解くひとつのやり⽅として、  各列にひとつのクイーンを置きながらチェス盤を横に移動していくというものがある。  $k−1$個のクイーンを置いた状態では、$k$個⽬のクイーンは、すでに盤上にあるどのクイーンも利き筋に⼊らない位置に置く必要がある。  この解き⽅は再帰的に定式化できる。最初の$k−1$列に$k−1$個のクイーンを置くパターンをすべて⽣成済みだと想定する。  それぞれのパターンに対して、$k$列⽬のそれぞれの⾏にクイーンを置いていって、  位置の集合を拡張したものを⽣成する。  次にこれらをフィルタして、$k$列⽬のクイーンがほかのクイ ーンに利かないものだけを残す。  こうすると、最初の$k$列に$k$個のクイーンを置くすべてのパターンの列ができる。  このプロセスを続けると、パズルの解答のひとつだけではなく、すべての解答が得られる。  この解き⽅をqueensという⼿続きとして実装し、  $n \times n$のチェス盤に$n$個のクイーンを置くという問題に対するすべての答えの列を返すようにする。  queensは、盤の最初の$k$列にクイーンを置くすべてのパターンの列を返す内部⼿続きqueen-colsを持っている。    (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)      )      この⼿続きの中で、rest-of-queensは最初の$k−1$列に$k−1$個のクイーンを置くパターンのひとつで、  new-rowは$k$列⽬のクイーンを置く候補となる⾏である。  盤上の位置集合に対する表現⽅法と、位置集合に新しい⾏・列の位置を追加するadjoin-position⼿続きと  位置の空集合を表すempty-boardを実装し、プログラムを完成させよ。  また、位置集合に対して、$k$列⽬のクイーンがほかのクイーンに利いていないかを調べるsafe?⼿続きも書く必要がある  (新しいクイーンの利きだけをチェックすればいいということに注意。  ほかのクイーンは互いに利いていないことが保証済みである)。  図2.8:8クイーンパズルのひとつの解 チェスの駒の動きについては以下を参照。  http://www.jca-chess.com/chess-2.htm 駒の動きとこの回答での駒の位置の表し方 基本な戦略としては、  「8x8のチェス盤に8個のクイーンを互いに取り合わない座標を列挙する」だから、1. 同じ列に2つ以上のクイーンは置かない→各列にクイーンを配置する2. 各クイーンの互いのy座標は重複しない3. 各クイーンの互いは対角線上にないを満たす、組み合わせを列挙すればよい。  この問題の解き方としては、各列のクイーンのy座標を列挙すればいいので、  1つの組み合わせ候補を(1 5 8 6 3 7 2 4)のようなy座標のリストとして表す。  各クイーンのx座標はこのリストのインデックス(1オリジン)と分かるので敢えて明記はしないこととする。  2.と3.についてはsafe?手続きでOKとなる組み合わせとなるかチェックする。  全体的な考え方としては、- 1列目から候補リストのリストを作成- 作成した候補リストのリストをsafe?手続きでフィルタする(NGとなるものはそぎ落とす)- フィルタ後のリストに2列目のy座標を加えて、候補リストのリストを作成- 作成した候補リストのリストをsafe?手続きでフィルタする(NGとなるものはそぎ落とす)- ・・・  という動作を8列目まで繰り返す。<jupyter_code>; 問題文のqueens手続き
; 以下の定義が必要
; ・empty-board
; ・safe?手続き
; ・adjoin-position手続き
(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)
  )

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

; 整数列の列挙
(define (enumerate-interval low high)
  (if (> low high) '()
      (cons low (enumerate-interval (+ low 1) high))))

; 集積
(define (accumulate op initial sequence)
  (if (null? sequence) initial
      (op (car sequence) (accumulate op initial (cdr sequence)))))

; フィルタリング
(define (filter predicate sequence)
  (cond ((null? sequence) '())
        ((predicate (car sequence))(cons (car sequence) (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence))))
  )

; 回答1
(define empty-board '())
; 回答2
; adjoin-position手続きの呼び出し方が決まっているため、
; この回答しかないはず。
; 列ごとの位置(Y座標)をリストで表す。
(define (adjoin-position new-row k rest-of-queens)
  (append rest-of-queens (list new-row))
  )
  
(define k 4)
(define board-size 4)
(define rest-of-queens (list 2 4 1))
(map (lambda (new-row) (adjoin-position new-row k rest-of-queens))
     (enumerate-interval 1 board-size))<jupyter_output><empty_output><jupyter_text>safe?手続きの考え方<jupyter_code>; k列目の位置のy座標を返す
(define (get-k-y k positions)
  (define (iter count pos)
    (if (>= count k) (car pos)
        (iter (+ count 1) (cdr pos))
        )
    )
  (iter 1 positions)
  )

; 回答3
(define (safe? k positions)
  (let ((k-y-pos (get-k-y k positions)))
    (define (iter count pos)
      (if (>= count k) #t
        (if (null? pos) #t
            (let ((y (car pos)))
              (let ((y-upper (- y (- k count)))
                    (y-lower (+ y (- k count))))
                ; y座標が同じか、対角線上にあればFalseを返す。
                ; それ以外はチェックを継続する。
                (if (or (= k-y-pos y) (= k-y-pos y-upper) (= k-y-pos y-lower)) #f
                    (iter (+ count 1) (cdr pos))
                    )
                )
              )
            )
        )
      )
      (iter 1 positions)
    )
  )

;(safe? 4 (list 1 2 3 4))
;(safe? 3 (list 2 4 1 3))
(safe? 4 (list 2 4 1 3))
(queens 3)
(queens 4)
(queens 6)
(queens 8)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13216798124067364, 'fraction_numerical': 0.0164144105734385, 'mean_word_length': 2.9395465994962215, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '343434', 'license': 'CC0-1.0', 'n_tokens_mistral': 2801, 'n_tokens_neox': 2652, 'n_words': 334, 'path': 'exercises/2.42.ipynb', 'repo_name': 'tokits/sicp-study', 'size': '4691'}