Ｎクイーン問題（１３）第三章　ビットマップ

ビットマップ

Ｎ×ＮのチェスボードのＮ個のクイーンの配置を、bitwise(ビット)で表したものがbitmap(ビットマップ)です。

ビットマップの特徴

斜め方向にクイーンを配置したかどうかを、left down right といった bit フラグで表します。

大きなメリットは、
１．ビットマップであれば、シフト(<<1 ,>>1)により高速にデータを移動できる。
２．配置フラグといったフラグ配列では、データの移動に O(N) の時間がかかるが、ビットマップであれば O(1)ですむ。
３．フラグ配列のように斜め方向に 2*N-1 の要素を用意する必要はなく Nビットで充分たりる。
４．ビットは初期値が０なので扱いやすい

デメリットとしては
２進数と１０進数により難読化が極まっている。

ビットマップを言葉で説明すると・・・

４ｘ４のチェス盤を使ってみましょう。
チェス盤の各行は1つの2進数で表されますが、これは単なるビットの並びです。
ある行の一番左のマスにクイーンが置かれた場合、その行は8という数字で表されます。

+-+-+-+-+
|Q| | | |   1000
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

この列の一番左には1があるので、2進数では1000となります。
左から3番目のマスにクイーンが置かれた場合、その列は2、つまり0010で表されます。

+-+-+-+-+
| | |Q| |   0010
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

1: 0001
+-+-+-+-+
| | | |Q| 
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

2: 0010
+-+-+-+-+
| | |Q| | 
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

4: 0100
+-+-+-+-+
| |Q| | | 
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

8: 1000
+-+-+-+-+
|Q| | | | 
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

1、2、4、8以外の数字は、

9→1001
+-+-+-+-+
|Q| | |Q| 
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

15→1111
+-+-+-+-+
|Q|Q|Q|Q| 
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

のように、2つ以上のマスの占有を表すのに使うことができます。

コンフリクトの列が5(0101)の場合、左から1番目と3番目のマスが、他のクイーンとぶつからない唯一の空きマスであることを示し、この2マスに次のクイーンを配置することになります。

5→0101
+-+-+-+-+
| |Q| |Q| 
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

実践、ビットマップ！

Ｎ５のボードレイアウト

 4 2 0 3 1  ↓ bitmapで表現
+-+-+-+-+-+
| | | | |O| 00001
+-+-+-+-+-+
| | |O| | | 00100
+-+-+-+-+-+
|O| | | | | 10000
+-+-+-+-+-+
| | | |O| | 00010
+-+-+-+-+-+
| |O| | | | 01000
+-+-+-+-+-+

各行(row)の状態をbitwise（ビットワイズ）で表現します。
クイーンが置いてある位置のbit（ビット）をON（１）にします。

バックトラッキングは行(row=0)から下に向かって順に、クイーンが配置できた場所のbitをON（１）にして、その後rowが一つインクリメントします。

 4         ↓ bitmapで表現
+-+-+-+-+-+
| | | | |O| 00001
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+

 4 2       ↓ bitmapで表現
+-+-+-+-+-+
| | | | |O| 00001
+-+-+-+-+-+
| | |O| | | 00100
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+

 4 2 0     ↓ bitmapで表現
+-+-+-+-+-+
| | | | |O| 00001
+-+-+-+-+-+
| | |O| | | 00100
+-+-+-+-+-+
|O| | | | | 10000
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+

 4 2 0 3   ↓ bitmapで表現
+-+-+-+-+-+
| | | | |O| 00001
+-+-+-+-+-+
| | |O| | | 00100
+-+-+-+-+-+
|O| | | | | 10000
+-+-+-+-+-+
| | | |O| | 00010
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+

 4 2 0 3 1  ↓ bitmapで表現
+-+-+-+-+-+
| | | | |O| 00001
+-+-+-+-+-+
| | |O| | | 00100
+-+-+-+-+-+
|O| | | | | 10000
+-+-+-+-+-+
| | | |O| | 00010
+-+-+-+-+-+
| |O| | | | 01000
+-+-+-+-+-+

効き筋

次に、効き筋をチェックするためにさらに３つのビットフィールドを用意します。

left
+-+-+-+-+-+
| | | |Q| |
+-+-+-+-+-+
| | |L| | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

down
+-+-+-+-+-+
| | | |Q| |
+-+-+-+-+-+
| | | |D| |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

right
+-+-+-+-+-+
| | | |Q| |
+-+-+-+-+-+
| | | | |R|
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

左下に効き筋が進む(left)、真下に効き筋が進む(down)、右下に効き筋が進む(right)３つです。
その３つのビットフィールドをそれぞれ、left, down, right と呼ぶことにします。

まずは row0 にクイーンを配置します。

Qの配置
+-+-+-+-+-+
| | | |Q| | 00010
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

次に、row0 のビットフィールドから row+1 番目のビットフィールド、ようするにひとつ下の row1 に探索を進め、

Qの配置
+-+-+-+-+-+
| | | |Q| | 00010
+-+-+-+-+-+
| | | | | | ←ここ
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

row0のビットフィールドでクイーンが配置されている bit と、

Qの配置
+-+-+-+-+-+
| | | |Q| | 00010 = bit
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

３つのビット left down right を使って、効き筋をチェックします。

効き筋は「ＯＲ演算」を使います。

ビット演算に関しては以下のリンクがおすすめです。
ビット演算入門

leftはひとつ左に

left
+-+-+-+-+-+
| | | |Q| | 00010
+-+-+-+-+-+
| | |L| | | 00100
+-+-+-+-+-+

downはそのまま下に、

down
+-+-+-+-+-+
| | | |Q| | 00010
+-+-+-+-+-+
| | | |D| | 00010
+-+-+-+-+-+

rightはひとつ右へ

right
+-+-+-+-+-+
| | | |Q| | 00010
+-+-+-+-+-+
| | | | |R| 00001
+-+-+-+-+-+

こういったロジックで row+1 番目の効き筋をチェックします。

bit（ビット）

クイーンの位置は「Q」です。
Qを配置した場合、そのposition（場所）はbitで表します。
bit（ビット）には、クイーンが配置されるとその位置が格納されるわけです。

以下の場合、bitは 00010 となります。

row0にQが配置された

+-+-+-+-+-+
| | | |Q| | 00010
+-+-+-+-+-+

ここでbitの操作が複雑となる原因のひとつ、
「00010」というクイーンの位置情報は、そのままbitに格納されるのではありません。

bitには00010 という場所の情報が格納されるわけですが、

「00001」の場合は「 1」
「00010」の場合は「 2」
「00100」の場合は「 4」
「01000」の場合は「 8」
「10000」の場合は「16」

が格納されることになります。

「はぁ？」

まず、
「00001」という並びは０と１でなりたつ表現方法で「２進数」といいます。
また、１０で桁上りをする表現方法はおなじみの「１０進数」といいます。

