問題タブ [n-queens]

N-Queen の独自のソリューションを生成するコードを作成しようとしています。N = 4 と 6 の正しい解を生成することができ (ただし、N の他のケースではそうではありません)、180 度と 90 度の回転による不明確な解の生成のケースを排除しました。問題は、他の冗長なケースを排除する方法についての私の理解にあります。

たとえば、N = 5 の場合、2 つの一意のソリューションを取得する必要がありますが、3 つ生成しています。そのうちの 1 つを削除する 2 つの冗長なソリューションは次のとおりです (3 番目のソリューションは正しい):

Q---- Q----

--Q-- ---Q-

----Q -Q---

-Q--- ----Q

---Q- --Q--

課題として、Matlab と再帰を使用して NQueens アルゴリズムを考案する任務がありました。したがって、私が設定した方法は、有効な配置をテストする2つのヘルパー関数isValidと、0のMxMボードからクイーンを配置または削除し、クイーンの可能なすべての動きから1を追加または削除するrecursiveQueenを持っていることです作れます。スペースの都合上、recursiveQueen 関数から加算関数を削除しましたが、8 方向で 1 を加算または減算するだけです。

私が抱えている主な問題は、前の行に解決策が見つからない場合、solveNQ 関数が次の列に移動することです。ステップを 6 つに分けました。

1) 最初の列にクイーンを置く

2) クイーンを次の列の次の有効な位置に配置します

3) 行の有効な配置が見つからなくなるまで、手順 2 を繰り返します。

4) 最後の列から女王を取り除く

5) 列の次の有効な場所にクイーンを配置します。

6) すべての行にクイーンが含まれるまで、手順 1 ～ 5 を繰り返します (この手順はコーディングしていません)。

私は大学の試験のために Prolog を勉強していますが、次の演習で問題があります。

私は 8-Queens 問題の次の古典的な解決策を持っています (これは私にとっては問題ではありません)。

わかりました、このプログラムは非常に単純に見えます: 互いに攻撃してはならない女王のリストがあります。

クイーンのリストが空の場合、クイーンがリスト内の別のクイーンを攻撃する可能性はないため、空のリストは問題の解決策です (解決策の基本ケースです)。

*クイーンのリストが空でない場合、[X/Y|その他] に分割できます。ここで、X/Y は、リスト内の最初のクイーンのボード上のラッププレゼンス位置です * (位置はカップルによるラッププレゼンスエンドです (X,Y ) ここで、X は列、Y は行です)

したがって、次の関係が真である場合、リスト [X/Y|Others] が問題の解決策であることは TRUE です。

1. サブリスト Others はそれ自体が解決策です (Others には、リスト内の他の女王を攻撃する女王は含まれません)

2. Y は 1 から 8 までの整数値に属します(8 行あるため)

3. リストの最初のクィーンは、サブリストの他のクィーンを攻撃しません その他

次に、クイーンが別のクイーンを攻撃しないことが真であるといつ言えるかを指定するnoattack関係が定義されます (これは非常に単純です: それらは同じ行、同じ列、同じ場所にとどまることはできません)。対角線）

最後に、X 値を 1 から 8 の値で制限することで、私の生活を簡素化するソリューション テンプレートがあります (2 つのクイーンが同じ列にとどまることはできないことがわかっているため、ソリューション内のすべてのクイーンは別の列にとどまります)。他のすべての女王)

したがって、最大の問題は、列数を指定する行にあると思います。

そして、ソリューション テンプレートを定義する行で:

可変数のクイーンを処理するために以前のソリューションを拡張する方法についてはわかりません。

私は SWI Prolog の実装に関する大学の試験のために Prolog を勉強しています。

順列を使用して問題を解決するこのバージョンの 8 クイーン問題がどのように機能するかについて、私は疑問を持っています。

以前の解決策では、次のソリューション テンプレートを使用しました: [1\Y1、2\Y2、3\Y3、4\Y4、5\Y5、6\Y6、7\Y7、8\Y8] これは、すべての女王が異なる行にある場合、X 値が制限される可能性があります。

このバージョンのプログラムでは、垂直方向の攻撃を防ぐためにすべてのクイーンが異なる行にある必要があることがわかります。そのため、各行にクイーンがあります。

