エイトクイーン問題
チェスの盤上(8×8マス)に、8個のクイーンを配置します。このとき、どの駒も他の駒に取られるような位置においてはいけません。 そのような置き方は何通りあるでしょうか。 ちなみにクイーンの動き方は次図のような感じです。縦横斜めにどれだけでも動くことができます。
Nクイーン問題
エイトクイーン問題の拡張で、「N×Nマスの盤上に、N個のクイーンを互いに取り合わないよう配置する方法は何通りあるか」というものです。 今回はNクイーン問題にも対応できるようなコードを書いていきたいと思います。考察
前置きが長くなりましたが早速エイトクイーン問題を考えてみましょう。 とにもかくにも、まずは素朴に考察してみます。8×8マスの盤上に一つずつクイーンを配置していって、各コマどうしが縦、横、斜めの効き筋にないかをチェックすれば良さそうです。
最初に置く駒の位置はどこでも良いので64通り、次に置く駒は最初の駒を置いた場所以外の63通り、...で合計64・63・・・57 = 178,462,987,637,760通りの置き方が考えられます。
これら全ての場合について、それぞれが縦、横、斜めの効き筋に被ることなく配置できているかをチェックして、配置できている場合だけを数えあげれば解けますね。
コンピュータは膨大な量の計算を高速にミスなく行えますから、この方法でもできなくはないかもしれません。
ただ、いくら計算が速いと言っても限界がありますから、可能な限り負担は減らしてあげたいですよね。
この方法では、8×8の盤ならまだしも、9×9, 10×10, ...
とNを増やしていった時に駒を置く場所の候補が爆発的に増加しますから、早々に限界が訪れるでしょう。
もう少し工夫が必要そうですね。
ベストな答えは出せませんでしたが、なるべく駒を置く場所の候補を少なくしたいという視点が得られました。
ではもう少し考察を続けます。
このような複雑な問題を考えるには、簡単な例(小さい数)で実験するという方法が有効です。
いきなり一般のNについて考えるのは不可能に近いですから、具体的に駒を2つ、3つと並べる方法を考えながら法則を探っていきます。
とりあえず適当に1個置くとして、1個目の駒の縦横斜めが効いている位置にわざわざ2個目の駒を置いたりしませんよね？
同様に、1個目と2個目の駒の縦横斜めが効いている位置に3個目の駒を置くこともありませんね。
最初は駒の置き方が64×63×・・・×57通りあると言いましたが、実際には駒を置く場所の候補はかなりザクザクと削れていきます。
「なるべく駒を置く場所の候補を少なくしたい」という課題は達成できそうです。
また、次々と駒を置いていって途中で駒を置く場所が無くなった時、最初から全てやり直しますか？
おそらく1個前に戻って考え直してみて、それでもダメならもう1個前に戻ってみて、というふうにやるのが自然かなと思います。
例を挙げると次のような感じです。
1行ずつ順にできるだけ左から置いていきます。
3行目に駒を置く場所が無くなってしまったので、2行目をもう1列右にズラして考え直します。
4行目にはもう置く場所がありません。1つ戻って3行目も今置いてある場所以外には動かせません。1つ戻って2行目もこれ以上動かせません。そこで、更に1つ戻って1行目の駒を1列右にズラします。
うまくいきましたね！
用語も簡単に補足。
解が見つからなかった時に1つ前の状態に戻ることをバックトラックと言います。
バックトラックするまで可能な限り探索を続けていく方法を深さ優先探索と言います。
と言うわけで、この辺りの話をコードに落とし込めれば良さそうです。
実装
さて、人の手でチェス盤と駒を書くのは簡単ですが、これをコードでどう表現しましょうか。 盤上に置かれた駒は「行」と「列」という2つの情報を持っています。つまり、行と列さえ決まれば盤上の駒の位置が特定できるということです。 これは、リストで表現すれば良いでしょう。 リストの要素は順序付けられているため、index(リストの何番目か)とvalue(値)の2つの情報を持っています。 indexをクイーンが置かれたマスの行、valueをクイーンが置かれたマスの列だと思えば、0〜7までのvalue(値)を持つ長さ8のリストで、盤面に置かれた8つのクイーンを表現できます。 indexは重複できませんが、今回は行が重複することはないので(同じ行に2つ以上クイーンを並べることはない)、むしろ好都合です。 さらにvalueを重複させないことで同じ列に複数のクイーンを並べるケースも除外しましょう。 例えば次の盤面は[3,6,2,7,1,4,0,5]と表現します。
斜めのチェックはどうしたら良いでしょう。
次に駒を置きたい場所の行をx,列をyとします。
既に配置済みの駒の行をx1,列をy1とします。
座標の格子点のようなイメージですね。
駒が互いに斜めの効き筋に配置されている時、x座標の差の絶対値とy座標の差の絶対値は等しくなります。
この性質を利用すれば、配置済みの全ての駒との斜めチェックを行うことができます。
def deplication(x, y):
"""斜めの重複チェック"""
for x1 in range(0, x):
y1 = board[x1]
if abs(x - x1) == abs(y - y1):
return True
return False
後はバックトラックを上手く書いてあげたいですね。
1行ずつ順に考えていき、縦のチェック(既に駒が置かれた列にはもう置けない)と斜めチェックに引っかからずに駒を置けるかどうか調べます。
置けた場合はn_queen(n, x + 1)を呼び出して次の行に駒が置けるかを考えます。
呼び出し先のfor文が回り切ったら(=次の行の駒を一番右まで進め、どの列にも駒を置けなくなったら)呼び出し元に処理が帰り、board.pop()でリストの端を削除した後for文を進めます(=最後に置いた駒を右にズラします)。
コード全体は次の通りです。
count = 0 # 駒の置き方が何通りか格納する変数
board = [] # 盤上に置かれた駒を表すリスト
def deplication(x, y):
"""斜めの重複チェック"""
for x1 in range(0, x):
y1 = board[x1]
if abs(x - x1) == abs(y - y1):
return True
return False
def n_queen(n, x):
"""
xはクイーンを配置する行
yはクイーンを配置する列
1行ずつ配置していき最後の行まで配置できたらcountを+1する
"""
global count
if n == x:
#print(board)
count += 1
else:
for y in range(0, n):
if y in board or deplication(x, y):
continue
board.append(y)
n_queen(n, x + 1)
board.pop()
n_queen(8, 0)
print(count)
実行すると「92」という答えが得られます。
n_queen()の第一引数に渡す値を変えてやればnが8以外の時の解も求められます。
print(board)のコメントを外してやれば、実際の駒の配置も見ることができます。