問題タブ [knights-tour]

バックトラックを使用してナイトツアーの問題を解決しようとしています。私が持っているアルゴリズムはうまくいくはずだと思います。試してみましたが、なぜ機能しないのかわかりません。その結果、無限ループが発生します。

ただし、バックトラックの行をコメントアウトするsolutionBoard[dst.x][dst.y]=-1;と機能します! 理由がわかりません！どんな助けでも大歓迎です。

これは、8x8 デッキの有名なナイツ ツアーのコードです。したがって、私のコードの主なアイデアは次のとおりです。ターンから目的地を選択し、isPossible で確認してから、再帰的に目的地に移動し、このセルを「1」にマークします。したがって、すべてのセルを確認し、64 のセルにいる場合は true を返します。しかし、私のコードは無限再帰になり、デバッグできません。推奨事項は大歓迎です。

私は、ナイトのツアーコードでナイトが取る移動をランダム化することに取り組んでいます。ただし、何らかの理由で、私の switch ステートメントは、可能な移動を実行する代わりに、常にデフォルトになります。私は自分で個別に実行firstMoveChoice()して機能したため、可能な移動方法が機能することを知っています。だから私は問題が私のランダムな動きのピッカーにあることを知っていますが、私はそれを理解できないようです.

ご協力ありがとうございます。この問題を調べても答えが見つからないので、本当に感謝しています。

上記のコードの結果は次のとおりです。

これが私の主な方法です：

これが私の ChessBoard クラスです。

ここはfirstMoveChoice()

これはthirdMoveChoice(): 異なる移動の数の変更を除いて、他のすべてのものと実質的に同じです。

私はこれを2日間続けて解決しようとしていますが、有効なアルゴリズムが見つかりません. チェス盤といくつかの駒が与えられた場合、各駒が正方形を 1 回しか訪問できないという条件で、その盤が駒で巡回できるかどうかを確認する必要があります。ある種の複数のバックトラックであることは知っていますが、機能させることができません。（個人の駒では一般騎士のツアーしか実装できていません）

tablero名前、ピースのリスト、禁止位置のリスト、自由位置のリスト、およびボードの寸法のタプルを保持するボードのクラスです。

fichaは駒のクラスで、名前 ( nombre)、位置を含むタプル ( posicion)、有効な動きを含むリスト( ) を保持しますmovimientos(たとえば、ポーンのリストは [ [0,1] ] になります。前に進むだけ 1)

どんな洞察も大歓迎です。

クラスは次のとおりです (任意のメソッドを自由に追加/削除してください)。

現在、再帰を理解しようとしています。factorial のようないくつかの簡単な再帰アルゴリズムを実装した後、もっと難しいことを試すことにしました。

ナイトツアーの問題を発見したので、有効なナイトツアーを見つけるプログラムを作ってみました。

もちろん動作せず、出力は無限ループです。

エラーが表示されません。独学で、相談できる人がいないのでこちらで質問させていただきます。

ここに私のC ++コードがあります:

DFS を使用してナイト ツアーの問題を解決しようとしています。グラフを生成しました (この例では 5x5 のマトリックスがあります):

次に、DFS を呼び出して、長さが 25 のパスを見つけようとしています (各正方形に到達しました)。これを行うには、現在のパスを追跡し、それを目的の長さと比較し、到達していない場合は、すべてのネイバーから再帰的に DFS にまたがります。チェックされていない隣接要素がない場合 (行き止まりに到達しましたが、まだ到達すべき四角があります)、パスから最後の要素を削除しています。

私の場合、完全なパスを見つけることができず、[0, 11, 2, 9, 12, 1, 8, 19, 22, 13, 4, 7, 10, 17, 6, 3, 14, 23, 16]. 私の間違いはどこですか？

ACCESS と board の 2 つの配列を持つ Knights Tour Algorithm を作成しようとしています。ACCESS は次の手が何であるかを把握するために使用する配列であり、board はユーザーが最終結果として見る配列です。私のアルゴリズムは、利用可能な動きの数が最も少ない正方形を見つけるためにチェックし、そこに行きます。利用可能な手数が同じである可能性のある手が 2 つある場合、どちらが中心から最も遠い (境界に最も近い) かを見つけて、その場所に移動します。このアルゴリズムは、常に完璧な 64 回の手のナイツ ツアー プログラムを提供する必要がありますが、私は通常、約 60 回の動きしか得られません。