したがって、情報を失うことなく、解決策はリストの順列になると言えます: [1,2,3,4,5,6,7,8]で、すべての要素が女王の Y 座標を表します。

したがって、この場合、私はその Y 座標 (その行インデックス) だけでクイーンの位置を rappresenting しています。

したがって、Queensが元のリスト[1,2,3,4,5,6,7,8]の前置突然変異であり、この順列が安全な場合(すべてのQueensこの順列リストは、他のクイーンを攻撃しません)。

OK、これは明らかです...これで安全な関係が定義されました。

リストが空の場合、攻撃がないため安全であるという基本的なケースがあります。

また、リストが空でない一般的なケースがあります。リストが空でない場合は、 [Queen|Others]に分割できます。ここで、Queenはリストの最初のクイーンで、 Othersは残りのサブリストです...したがって、サブリスト Others の場合、元のリスト[Queen|Others]は安全です。それ自体が解決策であり (安全であれば、Others に攻撃がない場合)、最初のアイテムのQueenが Othersサブリストの他の Queen を攻撃しない場合...

わかりました...今までは、私には明らかだと思います...

今、noattack関係の定義に問題があります!!!

問題は、私がクイーンの位置を Y 座標と X 座標だけで明示的に表現していないことです。

私は、ラププレゼンテーションのこの制限を回避するために、次の一般化があることを理解しています (よく理解できていることを願っています...よくわかりません...): ** また、各列に女王がいなければならないことも知っていますしたがって、リストの最初のクイーン (Queen) とサブリスト Others からの X 距離は 1** でなければなりません

最初の項目 Queen とサブリスト Others からの距離は、最初の項目 Queen とそれに最も近い Queen からの X 距離です。

したがって、クイーンが異なる列にある場合、 noattack関係は TRUE であり (コンストラクションでは常に true)、クイーンと Others サブリストの最も近いクイーンからの X 距離が 1 であると言って、別の行にある必要があることを表現できます。

しかし、私の推論が真実であれば、コードのこの部分でこのことをどのように表現するかを理解しようとすると、多くの問題が発生します。

私はプロローグで確率的検索を実装しています。

コードは

しかし、それは false を返します。私はプロローグをよく理解できませんが、実装する必要があります。どこが間違っているのかわかりません。

pthreads を使用して n-queen パズルを計算するための次のコードがあります。しかし、そのコードをコンパイルしようとすると、次のエラー メッセージが表示されます。

wikithread.c:7:5: エラー: ファイル スコープで可変的に変更された 'hist'

上部を変更し、配列にメモリを動的に割り当てると、次のエラーが発生します。

次に、次のエラーが表示されます。

wikithread.c:8:1: 警告: データ定義にタイプまたはストレージ クラスがありません [デフォルトで有効] wikithread.c:8:1: エラー: 'hist' wikithread.c:7:6: ノート: 以前の「hist」の宣言はここにありましたvector wikithread.c:23:27: エラー: 添え字付きの値は配列でもポインターでもベクトルでもありません wikithread.c:26:7: エラー: 添え字付きの値は配列でもポインターでもベクトルでもありません

誰でも、問題を解決するのを手伝ってくれますか?

注意: NQueens の問題を好きなように変更するように依頼されました。私はこの方法を考え、それを実行したいと考えています。これは宿題の直接的な質問ではなく、自分の変更をどのように実装するかという問題です。

以下に、4 つのクイーンを解決するコードを書きました。したがって、このコードによれば、2 つのクイーンが同じ行、同じ列、同じ対角線にあることはできず、攻撃しないようになっています。クイーンを配置すると、同じ列に配置できますが2行をスキップし、同じ行に2列をスキップして配置でき、同様に2列をスキップして同じ対角線に配置できるように変更しようとしています行と 2 つの列。

つまり、簡単に言えば、クイーンは同じ行、同じ列、同じ対角線に 2 つのブロックをスキップして配置できます。

4 つのクィーンの場合、現在の出力は次のようになります。

と

ただし、次の出力も得られるはずです。

ここでは、水平、垂直、斜めに 2 ブロックごとにクイーンが配置されています。

コード：

私は何を間違っていますか？変更で動作するようにコードを変更するにはどうすればよいですか?