問題タブ [knights-tour]

ここ数日、私は修士課程の勉強を控えて、この (一見単純な) パズルに集中してきました。

この 10*10 のグリッドは、100 の利用可能な場所の正方形を構成します。目的は、コーナーから開始し、いくつかの単純な「トラバース ルール」に従ってすべての場所をトラバースし、100 番に到達することです (または、プログラマーの場合は 99 番で、代わりに 0 から始めます :)

トラバースのルールは次のとおり
です。 1. 縦軸と横軸に沿って
2 つのスペースをホップします。 2. 対角線に沿って 1 つのスペースをホップし
ます。 3. 各マスは 1 回だけ訪れることができます。

よりよく視覚化するために、有効なトラバースの例 (8 番目のステップまで) を次に示し
ます。

手動で、私は退屈からこのパズルに取り組んできました。何年もの間、私は時々手で解こうと試みてきましたが、96 を超えることはありませんでした。簡単に聞こえますか? 自分で試してみてください:)

したがって、この問題を解決するために、Python で短い (約 100 行のコード) プログラムを開発しました。私はこの言語の初心者です。何ができるか見てみたいと思っていました。
プログラムは、徹底的な試行錯誤解決法を適用するだけです。言い換えれば、力ずくの深さ優先検索です。

ここから私の質問が発生します。残念ながら、プログラムは問題を解決できません。これは、状態空間が非常に大きいため、解決策が見つからない限り検索が終了しないためです。問題なく 98 まで (そしてそれを出力) することができますが、それでも完全な解決策ではありません。
プログラムは、これまでにカバーした検索ツリーの長さも出力します。数分で、たとえば 65 番目の要素からのトラバース リストが、1 つのパスについて最後までカバーされます。この数は、指数関数的に増加する期間で減少します。私はかなり長い間コードを実行してきましたが、50 バリアを超えることはできませんでしたが、今では確信しています。

この単純なアプローチは、私が永久に実行しない限り十分ではないようです。では、コードをより高速かつ効率的に改善して、解決策を導き出すにはどうすればよいでしょうか?

基本的に、次の方法に関するアイデアを楽しみにしています。

1. この問題に固有のドメイン知識を取得して活用する

2. 疲労を克服するためにプログラミングのテクニック/トリックを適用する

   ..そして、最終的に実質的な解決策を実現します。

前もって感謝します。

リビジョン
所属するドメインに問題を関連付けてくれた Dave Webb に感謝します。

これは、同じマスを再訪せずにチェス盤の周りでナイトを動かすことに関するナイツ ツアー問題に非常に似ています。基本的には同じ問題ですが、「トラバース ルール」が異なります。

私はナイトツアーの問題を調べていて、解決策を見つけるためにニューラルネットワークを使用してPythonでそれを実装することにしました。

メソッドの一般的な説明はウィキペディアで見つけることができます

私はそれを正しく実装したと思いますが（他に間違っているものは何も見えません）、機能しません。いくつかのリンクを更新し、接続する頂点の次数が2を超えるエッジを削除しますが、そうではありません。ソリューションに収束しません。

私が間違って実装したものについて誰かが何か考えを持っているかどうか疑問に思いました（恐ろしいコードについて申し訳ありません）。

編集
作業コードはGitHubhttps ://github.com/Yacoby/KnightsTourにあります

私はニューラル ネットワークの騎士のツアー ファインダーの単純な Java 実装を作成するために最善を尽くしましたが、なぜそれが機能しないのか完全に困惑しています..

6つのクラスがあり、3つはGUI用であり、実際のロジックなどを処理するためのものです.

ご参考までに、これはYacoby の python オファリングに触発されたものです 。彼は実装にも問題を抱えていましたが、私は同じ間違いを犯しているとは思いません..

スーパーコーディングではないことに感謝しますが、どんな提案でも感謝して受け取りました

ニューロン クラス:

スクエアクラス:

制御クラス:

GUI クラス: -

ボードクラス:

}

GuiSquare クラス:

回線クラス:

再帰についてもう少し学ぼうとしていますが、どういうわけかナイトツアーを解決できず、誰かが私の論理エラーを指摘してくれることを望んでいます。