00010   　２進数
    2   １０進数 (00010を１０進数にすると 2 になる）

２進数を１０進数に置き換える早見表

10進数  128  64  32  16   8   4   2   1
 2進数    0   0   0   0   0   0   0   0

２進数 00010 を１０進数に置き換えた値が知りたいは、早見表を使うと１０進数では 4 となります。

２進数を１０進数に置き換える早見表
10進数  16   8   4   2   1
 2進数   0   0   1   0   0

ということで、クイーンの位置が 00100 の場合は、4 が bitに格納されます。

bashでは２進数を１０進数に変換して出力する方法が用意されています。

bash-3.2$ echo $(( 2#00001 ))
1
bash-3.2$ echo $(( 2#00010 ))
2
bash-3.2$ echo $(( 2#00100 ))
4
bash-3.2$ echo $(( 2#01000 ))
8
bash-3.2$ echo $(( 2#10000 ))
16
bash-3.2$

＃（シャープ）の前の数字は２進数であることを示しています。
２進数 00100 の１０進数の値が知りたければ、次のようにします。

bash-3.2$ echo $(( 2#00100 ))
4

余談ですが（余談ということでもないのですが）、
Ｎが８の場合で、00010000 というクイーン配置の場合

10進数  128  64  32  16   8   4   2   1
 2進数    0   0   0   1   0   0   0   0

早見表の通り、１０進数では「16」となります。
当然、bashでも求めることができます。

bash-3.2$ echo $(( 2#00010000 ))
16

さらに余談ですが（これは本当に余談）、ビットフィールドに複数のbitがON（１）である場合、例えば「00101010」のような場合は、以下のように計算します。
（（一行にクイーンが３つもある！！）

00101010 
10進数  128  64  32  16   8   4   2   1
 2進数    0   0   1   0   1   0   1   0

この場合は、bitが立っている（と言います）10進数の値をを足し合わせることで表現できます。

ビットが立っている（１となっている）のは、３２と８と２ですから、

32 + 8 + 2 = 42

となります。

bashでも確認してみます。

bash-3.2$ echo $(( 2#00101010 ))
42

おお、いい感じですね。着いてきていますか？

Qの位置を確認

では、まずはQのposition（位置）を確認します。

Q
+-+-+-+-+-+
| | | |Q| | 00010=bit といいます。
+-+-+-+-+-+
| | | | | | 
+-+-+-+-+-+

Qのpositionは 00010 です。
１０進数では以下の早見表で見つけると良いです。

Qが置かれているbitの値は「00010」です

10進数  16   8   4   2   1
 2進数   0   0   0   1   0

10進数では「2」ですね。

まず、Qのpositionがわかりました。
Qのpositionをbitと言います。
通常、bitは変数名もbitとします。

bit = Q = 2#00010 = 2

row + 1 のleftの効き筋をチェック）してみます

left
+-+-+-+-+-+
| | | |Q| | 00010 (`bit`)
+-+-+-+-+-+
| | |L| | | ←ここ
+-+-+-+-+-+

「L」は「Q」の真下（row+1）を左に一つずらした位置となります。
ビット演算では以下のようになります。Lはleftを表しています。

( left | bit)<<1

( left | bit) といった表現を「ＯＲ演算」と言います。

left にはこの段階では値が何も入っていませんので「0」となります。
要するに初期値「０」のまま計算します。

前項で求めたとおり、Qであるbitは以下の通りでした。

bit = Q = 2#00010 = 2

leftは、初期値「０」な訳ですから、

( left | bit )
(   0  |  2  )

という計算式になります。
bashで計算してみましょう。

bash-3.2$ echo $(( (2|0) ))
2
bash-3.2$

「２」とでました。
さらに左に一つシフト（«1）してみます。
こうなりますね。

( left | bit )<<1
(   0  |  2  )<<1

bashで計算してみます。

bash-3.2$ echo $(( (2|0)<<1 ))
4
bash-3.2$

「４」とでました。
「４」の２進数はなんでしょう？
さっそく早見表で確認しましょう。

10進数  16   8   4   2   1
 2進数   0   0   1   0   0

00100 という事ですね。

Qが置かれている場所が「00010」で、
Lは「00100」となったわけです。
図で表すと以下のとおりです。

left
+-+-+-+-+-+
| | | |Q| | 00010 (bit)
+-+-+-+-+-+
| | |L| | | 00100 (left|bit)<<1
+-+-+-+-+-+

ということで、Qの位置から左に一つずれているのがわかります。
Qを配置してleftを使って左下の効きを簡単に求めることができました。

left  = ( left |  bit  )<<1
00100 = (  0   | 00010 )<<1
  4   = (  0   |   2   )<<1

row0にある Q の位置「00010」の、ひとつ下の row1 のleftの効き筋は (left|bit)<<1 という計算式を用いて、「00100」となりました。
言い換えると、Qの位置をbitにして、(left|bit)<<1とすることで、ビットの位置を一つ左にシフトして、Qのleftの効き筋を求めることができたということになります。

row + 1 のdownの効き筋をチェック）してみます

leftの場合は、( left | bit )«1 ということをしてQの位置から左に一つずらした位置を求めました。

downはleftのように左に一つずらしたりする必要はありません。
Qの位置からましたに下ろすだけですから値は同じなのです。

down
+-+-+-+-+-+
| | | |Q| | 00010
+-+-+-+-+-+
| | | |D| | 00010 (down|bit)
+-+-+-+-+-+

down  = ( down |  bit  )
00010 = (  0   | 00010 )
  2   = (  0   |   2   )

bashでも確認してみます。

bash-3.2$ echo $(( (0|2) ))
2
bash-3.2$

down は 2#00010 ですので 2 です。

ここまでをまとめると以下のとおりです。

bit = Q = 2#00010 = 2
10進数  16   8   4   2   1
 2進数   0   0   0   1   0

left = (left|bit)<<1 = 2#00100 = 4
10進数  16   8   4   2   1
 2進数   0   0   1   0   0

down = (down|bit)    = 2#00010 = 2
10進数  16   8   4   2   1
 2進数   0   0   0   1   0

row + 1 のrightの効き筋をチェック

rightはleft同様にシフトするわけですが、今度は右へシフトします。

right
+-+-+-+-+-+
| | | |Q| | 00010 (bit)
+-+-+-+-+-+
| | | | |R| 00001 (R)  (right|bit)>>1
+-+-+-+-+-+

right = ( right |  bit  )>>1
00010 = (   0   | 00010 )>>1
  1   = (   0   |   2   )>>1

bashでも確認してみます。

bash-3.2$ echo $(( (0|2)>>1 ))
1
bash-3.2$

ここまでをまとめると以下のとおりです。

bit = Q = 2#00010 = 2
10進数  16   8   4   2   1
 2進数   0   0   0   1   0

left = (left|bit)<<1 = 2#00100 = 4
10進数  16   8   4   2   1
 2進数   0   0   1   0   0

down = (down|bit)    = 2#00010 = 2
10進数  16   8   4   2   1
 2進数   0   0   0   1   0

right =(right|bit)>>1= 2#00001 = 1
10進数  16   8   4   2   1
 2進数   0   0   0   0   1

マスクビット

ビットの使い方として最も多いものの 1 つがマスクビットです。なじみの深いもので言えば、IPアドレスのマスクビットや割り込み制御のマスクビットなどが挙げられます。多種多様な場面で使用されるマスクビットですが、基本的なアイディアは共通で、

・複数のフラグをまとめて立てる
・複数のフラグをまとめて消す
・必要な情報だけを取り出すために、マスクした部分の情報のみを取り出す
といったものを効率良く実現するものです。
現在のフラグ状態を表すビットを bit として、マスクビットを mask としたとき

概要	実装
mask で表された部分のフラグをまとめて立てる	bit ｜= mask
mask で表された部分のフラグをまとめて消す	bit &= ~mask
mask で表された部分の情報のみを取り出したもの	bit & mask
mask で表された部分のどれかのフラグが立っているかどうか	if (bit & mask)
mask で表された部分のすべてのフラグが立っているかどうか	if ((bit & mask) == mask)

mask（マスク）

ここまでで３つのフラグを用いてQの効き筋を求めてきました。

left+down+right
+-+-+-+-+-+
| | | |Q| | 00010 (bit)
+-+-+-+-+-+
| | |L|D|R| 00111 (left|down|right)
+-+-+-+-+-+

３箇所の効き筋を演算子を使うと

(left|down|right)

となり、こうした表現を「ＯＲ演算」と言います。

さて、row + 1 番目のビットフィールドを探索して、left down right の３つのbitフラグを「ＯＲ演算」したビットフィールドを作りました。

ＯＮ（１）になっている位置は効き筋に当たるので置くことができません。

rowにQを配置して、

+-+-+-+-+-+  row
| | | |Q| |   0  今、自分はここにいて
+-+-+-+-+-+
| | | | | |   1
+-+-+-+-+-+
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

自分がいる row の一つしたの「row+1」のビットフィールドを探索するために、

+-+-+-+-+-+  row
| | | |Q| |   0  
+-+-+-+-+-+
|*|*|*|*|*|   1  この行(row)を順番に探索する
+-+-+-+-+-+
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

left down right の３つのフラグを使って、効きををチェックします。

left down right のいずれかがＯＮ（１）になっていたら効き筋に当たるから、その場所にはクイーンは配置できませんね。
という意味になります。

+-+-+-+-+-+  row
| | | |Q| |   0  bit  =      Q        = 2#00010 = 2
+-+-+-+-+-+      left = (left|bit)<<1 = 2#00100 = 4
|*|*|L|D|R|   1  down = (down|bit)    = 2#00010 = 2
+-+-+-+-+-+      right= (right|bit)>>1= 2#00001 = 1
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

そこで、上記の図の２箇所（アスタリスク＊の場所）がクイーンを配置することがが可能です。
この２箇所のアスタリスクは場所を簡単に得ることができます。

以下の通り、left は4 down は2 right は1 です。

bit  =      Q        = 2#00010 = 2

left = (left|bit)<<1 = 2#00100 = 4
down = (down|bit)    = 2#00010 = 2
right= (right|bit)>>1= 2#00001 = 1

効き筋 (left|down|right) は、次のように求めることができます。

(4|2|1)

と、なります。
bashで確認すると以下のとおりです。

bash-3.2$ echo $(( (4|2|1) ))
7
bash-3.2$

「７」となりました。これを２進数で表すと

bash-3.2$ bc <<<"ibase10;obase=2;7"
111
bash-3.2$

「１１１」ですから５ビットにすると
2#00111 となります。

そこで、以下のアスタリスクの部分を求めるには「反転」という演算をおこないます。

+-+-+-+-+-+  row
| | | |Q| |   0  bit  =      Q        = 2#00010 = 2
+-+-+-+-+-+      left = (left|bit)<<1 = 2#00100 = 4
|*|*|L|D|R|   1  down = (down|bit)    = 2#00010 = 2
+-+-+-+-+-+      right= (right|bit)>>1= 2#00001 = 1
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

ここで、2#11000を求めることができれば、それがクイーンを配置することができる場所ということになります。

2#11000 をbashで求めると24になります。

bash-3.2$ echo $(( 2#11000 ))
24
bash-3.2$

演算で求める場合は、「反転」という演算を使います。
(L|D|R) の反転はチルダ「〜」を使います。

~(L|D|R)

では、先に求めた「２４」になるかを確認してみましょう。

bash-3.2$ echo $(( (4|2|1) ))
7
bash-3.2$ echo $(( ~(4|2|1) ))
-8
bash-3.2$

なりませんね。。。

ここでmask(マスク）を使います。
maskとは、ビットフィールドのビットをすべて立てたものです。

+-+-+-+-+-+  row
| | | |Q| |   0  
+-+-+-+-+-+      
|M|M|M|M|M|   1  mask=2#11111
+-+-+-+-+-+      
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

このmaskは簡単に求めることができます。

mask=$(( (1<<size)-1 ));

Ｎ５の場合、２進数で求めると「３１」になります。

bash-3.2$ echo $(( 2#11111 ))
31

maskは、size=5 ( 1<<size )-1 という計算式で求めることができます。

bash-3.2$ echo $(( (1<<5)-1 ))
31

このmaskを使って
１．left down rightの３つのビットを使って効きの場所を特定

(left|down|right)

+-+-+-+-+-+  row
| | | |Q| |   0  
+-+-+-+-+-+      
| | |L|D|R|   1  2#00111
+-+-+-+-+-+      
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

２．反転させる

# 2#00111
~(left|down|right) = -8
# 2#11000

２．maskですべての配置箇所のビットをＯＮ（１）にする

maskを使ってすべてのビットを立てる

size=5;
mask=$(( (1<<size)-1 ));
+-+-+-+-+-+  row
| | | |Q| |   0  
+-+-+-+-+-+      
|M|M|M|M|M|   1  2#11111 = 31
+-+-+-+-+-+      
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

３．maskから~(left|down|right)を間引いた値をbitmapに格納

# クイーンが配置可能な位置を表す
bitmap=$(( mask&~(left|down|right) ))
+-+-+-+-+-+  row
| | | |Q| |   0  
+-+-+-+-+-+      
|1|1|0|0|0|   1  2#11000 = 24
+-+-+-+-+-+      
| | | | | |   2
+-+-+-+-+-+
| | | | | |   3
+-+-+-+-+-+
| | | | | |   4
+-+-+-+-+-+

 (left|down|right)  2#00111
~(left|down|right)  2#11000
mask                2#11111
----------------------------
AND                 2#11000  24 bitmap

おおお、２４になりました。
bitmapには２４が格納されるわけです。

これで効きのない場所を特定することができました。

１がクイーンを配置できる場所、いわゆる効き筋に当たらない場所ということになります。

あとは、効き筋に当たらない場所を順番にQを置いて行けばよいということになります。

順番にひとつひとつつまみ出して行く方法は後述します。

ここまでの処理をbashで書くと以下の通りになります。

#!/usr/bin/bash

mask=31; # 2#11111
left=4;  # 2#00100
down=2;  # 2#00010
right=1; # 2#00001

# (left|down|right)を反転させてmaskで間引く
# クイーンが配置可能な位置を表す
bitmap=$(( mask&~(left|down|right) ))
echo "$bitmap"  # 24

# 間引いた１０進数を２進数にして確認
bc<<<"ibase=10;obase=2;$bitmap"
# 11000

実行結果は以下のとおりです。

bash-3.2$ bash masktest.sh
11000

ビットマップで肝となるところを重点的に

# クイーンが配置可能な位置を表す
bitmap=$(( mask&~(left|down|right) ))

# 一番右のビットを取り出す
bit=$(( -bitmap & bitmap ));    

# 配置可能なパターンが一つずつ取り出される
bitmap=$((bitmap&~bit)) ;       

# Qを配置
board[$row]="$bit";        # Qを配置

# 再帰
bitmap_R "$size" "$((row+1))" "$(( (left|bit)<<1 ))" "$((down|bit))" "$(( (right|bit)>>1 ))";

bitmap=$(( mask&~(left|down|right) ))

クイーンが配置可能な位置を表す

bit=$(( -bitmap & -bitmap ));

while中の各繰り返しで、bit に、配置できる可能性と配置できない可能性をAND演算した結果をbitにセットしています。この結果、bit は、bitmap の最下位ビットを除いて、すべて0に設定し、Qを配置します。
もう少し噛み砕いて説明すると、単に最初の非ゼロビット（つまり最初に利用できる場所である１）を bit という変数に格納するだけです。
その bit （ビットが0010なら3列目）は、次のクイーンを置く場所となります。
つまり、bitmapの列を0にすることで、現在の位置が「取られた」ことを示すだけです。
こうすることで、whileループ中で、「取られた」場所を再度試す必要がなくなるということになります。

bitmap=$((bitmap&~bit)) ;

配置可能なパターンが一つずつ取り出され、bitmap の最下位ビットを開放、次のループに備え、新しい最下位ビットを探索、再帰的な呼び出しを行い、次の行のビットフィールドであるbitmap を更新します。
bit には、Qの場所を表す1 が1つだけ入ったビットフィールが格納されています。
渡された競合情報とOR演算 することで、再帰呼び出しの競合候補として追加されます。

board[$row]="$bit"; # Qを配置

要するにQを配置するわけです。

bitmap_R “$size” “$((row+1))” “$(( (left|bit)«1 ))” “$((down|bit))” “$(( (right|bit)»1 ))";

ソースの中も最も混乱する行だと思います。
演算子 >>1 と 1<< は、ビットフィールド列すべてのビットをそれぞれ右、または左に1桁移動させるだけです。

つまり、(left|bit)<<1 を呼ぶと、「leftとbitをOR演算で結合し、結果のすべてを1桁左に移動させる」という意味になります。

具体的には、left が 0001 （現在の行の4列目を通る右上から左下までの対角線が占有されていることを意味する）、bit が 0100（現在の行の2列目にクイーンを置く予定であることを意味する）の場合、(left|bit) の結果は 0101 （現在の行の2列目にクイーンを置いた後、右上から左下までの対角線2本目と4本目が占有されることになります）。

ここで、<< 演算子を加えると、(left|bit)<<1 となり、前の箇条書きで計算した 0101 を、すべて左に1つずつ移動させます。したがって、結果は 1010 となります。

さて、ここからが本当に難しいところなのですが、bitmap_R を再度呼び出す前に、なぜ1桁ずつ移動させるのでしょうか。

row が一番上の行から始まり、下に移動する場合、新しい行に移動するたびに、「占有対角線」のトラッキング変数である left と right を最新に保つ必要があります。

そこで、下のボートレイアウトを例にとると、

+-+-+-+-+  row
| | |Q| |   0  
+-+-+-+-+      
|Q| | | |   1  
+-+-+-+-+      
| | | |Q|   2
+-+-+-+-+
| |Q| | |   3
+-+-+-+-+

最上段3列目にクイーンを置くと、その瞬間の left down right はそれぞれ0010、0010、0010となる。

しかし、再びbitmap_Rを呼び出して次の行に進むと、2行目では、2列目、3列目、4列目のすべてが、これまでに配置した1つのクイーンによって「攻撃されている」ことがわかります。
具体的には、3列目が占領され（downは0010）、2行目の4列目を通る左上から右下の対角線が占領され（だからrightは0001）、2行目の2列目を通る右上から左下の対角線が占領されています（だからleftは0100）。

+-+-+-+-+  row
| | |Q| |   0  
+-+-+-+-+      
| |x|x|x|   1  
+-+-+-+-+      
| | | | |   2
+-+-+-+-+
| | | | |   3
+-+-+-+-+

そのため、「行を下る」たびに対角線を移動させる必要があります。
そうしないと、どの対角線が「占有」されているかという知識が、現在の行に対して正しくなくなるからです。

上記の例からわかるように、$(( ~(left|down|right )) を計算すると2#1000 となり、2行目の安全な場所は1列目のみであることがわかります。

斜めの効き筋

ビットマッププログラムのポイントは、斜めの利き筋のチェックをビット演算で行うことです。

    0 1 2 3 4
  *-------------
  | . . . . . .
  | . . . -3. .  0x02
  | . . -2. . .  0x04
  | . -1. . . .  0x08 (1 bit 右シフト)
  | Q . . . . .  0x10 (Q の位置は 4)
  | . +1. . . .  0x20 (1 bit 左シフト)  
  | . . +2. . .  0x40
  | . . . +3. .  0x80
  *-------------

この演算式の意味を理解するには、負の値がコンピュータにおける２進法ではどのように表現されているのかを知る必要があります。

負の値を２進数で表すと次のようになります。

 00000011   3
 00000010   2
 00000001   1
 00000000   0
 11111111  -1
 11111110  -2
 11111101  -3

正の値を負の値（補数と言います）にするときは、Ｒをビット反転してから＋１します。


 00000001   1
 11111110   反転
 11111111   -1 （1を加える）

 00000010   2
 11111101  反転
 11111110  -2  （１を加える）

加えるところがわかりにくいですね。

 00000001   1

に１を加えると

 00000010   2

さらに１を加えると

00000011   3

と、なります。
１０進数の足し算と２進数のインクリメントは異なるところに注意が必要です。

ここで、正の値２２と−２２をＡＮＤ演算すると以下のようになります。

     00010110   22
 AND 11101010  -22
------------------
     00000010

Ｎを２進法で表したときの一番下位のＯＮビットがひとつだけ抽出される結果が得られ、極めて簡単な演算によって１ビット抽出を実現させていることが重要です。

余談ですが、
bashで２進数を１０進数に変換するには以下のようにしました。

bash-3.2$ echo $(( 2#01000 ));
8

bashで１０進数を２進数に変換するには以下のようにします。

bash-3.2$ bc <<<"ibase=10;obase=10;8"
1000

余談終わり。

そこで下のようなwhile文を書けば、ループが bitmap のONビットの数の回数だけループすることになり、配置可能なパターンをひとつずつ全く無駄がループがなく生成されることになります。

  bitmap=$(( mask&~(left|down|right) )); # クイーンが配置可能な位置を表す
  while (( bitmap ));do
    bit=$((-bitmap&bitmap)) ;  # 一番右のビットを取り出す
    bitmap=$((bitmap&~bit)) ;  # 配置可能なパターンが一つずつ取り出される
    board[$row]="$bit";        # Qを配置
    bitmap_R "$size" "$((row+1))" "$(( (left|bit)<<1 ))" "$((down|bit))" "$(( (right|bit)>>1 ))";
  done

left down right は、Qが配置されるたびに、その効き筋を足し合わせ、すべてのrowの効き筋に対応します。

再帰では、こうしたことをプログラマが意識することなく実現できるわけですが、非再帰の場合は、left down right を配列などで効き筋を覚えておく必要が出てきます。

それはどうとして猛烈にわかりやすい図がありました。

ビットマップソースコード

ソース下部の再起・非再帰を切り替えて実行してください。

#!/usr/bin/bash

declare -i TOTAL=0;     # カウンター
#
: 'ボードレイアウトを出力';
function printRecord()
{
  size="$1";
  flag="$2"; # bitmap版は1 それ以外は 0
  echo "$TOTAL";
  sEcho=" ";  
  : 'ビットマップ版
     ビットマップ版からは、左から数えます
     上下反転左右対称なので、これまでの上から数える手法と
     rowを下にたどって左から数える方法と解の数に変わりはありません。
     0 2 4 1 3 
    +-+-+-+-+-+
    |O| | | | | 0
    +-+-+-+-+-+
    | | |O| | | 2
    +-+-+-+-+-+
    | | | | |O| 4
    +-+-+-+-+-+
    | |O| | | | 1
    +-+-+-+-+-+
    | | | |O| | 3
    +-+-+-+-+-+
  ';
  if ((flag));then
    for((i=0;i<size;i++)){
      for((j=0;j<size;j++)){
        if (( board[i]&1<<j ));then
          sEcho="${sEcho}$((j)) ";
        fi 
      }
    }
  else 
  : 'ビットマップ版以外
     (ブルートフォース、バックトラック、配置フラグ)
     上から数えます
     0 2 4 1 3 
    +-+-+-+-+-+
    |O| | | | |
    +-+-+-+-+-+
    | | | |O| |
    +-+-+-+-+-+
    | |O| | | |
    +-+-+-+-+-+
    | | | | |O|
    +-+-+-+-+-+
    | | |O| | |
    +-+-+-+-+-+

     ';
    for((i=0;i<size;i++)){
      sEcho="${sEcho}${board[i]} ";
    }
  fi
  echo "$sEcho";

  echo -n "+";
  for((i=0;i<size;i++)){
    echo -n "-";
    if((i<(size-1)));then
      echo -n "+";
    fi
  }
  echo "+";
  for((i=0;i<size;i++)){
    echo -n "|";
    for((j=0;j<size;j++)){
      if ((flag));then
        if (( board[i]&1<<j ));then
          echo -n "O";
        else
          echo -n " ";
        fi
      else
        if((i==board[j]));then
          echo -n "O";
        else
          echo -n " ";
        fi
      fi
      if((j<(size-1)));then
        echo -n "|";
      fi
    }
  echo "|";
  if((i<(size-1)));then
    echo -n "+";
    for((j=0;j<size;j++)){
      echo -n "-";
      if((j<(size-1)));then
        echo -n "+";
      fi
    }
  echo "+";
  fi
  }
  echo -n "+";
  for((i=0;i<size;i++)){
    echo -n "-";
    if((i<(size-1)));then
      echo -n "+";
    fi
  }  
  echo "+";
  echo "";
}
#
: '非再帰版ビットマップ';
function bitmap_NR()
{
  local -i size="$1";
  local -i row="$2";
  local -i mask=$(( (1<<size)-1 ));
  local -a left[$size];
  local -a down[$size];
  local -a right[$size];
  local -a bitmap[$size]
  local -i bitmap[$row]=mask;
  local -i bit=0;
  while ((row>-1));do
    if (( bitmap[row]>0 ));then
      bit=$(( -bitmap[row]&bitmap[row] ));  # 一番右のビットを取り出す
      bitmap[$row]=$(( bitmap[row]^bit ));  # 配置可能なパターンが一つずつ取り出される
      board[$row]="$bit";                   # Qを配置
      if (( row==(size-1) ));then
        ((TOTAL++));
        printRecord "$size" "1";            # 出力 1:bitmap版 0:それ以外
        ((row--));
      else
        local -i n=$((row++));
        left[$row]=$(((left[n]|bit)<<1));
        down[$row]=$(((down[n]|bit)));
        right[$row]=$(((right[n]|bit)>>1));
        board[$row]="$bit";                 # Qを配置
        # クイーンが配置可能な位置を表す
        bitmap[$row]=$(( mask&~(left[row]|down[row]|right[row]) ));
      fi
    else
      ((row--));
    fi
  done 
}
#
: '再帰版ビットマップ';
function bitmap_R()
{
  local -i size="$1"; local -i row="$2";
  local -i left="$3"; local -i down="$4"; local -i right="$5";
  local -i bitmap=;
  local -i bit=;
  local -i col=0;                     # 再帰に必要
  local -i mask=$(( (1<<size)-1 ));
  if (( row==size ));then
     ((TOTAL++));
     printRecord "$size" "1";         # 出力 1:bitmap版 0:それ以外
  else
    bitmap=$(( mask&~(left|down|right) )); # クイーンが配置可能な位置を表す
    while (( bitmap ));do
      bit=$((-bitmap&bitmap)) ;       # 一番右のビットを取り出す
      bitmap=$((bitmap&~bit)) ;       # 配置可能なパターンが一つずつ取り出される
      board[$row]="$bit";             # Qを配置
      bitmap_R "$size" "$((row+1))" "$(( (left|bit)<<1 ))" "$((down|bit))" "$(( (right|bit)>>1 ))";
    done
  fi
}
# 非再帰版ビットマップ
# time bitmap_NR 5 0;
#
# 再帰版ビットマップ
 time bitmap_R 5 0 0 0 0;    
 echo "$TOTAL";
#
exit;

まとめ版ソースコード

ソースの一番下で、再帰・非再帰を切換えて事項してください。

#!/usr/bin/bash

declare -i COUNT=0;
declare -i TOTAL=0;     # カウンター
declare -i UNIQUE=0;    # ユニークユーザー
declare -i DISPLAY=0;   # ボード出力するか
#
: 'ボードレイアウトを出力 ビットマップ対応版';
function printRecord()
{
  size="$1";
  flag="$2"; # bitmap版は1 それ以外は 0
  echo "$TOTAL";
  sEcho=" ";  
  : 'ビットマップ版
     ビットマップ版からは、左から数えます
     上下反転左右対称なので、これまでの上から数える手法と
     rowを下にたどって左から数える方法と解の数に変わりはありません。
     0 2 4 1 3 
    +-+-+-+-+-+
    |O| | | | | 0
    +-+-+-+-+-+
    | | |O| | | 2
    +-+-+-+-+-+
    | | | | |O| 4
    +-+-+-+-+-+
    | |O| | | | 1
    +-+-+-+-+-+
    | | | |O| | 3
    +-+-+-+-+-+
  ';
  if ((flag));then
    for((i=0;i<size;i++)){
      for((j=0;j<size;j++)){
        if (( board[i]&1<<j ));then
          sEcho="${sEcho}$((j)) ";
        fi 
      }
    }
  else 
  : 'ビットマップ版以外
     (ブルートフォース、バックトラック、配置フラグ)
     上から数えます
     0 2 4 1 3 
    +-+-+-+-+-+
    |O| | | | |
    +-+-+-+-+-+
    | | | |O| |
    +-+-+-+-+-+
    | |O| | | |
    +-+-+-+-+-+
    | | | | |O|
    +-+-+-+-+-+
    | | |O| | |
    +-+-+-+-+-+

     ';
    for((i=0;i<size;i++)){
      sEcho="${sEcho}${board[i]} ";
    }
  fi
  echo "$sEcho";

  echo -n "+";
  for((i=0;i<size;i++)){
    echo -n "-";
    if((i<(size-1)));then
      echo -n "+";
    fi
  }
  echo "+";
  for((i=0;i<size;i++)){
    echo -n "|";
    for((j=0;j<size;j++)){
      if ((flag));then
        if (( board[i]&1<<j ));then
          echo -n "O";
        else
          echo -n " ";
        fi
      else
        if((i==board[j]));then
          echo -n "O";
        else
          echo -n " ";
        fi
      fi
      if((j<(size-1)));then
        echo -n "|";
      fi
    }
  echo "|";
  if((i<(size-1)));then
    echo -n "+";
    for((j=0;j<size;j++)){
      echo -n "-";
      if((j<(size-1)));then
        echo -n "+";
      fi
    }
  echo "+";
  fi
  }
  echo -n "+";
  for((i=0;i<size;i++)){
    echo -n "-";
    if((i<(size-1)));then
      echo -n "+";
    fi
  }  
  echo "+";
  echo "";
}
#
: '非再帰ビットマップ版';
function bitmap_NR()
{
   local -i size="$1";
  local -i row="$2";
  local -i mask=$(( (1<<size)-1 ));
  local -a left[$size];
  local -a down[$size];
  local -a right[$size];
  local -a tmpBoard[$size];             #各rowのleft,right,downを足した配列
  local -a board[$size];                #クイーンを配置した場所を格納する配列
  local -i bitmap=mask;
  local -i bit;
  while true ;do
    if (( bitmap ));then
      bit=$(( -bitmap&bitmap ));        # 一番右のビットを取り出す
      bitmap=$(( bitmap^bit ));         # 配置可能なパターンが一つずつ取り出される
      board[$row]="$bit";               # Qを配置
      if (( row==(size-1) ));then
        ((TOTAL++));
        if ((DISPLAY==1));then
          printRecord "$size" "1";        # 出力 1:bitmap版 0:それ以外
        fi
        bitmap=tmpBoard[row];
        ((--row));
      else
        local -i n=$((row++));
        left[$row]=$(((  left[n]|bit)<<1 ));
        down[$row]=$((   down[n]|bit ));
        right[$row]=$(((right[n]|bit)>>1 ));
        tmpBoard[$row]=$bitmap;
        board[$row]="$bit";             # Qを配置
        # クイーンが配置可能な位置を表す
        bitmap=$(( mask&~(left[row]|down[row]|right[row]) ));
      fi
    else
      bitmap=tmpBoard[row];
      if (( row==0));then
        break ;
      fi
      (( row-- ));
    fi
  done  
}
#
: '再帰版ビットマップ';
function bitmap_R()
{
  local -i size="$1"; 
  local -i row="$2";
  local -i mask="$3";
  local -i left="$4"; 
  local -i down="$5"; 
  local -i right="$6";
  local -i bitmap=;
  local -i bit=;
  local -i col=0;                     # 再帰に必要
  if (( row==size ));then
    ((TOTAL++));
    if ((DISPLAY==1));then
      printRecord "$size" "1";         # 出力 1:bitmap版 0:それ以外
    fi
  else
    bitmap=$(( mask&~(left|down|right) )); # クイーンが配置可能な位置を表す
    while (( bitmap ));do
      bit=$((-bitmap&bitmap)) ;       # 一番右のビットを取り出す
      bitmap=$((bitmap&~bit)) ;       # 配置可能なパターンが一つずつ取り出される
      board[$row]="$bit";             # Qを配置
      bitmap_R "$size" "$((row+1))" "$mask" "$(( (left|bit)<<1 ))" "$((down|bit))" "$(( (right|bit)>>1 ))";
    done
  fi
}
#
: '非再帰版配置フラグ(right/down/left flag)';
function rdlFlag_NR()
{
  local -i size="$1";
  local -i row="$2"
  local -i matched=0;
  for ((i=0;i<size;i++)){ board[$i]=-1; }
  while ((row>-1));do
    matched=0;
    for ((col=board[row]+1;col<size;col++)){
      if (( !down[col]
        &&  !right[col-row+size-1]
        &&  !left[col+row] ));then
        dix=$col;
        rix=$((row-col+(size-1)));
        lix=$((row+col));
        if ((board[row]!=-1));then
          down[${board[$row]}]=0;
          right[${board[$row]}-$row+($size-1)]=0;
          left[${board[$row]}+$row]=0;
        fi       
        board[$row]=$col;   # Qを配置
        down[$col]=1;
        right[$col-$row+($size-1)]=1;
        left[$col+$row]=1;  # 効き筋とする
        matched=1;          # 配置した
        break;
      fi
    }
    if ((matched));then     # 配置済み
      ((row++));            #次のrowへ
      if ((row==size));then
        ((TOTAL++));
        if ((DISPLAY==1));then
          printRecord "$size";# 出力
        fi
        ((row--));
      fi
    else
      if ((board[row]!=-1));then
        down[${board[$row]}]=0;
        right[${board[$row]}-$row+($size-1)]=0;
        left[${board[$row]}+$row]=0;
        board[$row]=-1;
      fi
      ((row--));            # バックトラック
    fi
  done
}
#
: '再帰版配置フラグ';
function postFlag_R()
{
  local -i size="$1";
  local -i row="$2";
  local -i col=0;       # 再帰に必要
  if (( row==size ));then
     ((TOTAL++));
    if (( DISPLAY==1 ));then
      printRecord "$size";# 出力
    fi
  else
    for(( col=0;col<size;col++ )){
      board[$row]="$col";
      if (( down[col]==0 
        && right[row-col+size-1]==0
        && left[row+col]==0));then
        down[$col]=1;
        right[$row-$col+($size-1)]=1;
        left[$row+$col]=1;
        postFlag_R "$size" "$((row+1))";
        down[$col]=0;
        right[$row-$col+($size-1)]=0;
        left[$row+$col]=0;
      fi
    }
  fi
}
#
: 'バックトラック版効き筋をチェック';
function check_backTracking()
{
  local -i row="$1";
  local -i flag=1;
  for ((i=0;i<row;++i)){
    if (( board[i]>=board[row] ));then
      val=$(( board[i]-board[row] ));
    else
      val=$(( board[row]-board[i] ));
    fi
    if (( board[i]==board[row] || val==(row-i) ));then
      flag=0;
    fi
  }
  [[ $flag -eq 0 ]]
  return $?;
}
#
: '非再帰版バックトラック';
function backTracking_NR()
{
  local -i size="$1";
  local -i row="$2";
  for ((i=0;i<size;i++)){ board[$i]=-1; }
  while ((row>-1));do
    local -i matched=0;
    local -i col=0;  
    for((col=board[row]+1;col<size;col++)){
      board[$row]=$col;
      check_backTracking "$row";  # 効きをチェック
      if (($?==1));then # 直前のreturnを利用
        matched=1;
        break;
      fi
    }
    if ((matched));then
      ((row++));
      if ((row==size));then  # 最下部まで到達
        ((row--));
        ((TOTAL++));
        if (( DISPLAY==1 ));then
          printRecord "$size";# 出力
        fi
      fi
    else
      if ((board[row]!=-1));then
        board[$row]=-1;
      fi
      ((row--));
    fi
 done  
}
#
: '再帰版バックトラック';
function backTracking_R()
{
  local -i size="$1";
  local -i row="$2";
  local -i col=0;
  if ((row==size));then
    ((TOTAL++));
    if (( DISPLAY==1 ));then
      printRecord "$size";# 出力
    fi
  else
    for(( col=0;col<size;col++ )){
      board["$row"]="$col";
      check_backTracking "$row";
      if (($?==1));then 
        backTracking_R  $size $((row+1));
      fi
    }
  fi
}
#
: 'ブルートフォース版効き筋をチェック';
function check_bluteForce()
{
  local -i size="$1";
  local -i flag=1;
  for ((r=1;r<size;++r)){
    for ((i=0;i<r;++i)){
      if (( board[i]>=board[r] ));then
        val=$(( board[i]-board[r] ));
      else
        val=$(( board[r]-board[i] ));
      fi

      if (( board[i]==board[r] || val==(r-i) ));then
        flag=0; 
      fi
    }
  }
  [[ $flag -eq 0 ]]
  return $?;
}
#
: '非再帰版ブルートフォース';
function bluteForce_NR()
{
  local -i size="$1";
  local -i row="$2";
  for ((i=0;i<size;i++)){ board[$i]=-1; }
  while ((row>-1));do
    local -i matched=0;
    local -i col=0;  
    for((col=board[row]+1;col<size;col++)){
      board[$row]=$col;
      matched=1;
      break;
    }
    if ((matched));then
      ((row++));
      if ((row==size));then  # 最下部まで到達
        ((row--));
        check_bluteForce "$size";  # 効きをチェック
        if (($?==1));then # 直前のreturnを利用
          ((TOTAL++));
          if (( DISPLAY==1 ));then
            printRecord "$size";# 出力
          fi
        fi
      fi
    else
      if ((board[row]!=-1));then
        board[$row]=-1;
      fi
      ((row--));
    fi
 done  
}
#
: '再帰版ブルートフォース';
function bluteForce_R()
{
  local -i size="$1";
  local -i row="$2";
  local -i col=;
  if ((row==size));then
    check_bluteForce "$size";
    if (( $?==1 ));then 
      ((TOTAL++));
      if (( DISPLAY==1 ));then
        printRecord "$size";# 出力
      fi
    fi
  else
    #for(( col=0;col<(size-row);col++ )){
    for(( col=0;col<size;col++ )){
      board["$row"]="$col";
      bluteForce_R  $size $((row+1));
    }
  fi
}
#
function NQ()
{
  local selectName="$1";
  local -i max=15;
  local -i min=4;
  local -i N="$min";
  local startTime=0;
	local endTime=0;
	local hh=mm=ss=0; 
  echo " N:        Total       Unique        hh:mm:ss" ;
  for((N=min;N<=max;N++)){
    TOTAL=0;
    UNIQUE=0;
    startTime=$(date +%s);# 計測開始時間
    row=0;
    mask=$(( (1<<N)-1 ));
    "$selectName" "$N" 0 "$mask" 0 0 0;

    endTime=$(date +%s); 	# 計測終了時間
    ss=$((endTime-startTime));# hh:mm:ss 形式に変換
    hh=$((ss/3600));
    ss=$((ss%3600));
    mm=$((ss/60));
    ss=$((ss%60));
    printf "%2d:%13d%13d%10d:%.2d:%.2d\n" $N $TOTAL $UNIQUE $hh $mm $ss ;
  } 
}

while :
do
read -n1 -p "
エイト・クイーン メニュー
実行したい番号を選択
8) 非再帰ビットマップ
7) 再帰ビットマップ
6) 非再帰　配置フラグ
5) 再帰　　配置フラグ 
4) 非再帰　バックトラック 
3) 再帰　　バックトラック
2) 非再帰　ブルートフォース 
1) 再帰　　ブルートフォース 

echo "行頭の番号を入力してください";

" selectNo;
echo 
case "$selectNo" in
  8)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ bitmap_NR
    break;
    ;;
  7)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ bitmap_R 
    break;
    ;;
  6)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ rdlFlag_NR
    break;
    ;;
  5)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ postFlag_R;
    break;
    ;;
  4)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ backTracking_NR;
    break;
    ;;
  3)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ backTracking_R;
    break;
    ;;
  2)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ bluteForce_NR;
    break;
    ;;
  1)
    while :
    do 
      read -n1 -p "
      ボード画面の表示は？ 
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo "行頭のアルファベットを入力して下さい";

      " select;
      echo; 
      case "$select" in
        y|Y) DISPLAY=1; break; ;;
        n|N) DISPLAY=0; break; ;;
      esac
    done
    NQ bluteForce_R;
    break;
    ;;
  *)
    ;; 
esac
done
exit;

実行結果

実行結果は以下のとおりです。

bash-3.2$ bash bitmap.sh

エイト・クイーン メニュー
実行したい番号を選択
8) 非再帰ビットマップ
7) 再帰ビットマップ
6) 非再帰　配置フラグ
5) 再帰　　配置フラグ
4) 非再帰　バックトラック
3) 再帰　　バックトラック
2) 非再帰　ブルートフォース
1) 再帰　　ブルートフォース

