Nクイーン問題とは
Nクイーン問題とは、チェスの盤面にクイーンを１行に１個ずつ効き筋に当たらないように置いていこうという問題です。
NクイーンのNは盤面の行・列の数です８クイーンだと８x８です。
おける場所の数を算出する法則はないのでプログラムを組んでクイーンを配置していくしかないのですが、
Nの数が増えれば置ける場所の候補が爆発的に増えていきプログラムでも何年経っても終わらないようなものになります。
現在最大のNは２７クイーンです。
Nクイーンを早く解く方法はいくつかあって、
①アルゴリズムを使って探索を効率化する
②ビット計算で計算速度を上げる
③GPUなどを使って並列計算をする
などがあります。
Pythonで頑張る
Python は最近すっかりメジャーになり、プログラミング教育が小学校で必修化され最初に学ぶのがPythonだという話もあります。
ライブラリも非常に充実しています。
そこで勉強を兼ねてPythonを使ってNクイーン問題を解いていこうと思います。
アルゴリズムなしでNクイーン問題を解こうとすると。。。
Nクイーンはアルゴリズムを使うとどのくらい早くなるのでしょうか。
それを体感するために今回はまったくアルゴリズムを使わないでプログラムにNクイーン問題に取り組ませてみましょう。
まったくアルゴリズムを使わない方法は「ブルートフォース 力任せ探索」と呼ばれるものです。
N4だと4の4乗で256パターン
私のPCだと0m0.042sで終了しますが
N8だと8の8乗で16777216パターン
3m7.321sもかかってしまいます。
ちなみに今後やる検索効率化アルゴリズム「バックトラック」だと
N8でと0m0.03sで完了します（もっと早いアルゴリズムも出てきます。）。
ここでは触って動かしてみていただいて時間かかるなあと思っていただければ良いです。
プログラムについて
プログラムは以下のgitにあります。
https://github.com/suzukiiichiro/N-Queens/blob/master/03Python/py01_nqueen.py
このプログラムは鈴木維一郎先生が作成したものです。
私はこのプログラムを初めてみながらpythonだとこう書くんだと思いながら
pythonの勉強させてもらいながらコメントしていく感じになります。
プログラムのダウンロード方法は以下です。
git clone https://github.com/suzukiiichiro/N-Queens/
実行方法は
N-Queens/03Pythonに移動して
python py01_nqueen.py
です。
プログラム概要
このプログラムでやりたいことはエイトクイーン(N=8)の時に全ての可能性のある解の候補を体系的に数え上げます。
利き筋などは全く考えず1行に1個ずつクイーンを置いていきます。
パターン数はNxNになるのでエイトクイーン(N=8)だと8の8乗16777216パターンクイーンを配置します。
プログラムがやるのはここまでです。これが正解かどうかはプログラムではチェックしません。
プログラムが列挙したパターンから人力でどれが正解かをチェックしようと思ったらエイトクイーン(N=8)でも相当の年月がかかりますね。
出力はパターンのカウント数と各行にクイーンが置かれた場所になります。
1: 00000000
2: 00000001
3: 00000002
4: 00000003
.
.
.
163100: 00476433
163101: 00476434
163102: 00476435
163103: 00476436
.
.
.
16777213: 77777774
16777214: 77777775
16777215: 77777776
16777216: 77777777
例えば
163101: 00476434
だと
163101はカウント数です。163101番目のパターンという意味です。
00476434はクイーンが置かれた場所です
左端が1行目で左から右へ行数が増えていきます。
クイーンの位置が
0:1行目は0なので右から1番目
0:2行目は0なので右から1番目
4:3行目は4なので右から5番目
7:4行目は7なので右から8番目
6:5行目は6なので右から7番目
4:6行目は4なので右から5番目
3:7行目は3なので右から4番目
4:8行目は4なので右から5番目
に置かれたということを表現しています。
図にすると以下になります
この例だと2行目に1行目と同じ列にクイーンを配置しているので、2行目の段階で1行目の下の効き筋に引っかかっているので解にはなりません。
次回はプログラム詳細について説明していきたいと思います。
