無限クイーン

TAOCPの演習問題7221-38に, 無限クイーン列<q_n>の効率的計算法を考案せよというのがある.

面白い解答なので, その説明をしたい.

二進の配列 a,b,cを使う. cは正と負の添字がある.
G1. [初期化.] r←0, s←1, t←0, n←0とする. ( 1≤k≤nについて, q_kの計算が済んだ.)
G2. [q_n≤nを調べる.] (この時点で1≤k<sについて a_k=1でa₂=0; また-r<k≤tについてc_k=1 でc_-r=c_t+1=0; 各ベクターにはn個の1がある.) n←n+1, k←sとする.
G3. [見つけた?] a_k=b_k+n=c_k-n=0なら G5へ進む. そうでないなら, k←k+1とし, k≤n-rならこのステップを繰り返す.
G4. [q_n>nを作る.] t←t+1; q_n←n+t; a_k←b_2n+t←c_t←1とし, G2へ戻る.
G5. [q_n≤nを作る.] q_n←k; a_k←b_k+n←c_k-n←1とする. k=sなら, a_s=0になるまでs←s+1を繰り返す. k=n-rなら c_-r=0になるまでr←r+1を繰り返す. G2へ戻る.

このプログラムを忠実に辿ると, 大体こういうことをやっていると判明する.

TAOCPのプログラムでは, チェス盤の行も列も1から始めるが, 私はやはり0から 始めたい. 前回の無限クイーンの最後にあるように, 解の列は

0 2 4 1 3 8 10 12 14 5 7 18 6 21 9 24 26 28 30 11 13 34 36 38 40 15 17 44 16 47

のように始まる. その始めの方の置きかたを見ると(下の図 前回の図では, 行は下に 延びていたのに, 今回は逆に上に延びるように描いて申し訳けない.)

まず列n=0は行0にクイーンが置ける. それが左下の黒丸だ. そうするとどの行にはもう置けない ことを示す配列aの0を1に, 行-列の対角線に置けないことを示す配列cの0-0=0を1にする. 図ではそれを黒丸のすぐ右の青小丸とすぐ右上の赤小丸で示す. 配列bも0+0=0が 1になるがそれは図には示さない.

続いてn=1にクイーンを置くのだが, 青線が示すようにこの行には置けず, 赤の対角線が 示すようにこの斜線にも置けない. よって赤斜線の上のq=2に置くことになる. それが (1,2)の黒丸で, その右の青小丸と右上の赤小丸で配列の設定も分る.

n=2の列は, 行0は青線でだめ, 行2は赤線でだめ, その間の行1は, すぐ左上にクイーン がいてだめ(これは配列bで分る). 行4も(1,2)からの斜線のためだめで, 結局 行4に置く.

このようにして置いていくのだが, 青線はこれより下はすべて詰っている; 2本の赤線は この間はすべて詰っていることを示す. したがって行0の青線は, 列3の行1に置くと 行2まで詰ったので, ここからは行2から横に進む.

赤の斜線も同様に出来ている. 従ってある列でクイーンが置けるか調べるには, 青線路 の上から始め, 下の赤線の下までである. ここまでで配列a, b, cを調べ, 置けない 時は, 上の赤線の上に置くことになる.

この方針で私流に書いたプログラムが次だ.

(define qs (make-list 30))
(define as (make-list 50 0))
(define bs (make-list 80 0))
(define cs (make-list 40 0))
(define coff 20)
(define (a k) (list-ref as k))
(define (b k) (list-ref bs k))
(define (c k) (list-ref cs (+ k coff)))
(define (a! k) (list-set! as k 1))
(define (b! k) (list-set! bs k 1))
(define (c! k) (list-set! cs (+ k coff) 1))
(define (place k) (list-set! qs n k)
 (a! k) (b! (+ k n)) (c! (- k n)))
(define n 0) (define s -1) (define t 0) (define r 0)
(define k)
(while (< n 30) (set! k (+ s 1))
 (while 
  (and (< k (+ n r))
   (or (= (a k) 1) (= (b (+ k n)) 1) (= (c (- k n)) 1)))
  (set! k (+ k 1)))
 (if (and (= (a k) 0) (= (b (+ k n)) 0)
  (= (c (- k n)) 0))
  (begin (place k)
   (while (= (a (+ s 1)) 1) (set! s (+ s 1)))  
   (while (= (c (- r 1)) 1) (set! r (- r 1))))
  (begin (place (+ n t 1)) (set! t (+ t 1))))
 (set! n (+ n 1)))
qs

=>(0 2 4 1 3 8 10 12 14 5 7 18 6 21 9 24 26 28 30 11 13
  34 36 38 40 15 17 44 16 47)	  

変数sは青線を, rは下の赤線を, tは右の赤線を示す. これは最初のTAOCPのプログラムと 同じである. 変数kの使い方も同様.

下の図は, 上のと同じだが, nの範囲を広げた. また配列を調べた位置を白丸で示した. 白丸の数が少ないことに注目して欲しい. TAOCPのプログラムは判定の方法が違うので, 白丸の数はこれよりかなり多い.