対象解除法
今回から対象解除法を取り扱います。
解を見てみると左右反転だったり90度、180度回転すると同じものがあります。この性質を利用して探索回数を減らそうというアルゴリズムです。
プログラムソースは以下のURLにあります。
https://github.com/suzukiiichiro/N-Queens/blob/master/03Python/py04_nqueen.py
まずプログラムを実行してみましょう。
python py04_nqueen.py で実行できます。
n4からn15までnqueenを実行し解の数とかかった時間を出力します。
N: Total Unique hh:mm:ss.ms
4: 2 1 0:00:00.000
5: 10 2 0:00:00.000
6: 4 1 0:00:00.000
7: 40 6 0:00:00.001
8: 92 12 0:00:00.004
9: 352 46 0:00:00.018
10: 724 92 0:00:00.080
11: 2680 341 0:00:00.372
Total が解の総数になります。Uniqueが左右反転、90度、180度回転させて同じものを同一解として取り扱ったものです。
UniqueはTotalに比べるとかなり少なくN8ですとTotal 92に対してUnique が12です。
Unique解からTotalの数を一定の法則で計算が可能です。
まず全ての解は左右反転できます。
さらに90度回転して同じであればその4倍 180度回転で同じあればその2倍となります。
すなわち
90度回転して同じであれば 8倍
180度回転して同じであれば 4倍
それ以外は 2倍
となります。
もしこれが本当であれば、全てのTotalのルートを探索する必要はなく、全てのUniqueのルートを探索しさえすればあとは単純な掛け算で解の総数を出すことができます。大幅な探索コストの削減が期待できそうです。
本当にそうなのでしょうか？
py04_nqueen.pyは実行結果は正解数だけしか出力していません。
そこで、プログラムを改造してクイーンの位置も出力するようにして目で見て確かめてみましょう。
プログラムのどの部分を改造すれば良いでしょうか？
それでは、プログラムを眺めてみましょう。
グローバル変数
py03_nqueen.py と違う部分は
221,222行目のAT,AS配列です。
AT,ASは321行目のsymmetryopsメソッド内で左右反転、90度、180度回転して同じかチェックする箇所があるのですが。そこで使用します。
それ以外は同じです。
314行目のABOARD配列はpy03_nqueen.pyでは宣言するだけで使用していませんでしたが今回からは使用します。
ABOARD配列は各行のどこにクイーンを設置したかを記憶しておく配列です。
symmetryopsメソッドで反転回転チェックをする際に使用します。
各行のクイーンの場所を記憶しているのででプログラムを改造する時はこの配列を使ってクイーンの位置を出力すれば良さそうですね。
mainメソッド
py03_nquenn.pyと違う部分は337行目でABOARDをglobal宣言しているだけでそれ以外は同じです。
py03ではABOARDを宣言しただけでプログラムのなかで使用していなかったのですが今回からは本格的に使用するためちゃんとglobal宣言しています。
mainメソッドはn4からn15まで346行目でnqueenメソッドを呼び出して解を求め
nごとにTOTAL,UNIQUE,かかった時間を出力します
nqueen
py03_nqueen.pyとほとんど一緒です。
FA,FB,FCフラグで上下、左右対角線をチェックしながら再帰を利用しながら1行に1個ずつクイーンを置いていきます。
違う部分はどこでしょう。
まず、ABOARDを使うので314行目でABOARDをglobal宣言しています。
次に、if row == size :で全行クイーンを置き終わった時の処理が違います。
py03ではTOTALに1を加算していただけですが、py04はsymmetryopsメソッドを呼び出しています。
symmetryopsでは左右反転、90度、180度回転して同じものがあるかどうかチェックします。
symmetryopsの詳細な説明は後に譲りますが、同じものの中で優先順位の最も高いものだけが8(90度回転して同じ),4(180度回転して同じ),2(左右反転のみ)のスコアを返し、その他は0のスコアを返します。
322行目でstotalが0以外の時のみUNIQUEを1加算し、stotal 2,4,8いずれかのスコアをTOTALに加算します。
改造を加える部分は？
ざっとプログラムの概要を説明しましたが、それではどの部分に改造を加えてクイーンの設置場所を出力すると良いでしょうか？
全行クイーンを置き終わった時が良いですよね。
とすると 320行目の if row==size の後が良いでしょう。
ユニークなのか90,180度回転して同じものがあるのかも知りたいですから、
321行目のsymmetryopsを実行した後が良いですね。
そして、stotalが0の時優先順位で負けたもののクイーンの配置を出力したいですから322行目より前の方が良いですね。
ですので、321行目と322行目の間でクイーンの設置場所を出力するように改造しましょう。
長くなったので今回はここまでで次回プログラムを改造しましょう。
