問題タブ [knights-tour]

そこで、8*8 のチェス盤のナイツ ツアーを解決するために、この実装を思いつきました。しかし、実行に長い時間がかかっているようです (停止しなければならないほど長い)。しかし、dx、dy 配列をコメントに書かれているものに置き換えると、プログラムは魔法のように機能し、出力が得られます。ブルートフォースアルゴリズムが解決策を迅速に見つけることができるように、配列を巧みに選択していると彼らは言います。

しかし、そもそもこの配列 (dx,dy) は、他のコードから取得したものです。では、なぜこのコードがそれらの配列 (コメント内) で機能し、私のものではないのか、誰でも説明できます。

私は現在ナイツツアープロジェクトに取り組んでいます。私の最終的な目標は、バックトラッキング (スタックの実装による) と Warnsdorff のヒューリスティックを使用してこのプロジェクトを作成することです。push や pop など、スタック関数が作成済みのライブラリは使用できません。また、再帰を使用して問題を解決することもできません。そうは言っても、私は今かなり行き詰まっており、次の大きなマイルストーンは、後戻りするだけで問題を解決することです.

これをシュガー コーティングするつもりはまったくありませんが、今のところ私のコードは 1 つの大きな混乱です。プログラムを実行するために必要なツールはほぼすべて作成しましたが、あとはすべての部品を組み合わせるだけです。

以下は私のコードです：

}

したがって、この時点での私の考えは、次のことを行うことです。

水平方向と垂直方向の配列 (騎士の可能な動き) を使用して、騎士の現在の位置を変更するループを作成します。位置が変更されると、カウンターがインクリメントされ、-1 が現在のカウンター値に置き換えられます。騎士が移動したら、作成したプッシュ関数を使用して、新しい座標の情報をリンク リストに渡す必要があります。これを行うには、プッシュする配列 (x,y) または複数の値を渡す方法を見つける必要があります。また、現在取り組んでいるバウンド チェックを作成する必要もあります (ナイトが行ったことのある場所に移動せず、ボードから外れないようにします)。最後に、騎士が動けなくなった場合は、作成した pop 関数を使用してステップを戻し、別の動きを続ける必要があります。

ヘルプ、修正、開始場所、またはその他の提案があれば、本当に感謝しています。私はとても立ち往生しています..

プログラムを実行すると、Knights Tour が見つからず、StackOverflow エラーが発生します。これを引き起こしている原因と、実際に Knights Tour を見つけてこのエラーを取り除くためにコードを変更する方法を教えてください。プロジェクトは私の CS280 クラスのためのもので、金曜日に予定されています。助けてください。ありがとう！！

この目的のために、特に 2 次元ベクトルを扱うクラス Board を作成しました。ナイツツアーを解決しようとしています。出来上がったらプリントアウトしたい。再帰的な voyagingKnight() 関数を使用すると、何も実行されず、結果が出力されないことがわかりました。再帰呼び出しのステップ番号を増やしたいようですが、これは機能していません。

ベクトル引数 incs は、ナイトを移動するための増分の 2 次元ベクトルです。各行では、最初の列で行が移動し、2 番目の列で列が移動します。

ここでの私の推論の欠陥について何か提案はありますか? 関連するコード

8*8 のチェス盤で Knight の巡回問題を解こうとしています。しかし、私のバックトラックは無限ループに陥っています。私のロジック機能は次のとおりです。

N は 8 です。

sol [][] は、騎士が行った動きを格納します。

配列 move_x と move_y は、騎士の次の位置を取得するために x と y に追加される値を格納します。

まず、x を 0、y を 0、no_of_moves を 1 として渡し、sol[0][0] 以外の sol[][] のすべての値を 0 として渡しました。

とがチェス盤の内側にあり、まだアクセスされていないis_valid()かどうかをチェックします。nextxnexty