問題タブ [knights-tour]

[0,0]から始めて、すべての広場に行き、[0,0]に戻って座る必要があります

私のボードからの画像

これは私が試したコードです：

私の問題はtruepath変数が常にnullであり、トリップされた正方形を与えることができないことです

Haskell を使用して Knight's tour の再帰的ソリューションを実装しました。私のアルゴリズムは基本的に Warnsdorff の規則に基づいています。

例：

• チェス盤のサイズ: 5x5
• 開始位置: (3,3)

この例に基づく基本的な考え方:

(1) 現在のポイント (3,3) から許可された移動を計算する
=> (1,2),(1,4),(2,1),(2,5),(4,1),(4,5 ),(5,2),(5,4)

(2) これらのポイントのそれぞれについて、そのポイントに到達するために実行できる移動の数を計算します (「入り口」の数)
=> ((1,2),2),((1,4),2) ,((2,1),2),((2,5),2),((4,1),2),((4,5),2),((5,2),2) ,((5,4),2)

(3) 入り口が最小のポイント、またはすべてのポイントの入り口が同じ場合は最初のポイントを見つける
=> (1,2)

(4) 決定したポイントで同じ関数を呼び出す (再帰の開始)

そうすれば、問題を解決する方法を決定することができます。しかし、ここで、開始位置の他のすべての可能なソリューションを決定する必要があります (例 (3,3))。残念ながら、それを達成する方法が本当にわかりません。

アイデアは大歓迎です。

これは私の現在のHaskellコードです（指定された開始位置に対して1つのソリューションを提供します）：

私は騎士のツアーアルゴリズムについて学んでいます。再帰的な罰金を使用して実装しましたが、時間がかかり、クローズドツアーではありません。

今、私は現在、閉じたツアーを見つけるための高速なアルゴリズムを見つけています。誰かが私にいくつかのアルゴリズムを勧めることができますか?

更新:次のようなクローズド ナイト ツアーを見つけるためのヒューリスティックをどこかで読みました:Min[F(x, y)]どこでF(x,y) is a set of f(x,y)=Min(x-1, n-x) + Min(y-1, n-y)と(x, y)は次のステップの位置、nはチェス盤のサイズです。しかし、そのヒューリスティックをどのように使用すればよいでしょうか?

このサイトに投稿するのはこれが初めてです。このサイトのガイドラインに完全に従わない場合はご容赦ください。

私の問題はおそらく単純ですが、理解できません。私の騎士のツアー アルゴリズムは、騎士のパスを再帰的に見つけます。インデックス [0,0] で動作し、配列のスペースを完全に反復処理します...ただし、インデックス [0,0] 以外では、プログラムは永遠のようにハングアップします。これが私のコードです：

私はプログラミングが初めてで、ナイツツアーの問題を練習として解決したいと考えていました。だから私はそれを試してみました。再帰の概念を学んだばかりで、それを使用して 4X4 ボードの問題を解決しようとしていました。私のコードは次のとおりです。

これを実行すると、次の出力が得られます。

これにより、ボード上のボックスの位置が、アクセスされた順序でわかります。私の質問は次のとおりです。

1. ポイント 0,0 は 3,1 になり、最後から 2 番目のポイントは 1,0 になり、そこから 0,3 になります。それを行うべきではありません。これを理解しようとしましたが、できませんでした。誰でもこれで私を助けて、これがどのように、そしてなぜ起こっているのか教えてください。

2. これもこのように解決できますか？つまり、 には複雑で複雑なアルゴリズムがたくさんあると確信していますが、再帰を練習する何かが欲しかっただけです。DFS アルゴリズムを学びましたが、これには同じことが必要だと感じました。誰でも私を正しい方向に向けてくれます(これを機能させるための簡単な方法です。速度などのために最適化する必要はありません)。

ありがとう。

