問題タブ [n-queens]

私は Ivan Bratko の本で Prolog を勉強しています: 人工知能のプログラミング と本で、空間状態の「グラフ」を使用して問題を解決するこのバージョンの 8 クイーン問題を見つけました。

これは、順列に基づく 8 クイーン問題の解決策 (そのnoattack/3関係を使用) と、可能性のある後継状態の状態 (グラフのノード) を構築すると思われるs/2述語を組み合わせたものです。だから私は次のようなものを持っています:

s(ActualState、SuccessorState)

goal/1述語は、正確に 8 個のクイーンを配置する必要があることを指定しているだけだと思います。

この本では、次のクエリを実行すると言います: solve([],Solution)は、クイーンの数が増加するボード ポジションのリストを生成し、このリストは 8 つのクイーンの安全な構成で終了します。

しかし、このクエリを実行しようとすると機能せず、次の出力が得られます。

当然のことながら、行 2 で呼び出されるnoattack述語は 2 つのパラメーターしか取りませんが、noattack述語には 3 つのパラメーターが必要です。

なんで？私は何が欠けていますか？

SICP contains an partially complete example of the n-queens solutions, by walking a tree of every possible queen placement in the last row, generating more possible positions in the next row to combine the results so far, filtering the possibilities to keep only ones where the newest queen is safe, and repeating recursively.

This strategy blows up after about n=11 with a maximum recursion error.

I've implemented an alternate strategy that does a smarter tree-walk from the first column, generating possible positions from a list of unused rows, consing each position-list onto an updated list of yet-unused rows. Filtering those pairs considered safe, and recursively mapping over these pairs for the next column. This doesn't blow up (so far) but n=12 takes a minute and n=13 takes about 10 minutes to solve.

Not really looking for code, but a simple explanation of a strategy or two that's less naive and that clicks well with a functional approach.

簡単な演習 (例: フィボナッチ) を行ったにもかかわらず、再帰とバックトラックを理解するのに苦労しています。ここで私の「脳の流れ」を紹介させてください。

1. 私は教科書を読み、現在の位置が次の列に次のクイーンを配置する可能性を排除する場合、バックトラックを使用して前のクイーンを削除できることを知っています. したがって、これは簡単に思えます。私がする必要があるのは、それを削除して、プログラムに次の可能な場所を決定させることだけです。

2. しばらくすると、プログラムが 6 番目のクィーンで止まっていることがわかったので、単に 5 番目のクィーンを削除すると、プログラムは単純に現在の位置に戻すことがわかりました (つまり、最初の 4 つのクィーンが与えられた場合、5 番目のクィーンは常に同じクィーンに分類されます)。驚くべきことではありません）。そこで、最後の女王の位置を追跡する必要があると考えました。

3. これは私が困惑したときです。最後のクイーンの位置を追跡する場合 (バックトラックしたときにプログラムがクイーンを同じ場所に配置できないようにするため)、2 つの潜在的な問題があります。

a) 5 番目のクイーンを削除し、次の可能な位置を決定するコードを作成する必要があるとします。これは、現在の位置 (削除される前) を無視することで解決でき、次の行で可能な場所を探し続けます。

b) 以前のすべてのクイーンを追跡する必要がありますか? そうらしい。実際には、1 つのクイーンではなく 2 つのクイーン (またはそれ以上) を削除する必要があるとしましょう。それらの現在の位置をすべて追跡する必要があります。しかし、これは見た目よりもはるかに複雑です。

1. それで、教科書で答えを探し始めました。残念ながら、バックトラッキング コードはなく、再帰コードしかありません。次に、ここにコードを見つけました：

http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/

これはとてもシンプルでありながら機能するので、私は非常に驚きました! 唯一のバックトラック部分は、最後のクイーンを削除することです! 問題は、次のコードは、4 つのクイーンの位置が与えられたときに、5 番目のクイーンが常に同じ場所に何度も落ちるとは限らないことをどのように確認するのでしょうか? 私が理解していないのは、再帰的にバックトラックする方法だと思います（より多くのクイーンを削除する必要があるとしましょう）。再帰的に進むときは問題ありませんが、再帰的に戻るにはどうすればよいですか?

わかった。現在、動作するコードがいくつかありますが、上記のコードに従って自分のコードをほとんど変更したため、非常に不安定です。

numQueen が 5 であるとすると、for ループで 6 番目のクイーンを配置できるかどうかを確認します。すべての行でこれが不可能であることはわかっているため、関数は false を返します。その後、それが呼び出された場所、つまり numQueen が 4 のときに "縮小" すると仮定します。そのため、ClearQueen(4) が呼び出され、最後のクイーン (5 番目) が削除されます。どうやら for ループが終了していないため、次の行を試してさらに開発できるかどうかを確認します。つまり、5 番目のクイーンを次の行に配置できるかどうかを確認し、配置できる場合は、6 番目のクイーンを配置できるかどうかをさらに確認します。

ええ、うまくいくようです。

クイーンドミネーション n×n ボードを考えると、ドミネーション数は、すべての正方形を攻撃または占有するために必要なクイーン (またはその他のピース) の最小数です。n=8 の場合、クイーンの支配数は 5 です。述語 slution(N) を書き、すべての正方形をカバーするために必要なクイーンの最小数を取得します。

基本的な関数のみを使用して Haskell の 8-queens 問題を解決して
います。これはコードです。

クイーンが同じ行にないことを関数がチェックすることを明確にするために、SafeHH は Horizantly を表し、SafeDは斜めの競合をチェックすることになっています。関数は問題なく問題ないと
確信しており 、コードをコンパイルすると問題は発生しませんが、呼び出し時に このエラーが表示される関数：SafeHSafeD
queens

誰でも私を助けてもらえますか?? すべてのことを前もって感謝します:)

検索しましたが、答えが見つかりませんでした。

Java で実装されたシミュレーテッド アニーリング (SA) アルゴリズムを使用して 8 クイーン パズル (具体的には N クイーン パズル) を解こうとしていますが、目的関数に関してはちょっと行き詰まっています。目標 (最適解) に近づいているかどうかはどうすればわかりますか?

試行に「ポイント」を与える方法を 2 つ思いつきました (より多くのポイントが試行をより良いものにします)。

1. 合法的にボードにいるクイーンの数

2. 合法的にボード上にあるクイーンの数 + 次のクイーンを合法的に配置するための利用可能なスポットの量

しかし、これらが良いかどうかは判断できません。ヒントやその他の情報を提供していただけますか? :)