力まかせ探索
力まかせ探索のアルゴリズムを高速化する方法として、その問題に特有のヒューリスティクスを使って探索空間(すなわち解候補集合)を狭める方法がある。
例えば、エイト・クイーンの場合を考えてみよう。2つ以上のクイーンを同じマスに置けないという事実を使えば、考慮すべき組合せは64個のマスから8個のマスを選ぶことに他ならず、解候補数は 64!/56!/8! = 4,426,165,368 となる。
さらにもっと考察すれば、2つのクイーンが同じ行や列に配置されていれば、解にはならないということも言える。従って、さらに解候補を制限することができ、クイーン1は行1に、クイーン2は行2に、というようにそれぞれが別の行になるよう配置すればよい。このような配置をするには、配置を8要素の配列(c[1] から c[8])で表し、それぞれの要素は 1 から 8 までの値をとるようにする。従って、c[1] にはクイーン1の列番号、c[2] にはクイーン2の列番号というふうに格納する。