チェスナイトの動きだけを使って1つのタイルから別のタイルに移動する単純なアルゴリズム

Question

チェスのナイトの動きだけを使って、どの2つのポイント間をすばやく見つける方法を探している問題があります。私の最初の考えは、A*アルゴリズムまたはDijkstra'sアルゴリズムでしたが、私は騎士の動きだけが使用されていることを確認する方法がわかりません。より良いアルゴリズムを提案できれば助けてくれるでしょう。ありがとうございました。あなたが始めるどのソース広場、そしてあなたは、パズルを解決するために上陸する必要がある場所である先の広場、：

は、2つのパラメータを取り込み答え（SRC、DEST）と呼ばれる関数を記述します。この関数は、チェスナイトの動き（つまり、任意の方向の2つの正方形の直後にその方向に垂直な1つの正方形が続いている）を使用して、ソーススクエアからデスティネーションスクエアに移動するために必要な最小の移動数を表す整数を返します、またはその逆、「L」字形）。送信元と宛先の両方の正方形は0と63までの整数となり、以下の例のチェス盤のように番号が付けられている：あなたが与えられたノードのためのすべてのネイバーを見つける必要があるアルゴリズムについては

 
------------------------- 
| 0| 1| 2| 3| 4| 5| 6| 7| 
------------------------- 
| 8| 9|10|11|12|13|14|15| 
------------------------- 
|16|17|18|19|20|21|22|23| 
------------------------- 
|24|25|26|27|28|29|30|31| 
------------------------- 
|32|33|34|35|36|37|38|39| 
------------------------- 
|40|41|42|43|44|45|46|47| 
------------------------- 
|48|49|50|51|52|53|54|55| 
------------------------- 
|56|57|58|59|60|61|62|63| 
------------------------- 

Answer 1

は次のように問題にアプローチ：

ステップ1：チェスボードの各正方形が頂点であるグラフを構築します。

ステップ2：1つの正方形から別の正方形へのナイト移動が1つの場合、正確に頂点間にエッジを配置します。

ステップ3：ダイクストラのアルゴリズムを適用します。 Dijkstraのアルゴリズムは、2つの頂点（四角形）の間のパスの長さを求めるアルゴリズムです。

Answer 2

。 https://docs.python.org/3/library/functions.html#divmodを使用すると、0〜63の表記を行と列に簡単に変換できるため、騎士の計算が簡単になります

Answer 3

この問題では、幅優先検索だけで十分です（DijkstraとBFSは重み付けされていないグラフの場合と同じ方法）。チェスナイトの移動だけが使用されるようにするには、移動を適切な方法で定義する必要があります。

チェスナイトは、2つの正方形を任意の方向に移動し、次に1つの正方形をそれに垂直に移動することに注意してください。これは、2つの正方形を右から左に1つ、正方形を上下に2つ、または2つの正方形を上下に動かし、次に1つの正方形を左右に動かすことができることを意味します。

0〜63の代わりに行（0〜7）と列（0〜7）でセルを識別すると、計算がはるかに簡単になります。これは、セルインデックスを8で割って商と剰余を行と列のインデックスとして使用します。したがって、騎士の位置が(x, y)の場合、次の可能な位置は(x - 2, y - 1), (x - 2, y + 1), (x + 2, y - 1), (x + 2, y + 1), (x - 1, y - 2), (x - 1, y + 2), (x + 1, y - 2), (x + 1, y + 2)のいずれかになります。これらの8つのセルがすべてグリッドの内側にない可能性があるので、ボードから落ちた場所を破棄してください。

Answer 4

User_Targaryenの答えはあなたの質問に直接答えるので最高ですが、計算が最短時間での回答の配信であれば、代数的解決法をお勧めします。

アルゴリズムを短縮するには、x、y、およびxy軸に関する反射を使用して、x> = yの正の値（x、y）のみを考慮し、開始移動を座標、0）。これは可能な方向の1オクタント（1/8）です。

解決策を発見するヒントは、グラフ用紙またはダイクストラのアルゴリズムを使用して、最初のオクタントのすべての点に5回までの移動を制限し、これをグリッドとして表示することです。グリッドの各セルには、移動の最小回数を表す桁でラベルを付ける必要があります。

質問を拡大したい場合や、追加情報が必要な場合はお知らせください。