echo 行頭の番号を入力してください;

8

      ボード画面の表示は？
      y) する（ブルートフォースはおすすめしない）
      n) しない

      echo 行頭のアルファベットを入力して下さい;

      n
 N:        Total       Unique        hh:mm:ss
 4:            2            0         0:00:00
 5:           10            0         0:00:00
 6:            4            0         0:00:00
 7:           40            0         0:00:00
 8:           92            0         0:00:00
 9:          352            0         0:00:01
10:          724            0         0:00:04
:
:
bash-3.2$

参考リンク

以下の詳細説明を参考にしてください。
【参考リンク】Ｎクイーン問題過去記事一覧
 【Github】エイト・クイーンのソース置き場 BashもJavaもPythonも！

Ｎクイーン問題（５０）第七章マルチプロセス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-04-n-queens-suzuki/
Ｎクイーン問題（４９）第七章マルチスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-03-n-queens-suzuki/
Ｎクイーン問題（４８）第七章シングルスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-02-n-queens-suzuki/
Ｎクイーン問題（４７）第七章クラス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-01-n-queens-suzuki/
Ｎクイーン問題（４６）第七章ステップＮの実装 Python編
https://suzukiiichiro.github.io/posts/2023-06-16-02-n-queens-suzuki/
Ｎクイーン問題（４５）第七章キャリーチェーン Python編
https://suzukiiichiro.github.io/posts/2023-06-16-01-n-queens-suzuki/
Ｎクイーン問題（４４）第七章　対象解除法 Python編
https://suzukiiichiro.github.io/posts/2023-06-14-02-n-queens-suzuki/
Ｎクイーン問題（４３）第七章　ミラー Python編
https://suzukiiichiro.github.io/posts/2023-06-14-01-n-queens-suzuki/
Ｎクイーン問題（４２）第七章　ビットマップ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-05-n-queens-suzuki/
Ｎクイーン問題（４１）第七章　配置フラグ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-04-n-queens-suzuki/
Ｎクイーン問題（４０）第七章　バックトラック Python編
https://suzukiiichiro.github.io/posts/2023-06-13-03-n-queens-suzuki/
Ｎクイーン問題（３９）第七章　バックトラック準備編 Python編
https://suzukiiichiro.github.io/posts/2023-06-13-02-n-queens-suzuki/
Ｎクイーン問題（３８）第七章　ブルートフォース Python編
https://suzukiiichiro.github.io/posts/2023-06-13-01-n-queens-suzuki/
Ｎクイーン問題（３７）第六章 C言語移植その１７ pthread並列処理完成
https://suzukiiichiro.github.io/posts/2023-05-30-17-n-queens-suzuki/
Ｎクイーン問題（３６）第六章 C言語移植その１６ pthreadの実装
https://suzukiiichiro.github.io/posts/2023-05-30-16-n-queens-suzuki/
Ｎクイーン問題（３５）第六章 C言語移植その１５ pthread実装直前版完成
https://suzukiiichiro.github.io/posts/2023-05-30-15-n-queens-suzuki/
Ｎクイーン問題（３４）第六章 C言語移植その１４
https://suzukiiichiro.github.io/posts/2023-05-30-14-n-queens-suzuki/
Ｎクイーン問題（３３）第六章 C言語移植その１３
https://suzukiiichiro.github.io/posts/2023-05-30-13-n-queens-suzuki/
Ｎクイーン問題（３２）第六章 C言語移植その１２
https://suzukiiichiro.github.io/posts/2023-05-30-12-n-queens-suzuki/
Ｎクイーン問題（３１）第六章 C言語移植その１１
https://suzukiiichiro.github.io/posts/2023-05-30-11-n-queens-suzuki/
Ｎクイーン問題（３０）第六章 C言語移植その１０
https://suzukiiichiro.github.io/posts/2023-05-30-10-n-queens-suzuki/
Ｎクイーン問題（２９）第六章 C言語移植その９
https://suzukiiichiro.github.io/posts/2023-05-30-09-n-queens-suzuki/
Ｎクイーン問題（２８）第六章 C言語移植その８
https://suzukiiichiro.github.io/posts/2023-05-30-08-n-queens-suzuki/
Ｎクイーン問題（２７）第六章 C言語移植その７
https://suzukiiichiro.github.io/posts/2023-05-30-07-n-queens-suzuki/
Ｎクイーン問題（２６）第六章 C言語移植その６
https://suzukiiichiro.github.io/posts/2023-05-30-06-n-queens-suzuki/
Ｎクイーン問題（２５）第六章 C言語移植その５
https://suzukiiichiro.github.io/posts/2023-05-30-05-n-queens-suzuki/
Ｎクイーン問題（２４）第六章 C言語移植その４
https://suzukiiichiro.github.io/posts/2023-05-30-04-n-queens-suzuki/
Ｎクイーン問題（２３）第六章 C言語移植その３
https://suzukiiichiro.github.io/posts/2023-05-30-03-n-queens-suzuki/
Ｎクイーン問題（２２）第六章 C言語移植その２
https://suzukiiichiro.github.io/posts/2023-05-30-02-n-queens-suzuki/
Ｎクイーン問題（２１）第六章 C言語移植その１
N-Queens問://suzukiiichiro.github.io/posts/2023-05-30-01-n-queens-suzuki/
Ｎクイーン問題（２０）第五章並列処理
https://suzukiiichiro.github.io/posts/2023-05-23-02-n-queens-suzuki/
Ｎクイーン問題（１９）第五章キャリーチェーン
https://suzukiiichiro.github.io/posts/2023-05-23-01-n-queens-suzuki/
Ｎクイーン問題（１８）第四章エイト・クイーンノスタルジー
https://suzukiiichiro.github.io/posts/2023-04-25-01-n-queens-suzuki/
Ｎクイーン問題（１７）第四章　偉人のソースを読む「Ｎ２４を発見ＪｅｆｆＳｏｍｅｒｓ」
https://suzukiiichiro.github.io/posts/2023-04-21-01-n-queens-suzuki/
Ｎクイーン問題（１６）第三章　対象解除法ソース解説
https://suzukiiichiro.github.io/posts/2023-04-18-01-n-queens-suzuki/
Ｎクイーン問題（１５）第三章　対象解除法ロジック解説
https://suzukiiichiro.github.io/posts/2023-04-13-02-nqueens-suzuki/
Ｎクイーン問題（１４）第三章　ミラー
https://suzukiiichiro.github.io/posts/2023-04-13-01-nqueens-suzuki/
Ｎクイーン問題（１３）第三章　ビットマップ
https://suzukiiichiro.github.io/posts/2023-04-05-01-nqueens-suzuki/
Ｎクイーン問題（１２）第二章　まとめ
https://suzukiiichiro.github.io/posts/2023-03-17-02-n-queens-suzuki/
Ｎクイーン問題（１１）第二章　配置フラグの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-17-01-n-queens-suzuki/
Ｎクイーン問題（１０）第二章　バックトラックの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-16-01-n-queens-suzuki/
Ｎクイーン問題（９）第二章　ブルートフォースの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-14-01-n-queens-suzuki/
Ｎクイーン問題（８）第一章　まとめ
https://suzukiiichiro.github.io/posts/2023-03-09-01-n-queens-suzuki/
Ｎクイーン問題（７）第一章　ブルートフォース再び
https://suzukiiichiro.github.io/posts/2023-03-08-01-n-queens-suzuki/
Ｎクイーン問題（６）第一章　配置フラグ
https://suzukiiichiro.github.io/posts/2023-03-07-01-n-queens-suzuki/
Ｎクイーン問題（５）第一章　進捗表示テーブルの作成
https://suzukiiichiro.github.io/posts/2023-03-06-01-n-queens-suzuki/
Ｎクイーン問題（４）第一章　バックトラック
https://suzukiiichiro.github.io/posts/2023-02-21-01-n-queens-suzuki/
Ｎクイーン問題（３）第一章　バックトラック準備編
https://suzukiiichiro.github.io/posts/2023-02-14-03-n-queens-suzuki/
Ｎクイーン問題（２）第一章　ブルートフォース
https://suzukiiichiro.github.io/posts/2023-02-14-02-n-queens-suzuki/
Ｎクイーン問題（１）第一章　エイトクイーンについて
https://suzukiiichiro.github.io/posts/2023-02-14-01-n-queens-suzuki/

