バックトラック法Ｎクイーン問題 ８クイーン問題と呼ばれるパズルを例にとって，バックトラック法の考え方を説明する。 まず，チェスのクイーンの駒が動ける範囲を解説しよう。クイーンは，次の図のように自分の場所から縦横斜めの方向に何マスでも動くことができる。 ８クイーン問題を解く方法として，まず考えられるのは，８個のクイーンの置き方をすべて調べて，条件を満たすものを探す，というものがある。 しかし，８個のクイーンをチェス盤上に置く置き方が 64Ｃ8 = 4426165368 通りあることを考えると， この方法があまりにも非現実的であることが分かる。 しかし，１つの行には１個のクイーンしか置けないことを考えると，調べる場合の数を減らすことができる。 すなわち，８つの行それぞれに，１個のクイーンをどこに置くか，ということを考えればいいから， その場合の数は， 8の8乗 = 16777216 通りである。 この考え方で
