8×8の盤に, 5個のクイーンを, 盤のすべての場所を支配するように置く という問題である. 1863年の本にあるそうだから, 古典的問題である.
この解は, 4860通りあるらしいので, 自分でも計算することにした.
私のことだから, Schemeを使う. またSchemeを使うなら, bit-stringが役立つ.
プログラムを書いたら, 思ったより簡単で, 1時間はかからなかった. こんな具合だ.
(define (r n) (map (lambda (i) (+ (* n 8) i)) (range 0 8)))
(define (c n) (map (lambda (i) (+ (* i 8) n)) (range 0 8)))
(define (d n) (if (< n 0) ;n=i-j -7<=n<8
(map (lambda (i) (+ (* i 9) (- 0 n))) (range 0 (+ n 8)))
(map (lambda (i) (+ (* i 9) (* n 8))) (range 0 (- 8 n)))))
(define (u n) (if (< n 7) ;n=i+j 0<=n<15
(map (lambda (i) (+ (* i -7) (* n 8))) (range 0 (+ n 1)))
(map (lambda (i) (+ (* i -7) (+ n 49))) (range 0 (- 15 n)))))
(define (bs n)
(let ((i (quotient n 8)) (j (modulo n 8))
(b (make-bit-string 64 #t)))
(for-each (lambda (m) (bit-string-clear! b m))
(append (r i) (c j) (d (- i j)) (u (+ i j))))
b))
(define bss (map bs (range 0 64)))
(do ((i 0 (+ i 1)) (count 0) (bs (make-bit-string 64 #t)))
((= i 60) count) (display (list 'i i))
(let ((bs (bit-string-copy
(bit-string-and bs (list-ref bss i)))))
(do ((j (+ i 1) (+ j 1))) ((= j 61))
(let ((bs (bit-string-copy
(bit-string-and bs (list-ref bss j)))))
(do ((k (+ j 1) (+ k 1))) ((= k 62))
(let ((bs (bit-string-copy
(bit-string-and bs (list-ref bss k)))))
(do ((l (+ k 1) (+ l 1))) ((= l 63))
(let ((bs (bit-string-copy
(bit-string-and bs (list-ref bss l)))))
(do ((m (+ l 1) (+ m 1))) ((= m 64))
(if (bit-string-zero?
(bit-string-and bs (list-ref bss m)))
(set! count (+ count 1))))))))))))
盤のますには, 左上から右上にかけ, そして上から下へ, 0から63まで番号を付ける.
行rは上が0, 下が7(その番号をiとする), 列cは左が0, 右が7(その番号をjとする),
左上から右下への対角線dは, ます7を通る(i=0,j=7)のを-7, ます0を通るのを0,
ます56を通る(i=7, j=0)のを7, 左下から右上への対角線uは, ます0を通る(i=0,j=0)
のを0, ます56を通る(i=7,j=0)のを7, ます63を通る(i=7,j=7)のを14とする.
先頭の関数, r,c,d,uは, 行n, 列n, 下り対角線n, 上り対角線nにいるクイーンが支配する ますの番号を返す.
bssは, ますnのクイーンが支配するますをビット0, それ以外をビット1にした, 64ビット のビット列の配列である。＜br＞
これだけ用意し, 後は5個のクイーンを, 全面に置きながら, 支配場所を集め, 5個置いた 時に, すべてのます(に対応するビット)が0なら, countを1増やす.
やってみたら, 18秒くらいで, 4860が得られた.
0 件のコメント:
コメントを投稿