問題タブ [knights-tour]

私は最近プロローグを手に入れ、有名なパズル Knight's Tour [ここにあります] の解決策を見つけるプログラムを作成しようとしています。

Warnsdorff アルゴリズムを使用して、チェス盤の特定の場所から行うことができるすべての可能な動きを見つけようとしています。上記の動きを見つけるのに苦労しました。

これまでの私のコードは次のとおりです

可能な移動の数は、それらをすべて見つけた後にのみカウントされるため、リストは必要な方法でソートされていません。

たとえば、この入力で

結果は

しかし、私は得る

誰かが私が得るNewXのを手伝ってくれるなら、NewYそれは素晴らしいことです

誰かが私の間違いを見つけることができますknight's tour codeか? 見つからないようで、スタック オーバーフローではなく、無限ループが発生しています。

そしてそれを呼び出す：

jmp複数の試行を実行していて、たどったパスも表示したいので、変数が必要です。ありがとう！

このコードは、バックトラッキングを使用して解決しているナイト ツアーの問題で無限ループに陥っています。配列を使用して、方向x[8] and y[8]の可能な動きにアクセスしました。また、すでに解決された回答と同じように、8これらxと配列を形成しました。yしかし、まだ何かが欠けていて、何がうまくいかないのか理解できません。

CodeReviewで提示されたソリューションは、CentOS 7.1 で正常に動作します。私はそれをWindows 7、Visual Studio 2012に移植しようとしました.VS 2012がコードコンパイルをサポートしていないC++ 11の部分を可能にするためにマイナーな編集を行い、ループの最初の実行が正しく機能します. テスト ケースの残りの実行は失敗し、実行のたびに不正確さが増していきます。

この問題のコードはgithubにあります。

0 で計算を終了 /* ここの問題は問題に含まれていません */
経過時間: 0.202012 秒

すべてのパス検索の起点は A3 でした すべてのパス検索
の終点は H4
でした ボードの各エッジの正方形の数は 8 です
検索をさらに制限するために使用されたスライス方法論は、行または列への繰り返しの訪問ではありませんでした。
結果のパスは 5 つです
試行されたパスは 323 ありました
パスの長さの平均は 4.8 です
パスの長さの中央値は 4 です
最長のパスは 6 回の移動
です 最短のパスは 4 回の移動です

問題は、以下にリストされているファイルのいずれかにあると思います。私はこれを 2 日間デバッグしてきました。

CRKnightMoves_Cpp2.cpp

KnightMovesImplementation.h

KnightsImplementation.cpp

KMMoveFilters.h

KMMoveFilters.cpp

Knights Tour の問題を C# で実装しようとしています。

このリンクの C++ コードを参照します。

http://www.geeksforgeeks.org/backtracking-set-1-the-knights-tour-problem/

私の C# コード (C++ コードとほぼ同じ) が同じ結果を生成しない理由を理解しようと、何時間も頭を悩ませてきました。なんらかの理由で、実際に無限ループに陥っていると思います。

C# コードは次のとおりです。

Main メソッドでの実行:

騎士は (a,b) の位置にあり、(c,d) にいる王を取る必要があります。どうやって：

A: ツアーを視覚化する

B: (a,b) から (c,d) に移動するために必要な最小ステップを計算します。

私が見つけた実装は、基本的にチェス盤上の騎士の一連の動きであり、騎士はすべての正方形を 1 回だけ訪れますが、より具体的に特定の場所に足を踏み入れたいと考えています。

どのようなアルゴリズムまたは戦略を探す必要がありますか?

私はpythonの使用を考えています

ナイトのツアーは前に頼まれたのですが、いまだに困っています。チェス盤のすべてのセルを訪問する再帰を試みていますが、52 回を超える訪問はできません。その後、バックトラックし、訪問したセルの数がカウントダウンします。これが私のコードです：

これは私のコードです:

終わらない理由を知っていますか (もっと待てるかも...)? 同じブルートフォースアルゴリズムを実装するための他のソリューションがありますが、より高速に動作しますか?