私は C# でゲーム Knights Tour の単純な C# プログラムを実行していますが、C# のすべてを学ぶのは難しい方法です。ボードと騎士の駒があり、騎士は騎士の絵が描かれたカスタム パネルです。

私がやろうとしているのは、ユーザーが実行時に騎士の駒コントロールをクリックしてドラッグできるようにすることです (設計時にコントロールを移動して配置する方法とまったく同じです) が、何らかの理由で非常に望ましくない結果が得られます。

このコードが同じことをしない本当の理由はわかりませんが、明らかに何かが欠けています。騎士をクリックして動かすと、マウスと同じ速度ではなく、はるかに遅く動きます。また、見えない場所に移動するとフェードします。

フォーム デザイナーと同じように騎士の駒を動かし、チェスの駒をチェス盤上で動かすにはどうすればよいですか?

任意の支援をいただければ幸いです。

私はコードを少し更新しましたが、それは役に立ちますが、アニメーションの側面はまだかなり途切れ途切れで、パネルが移動して配置されると背景が少し拾われます.

フォーム デザイナーでどのようにスムーズに行うのですか?

Knight's Tour のコードを書こうとしています:

ナイト ツアーとは、チェス盤上のナイトの一連の動きであり、ナイトがすべてのマスを 1 回だけ訪れるようになっています。

他の人のコードを変更しようとしましたが、バックトラッキングが正しく機能していないようです - 解決策が見つかりません。騎士が 0, 0 から開始する場合は完全に正常に動作しますが、2D グリッドの他の場所から開始する場合、プログラムは永遠に続きます。

このコードのどこにバグがありますか?

最近、Just A Trim Pleaseという小さなフラッシュ ゲームをプレイしましたが、コンセプト全体がとても気に入りました。

ゲームの基本的な目的は、各マスを 1 回通過して芝生全体を刈ることです。芝刈り機はタイルの上からスタートし、そこからあらゆる方向に移動できます (壁に遮られている場合を除く)。草のタイルの上を複数回走ると劣化し、レベルが下がります。上下左右にしか移動できません。ただし、ゲームを終了すると、さらにタイルが追加されます。

• 一度しか刈れないタイル（草）。
• 劣化する前に2 回乗り越えることができるタイル(背の高い草)。
• 好きなだけ上がれるタイプ（コンクリート）。
• 越えられないタイル（壁）。

私の言いたいことが分からない場合は、ゲームをプレイすれば理解できます。

私は、最初の種類のタイル (基本的にはナイツ ツアー問題のバリエーション) だけでパズルを解くことができるブルート フォース アルゴリズムをコード化することができました。ただし、これは最適ではなく、一度しか実行できないタイルのパズルでのみ機能します。余分なタイルをどのように処理するかについて、私は完全に迷っています。

開始点とタイル マップが与えられた場合、レベルを解決するパスを見つける方法またはアルゴリズムはありますか (解決できる場合)? 私は効率を気にしません。これは私が念頭に置いていた質問です。それを解決するためにどのように行かなければならないのか、私は興味があります。

私はコードを探しているのではなく、単なるガイドライン、または可能であれば手順のプレーンテキストの説明を探しています。ただし、疑似コードがある場合は、共有してください。:)

(また、これが経路探索と関係があるかどうかは完全にはわかりませんが、それが私の最善の推測です。)

Backtrackingメソッドを使用して、C++ でKnight's tourアルゴリズムをコーディングします。しかし、n > 7 (7 x 7 のチェス盤よりも大きい) の場合、遅すぎるか無限ループに陥っているようです。

問題は次のとおりです: このアルゴリズムの時間計算量はどのくらいですか? また、どのように最適化すればよいでしょうか?!

Knight's Tour 問題は、次のように記述できます。

n × n マスのチェス盤が与えられたとき、騎士がすべてのマスを 1 回だけ訪れる道を見つけてください。

これが私のコードです：

上記の例 (n = 7) の出力は次のようになります。