最新技術やプログラム、デザインなど様々な情報を提供するサイト

Ｎクイーン問題（１３）第三章　ビットマップ

ビットマップ

ビットマップの特徴

ビットマップを言葉で説明すると・・・

実践、ビットマップ！

効き筋

bit（ビット）

Qの位置を確認

row + 1 のleftの効き筋をチェック）してみます

row + 1 のdownの効き筋をチェック）してみます

row + 1 のrightの効き筋をチェック

マスクビット

mask（マスク）

ビットマップで肝となるところを重点的に

bitmap=$(( mask&~(left|down|right) ))

bit=$(( -bitmap & -bitmap ));

bitmap=$((bitmap&~bit)) ;

board[$row]="$bit"; # Qを配置

bitmap_R “$size” “$((row+1))” “$(( (left|bit)«1 ))” “$((down|bit))” “$(( (right|bit)»1 ))";

斜めの効き筋

ビットマップソースコード

まとめ版ソースコード

実行結果

参考リンク

書籍の紹介

suzukiiichiro

サイト内検索

Ｎクイーン問題（１３）第三章 ビットマップ

ビットマップ

ビットマップの特徴

ビットマップを言葉で説明すると・・・

実践、ビットマップ！

効き筋

bit（ビット）

Qの位置を確認

row + 1 のleftの効き筋をチェック）してみます

row + 1 のdownの効き筋をチェック）してみます

row + 1 のrightの効き筋をチェック

マスクビット

mask（マスク）

ビットマップで肝となるところを重点的に

bitmap=$(( mask&~(left|down|right) ))

bit=$(( -bitmap & -bitmap ));

bitmap=$((bitmap&~bit)) ;

board[$row]="$bit"; # Qを配置

bitmap_R “$size” “$((row+1))” “$(( (left|bit)«1 ))” “$((down|bit))” “$(( (right|bit)»1 ))";

斜めの効き筋

ビットマップソースコード

まとめ版ソースコード

実行結果

参考リンク

書籍の紹介

Ｎクイーン問題（１４）第三章 ミラー

Ｎクイーン問題（１２）第二章 まとめ

suzukiiichiro

サイト内検索

Ｎクイーン問題（１３）第三章　ビットマップ

Ｎクイーン問題（１４）第三章　ミラー

Ｎクイーン問題（１２）第二章　まとめ