mainメソッド概要
今回は前回から引き続きバックトラックを説明していきたいと思います。
プログラムソースは以下のURLにあります。
https://github.com/suzukiiichiro/N-Queens/blob/master/03Python/py03_nqueen.py
429-437行目でグローバル変数を宣言した後に呼び出されるのは486行目のmainメソッドです。
467-484行目のmainメソッドの内容を見てみましょう。
nmin=4からMAX=15まで複数のNについて探索し、解の数と実行時間を出力します。
以下が出力結果です。
N: Total Unique hh:mm:ss.ms
4: 2 0 0:00:00.000
5: 10 0 0:00:00.000
6: 4 0 0:00:00.000
7: 40 0 0:00:00.001
8: 92 0 0:00:00.004
9: 352 0 0:00:00.019
10: 724 0 0:00:00.088
11: 2680 0 0:00:00.439
12: 14200 0 0:00:02.345
13: 73712 0 0:00:13.412
14: 365596 0 0:01:21.331
NがNQueenのN数、Totalが解の総数、Uniqueは左右反転ミラー、回転で同じ形のものを同一解として計算した場合の数、
hh:mm:ss.msは各Nごとに処理にかかった時間です。
Uniqueは今回は全て0ですがロジックが進んでいくとまずUnique数を算出してそこからTotalを求めるようになりますので今の所は流しておいてください。
エイトクイーン(N=8)の解の数は8: の92、実行時間は4msとなります。
ブルートフォースが3m7.321s、配置フラグが0m0.554sでしたから格段に高速になったことがわかると思います。
mainメソッド詳細
メソッドの中身を見ていきましょう。
459行目 nmin=4 でスタートするNの数を指定しています。
461行目 for i in range(nmin,MAX): でnmin=4からMAX=15まで1ずつインクリメントしてnqueenを実行していきます。
462,463行目でfor文の冒頭でTOTAL,UNIQUEを0で初期化しています。
これをしとかないと出力されるTotal,Uniqueの数が累計数になってしまいますので注意しましょう。
464,465行目でABOARD配列を初期化しています。ABOARD配列は各行のどこにクイーンを置いたかを記憶するための配列です。ロジックが進んでいくと必須の配列になるのですが、今回のロジックでは使用しませんので読み飛ばしてください。
467行目でnqueenメソッドを呼び出しています。
今までは引数はrow=0の行情報1つだけでしたが、今回から複数のNについてNqueenを実行するようになるので第2引数にsizeが追加されています。
sizeは461行目のfor i in range(nmin,MAX)のiで渡します。
466行目,468-470行目でnqueenメソッドの前後時間を計測してメソッドの実行にかかった時間を算出しています。
datetime.now()で現在時刻が取得できます。
466行目でstart_timeにnqueenメソッド呼び出し直前の時間を取得しておき、
468行目でメソッド終了直後の現在時刻とstart_timeを引くことによってメソッドの実行にかかった時間をtime_elapsedとして算出しています。
469行目で'{}'.format としていますがこれはtime_elapsedがdatetimeオブジェクトなのでstringにキャストしています。
format関数は、文字列中の{ }の場所に、引数をにstringキャストして埋め込むことができるみたいです。
470行目で下３桁を切り捨てています。
stringは配列の扱いなのでスライスできるみたいです
[:-3]
ですと、0文字目から後ろから3文字除いた範囲を取り出しています。
例えば以下のようになります。
0:00:00.005309
0:00:00.005
基本的にformat関数は、文字列中の「{ }」の場所に、引数をstringにキャストして埋め込む
text = _text[:-3] スライス機能 先頭から末尾3文字を除いた文字列を切り取る
nqueenメソッドについて
プログラムの内容は基本的に前回の配置フラグと同じです。
違うのは以下の2点です。
1つ目は450,451,453行目です。
前回は配置フラグとして上下の利き筋だけチェックするFAだけ使っていました。
今回は、FAの他に左対角線の利き筋をチェックするFB、右対角線の利き筋をチェックするFCも使用しています。
2つ目445行目です。
前回までは最終行まで行ったらprintOutメソッドでCOUNT数と各行のクイーンの配置場所を出力していました。
今回はTOTAL +=1 として正解数に1加算しています。
FA,FB,FCの配置フラグのチェックを通過して最終行まで辿り着ければ正解としてカウントして良いと言えるからです。
次回は図で説明しながら実際の動きを追ってみましょう。
