8queen.scm

8queen.scm

;; report 70 :8queen
;; （説明適当）
;;arrowと攻撃範囲の対応
;; arrow -1-> (dx, dy) = (1 , -1) （右上）
;; arrow 0-> (dx, dy) = (1 , 0)（右）
;; arrow +1-> (dx, dy) = (1 , 1)（右下）
;; for x in 0..7 
;;  for y in 0..7
;; でチェックするようなイメージ。


(define (eight-queen)
  (eq-search-canpos 0 "" (list 0 0 0)))

;; maps -> （右上、右、右下）方向の攻撃範囲（ビット列で表現）のリスト（長さ3）
(define (eq-search-canpos idx positions maps)
  (cond 
	((= idx 8) ())
	((= (string-length positions) 8)
	 (list positions))
	(else 
	  (let 
		((when-notput (eq-search-canpos (+ idx 1) positions maps)))
		(if (logbit? idx (lapover-triple maps)) ;;置けるかチェック
		  when-notput ;; cannot put queen here
		  (let 
			((when-put (eq-search-canpos 0 (string-append positions (number->string idx)) (eq-next-map -1 idx maps))))
			(append when-notput when-put)))))))  ;; can put queen here

;; x++した際の攻撃範囲のmapを返す(ループ部分)
(define (eq-next-map arrow pos maps)
  (if (= arrow 2)
	()
	(cons (check-map pos arrow (car maps))  (eq-next-map (+ arrow 1) pos (cdr maps)))))

;; y = posにqueenを置いた時、x++での攻撃範囲のmapを作る
(define (check-map pos arrow amap)
  (mod (ash (logior amap (ash 1 pos)) arrow) (ash 1 8)))

;; 攻撃範囲のmapの論理和をとる
(define (lapover-triple maps)
  (if (null? maps)
	0
	(logior (car maps) (lapover-triple (cdr maps)))))


(use slib)
(require 'trace)
(set! debug:max-count 10)
(trace eq-search-canpos)
;;(trace eq-next-map)
;;(trace check-map)
;;(trace lapover-triple)


;; answer = ("73025164" "72051463" "71420635" "71306425" "64205713" "63175024" "63147025" "62714053" "62057413" "61520374" "61307425" "60275314" "57130642" "53607142" "53602417" "53174602" "53047162" "52630714" "52617403" "52613704" "52470316" "52460317" "52074136" "52073164" "52064713" "51603742" "51602473" "50417263" "47306152" "47302516" "46302751" "46152073" "46152037" "46137025" "46031752" "46027531" "42736051" "42061753" "42057136" "41703625" "41506372" "41362750" "41357206" "40752613" "40731625" "40357162" "37420615" "37046152" "37025164" "36420571" "36415027" "36271405" "36074152" "35720641" "35716024" "35041726" "31750246" "31746025" "31640752" "31625740" "31625704" "31475026" "30475261" "30471625" "27360514" "26175304" "26174035" "25713064" "25704613" "25703641" "25317460" "25307461" "25164073" "25160374" "25147063" "24730615" "24603175" "24175360" "24170635" "20647135" "17502463" "16470352" "16257403" "15720364" "15063724" "14630752" "14602753" "13572064" "06471352" "06357142" "05726314" "04752613")