編集：これが大丈夫だといいのですが。このプログラムを実行しようとしましたが、22を超える有効な移動を取得できませんでした。

ナイトツアー問題はすべての CS 学生に人気があることを知っていますが、私の問題を解決するのに苦労しています。この再帰アルゴリズムを使用して移動を進めますが、移動が 50 付近に到達すると、使用可能な移動がなく、ツアーを完了することができないため、バックトラックする必要があります。ChessNode (ノードが訪問されたかどうか、移動されたかどうかなどを保持します...)、次の行、次の列、および前のノードの移動カウントを渡します。

そのため、最初にコーナー ボードの位置に移動できるスポットを確認し、次に利用可能な移動に基づいて再帰呼び出しを行います。だから私の主な質問は、私が何か間違ったことをしているのでしょうか? または、ツアーをもう少し直感的にするために使用できる別の条件はありますか?

前もって感謝します！

「Knight's Tour」と呼ばれる、チェス盤のすべての正方形 (サイズは実際には問題ではありませんが、今のところ 6x6 です) を通過するプログラムを作成しようとしています。

ツアーは閉鎖されているはずです。つまり、最後に訪れた広場の騎士は、開始した広場を「攻撃」できます。コードはいくつかの正方形でうまく機能します。たとえば、main の入力 'traverse(1,1,1)' は、彼がトラバースしているだけでなく、バ​​ックトラックしてゴールに向かってトラバースに戻ることを示す出力を生成します。ただし、代わりに「traverse(1,0,0)」を入力すると、StackOverflowErrorが発生します。バックトラックとトラバースが成功することもあるので、コードが機能することはわかっていますが、エラーを取り除く方法がわかりません。私はあまりにも多くの電話をかけていると思いますが、それを回避する方法がわかりません.訪問する広場がたくさんあります:) コードを編集しました。

バックトラッキングでのナイトツアーの問題を解決するには、SML コードを作成する必要があります。チェス ナイトはチェス盤 (サイズ: ) のいたるところを走らなければNxNならず、各マスを 1 回だけ訪れなければなりません (最後に最初のマスに戻る必要はありません)。

空のボードを作成する関数、ボード内の正方形を設定または取得する関数、騎士の次の動きのリストを取得する関数はすべて既に作成しています。しかし、再帰関数を SML で記述する方法がわかりません (このアルゴリズムを C で記述する方法は知っていますが、SML では記述できません)。

8x8 チェス盤の C のアルゴリズム

バックトラッキングを使用してナイツ ツアーの問題を解決するアルゴリズムを JavaScript で記述しようとしていますが、うまくいきません。基本的に、この関数は、各移動の場所を含むVisitedという配列を出力することになっています。ただし、配列には位置が追加されず、[[0,0]] のままです。これが私のコードです。どんな手掛かり？

ありがとうございました。

これが私が書いたコードです。

少し説明。私はチェスのボードを表すために int [8][8] を使用しており、最初はボードのすべての正方形に数字 -1 を入れています。

ナイトが移動すると、カウンター (int カウンター) で訪問するマスをマークし、そこから (そしてナイトが実行できるすべての正当な動きに対して) パスを見つけるために再帰呼び出しを行います (目標は、各マスを 1 回だけ訪問することです)。 ）。

カウンターが 64 に達すると、関数bool knighttour(square start,int &counter,int cb[][8]) は true を返す必要があり、メイン プログラムは [8][8] チェス盤にマークされているように「騎士のツアー」を表示する必要があります。

私が提供した上記のコードは無限ループで実行されると思います。3分間走らせました。

再帰バックトラッキングを使用してナイト ツアー問題を解決しようとしています。誰かが私のコードを最適化するのを手伝ってくれますか? 私のコードは 6X6 ボードまで動作します。. N=7 を超えると、 を解くのにほぼ無限の時間がかかります。これが私のコードです:

私はスタンフォード 106B ライブラリを使用しています (グリッドは 2 次元ベクトルです) Visual Studio 2008 必要なライブラリ ファイルを含む空のプロジェクト