チェスの駒がPythonのすべての位置に到達するための最小移動数を見つけるためのプログラム

チェス盤と、ボード内でL字型に動く特別な騎士の駒Kがあるとします。ピースが（x1、y1）の位置にあり、（x2、y2）に移動する場合、その移動はx2=x1±a;として記述できます。 y2=y1±bまたはx2=x1±b; y2=y1±a;ここで、aとbは整数です。位置（0、0）からチェス盤の位置（n-1、n-1）に到達するために、そのチェスの駒が到達するための最小移動数を見つける必要があります。位置に到達できない場合は-1とマークされ、到達できない場合は移動数が返されます。 n – 1行の出力を出力します。ここで、各行iには、ピースが各jに対して実行する必要のある最小移動数を表すn −1個の整数が含まれます。

したがって、入力がn =6の場合、出力は

5  4  3  2  5
4 -1  2 -1 -1
3  2 -1 -1 -1
2 -1 -1 -1 -1
5 -1 -1 -1  1

騎士が5x5のチェス盤の位置（3、3）にある場合、騎士が移動する可能性があります。

出力の最初の行には、ピースが位置（1,1）から（1,5）に到達するために必要な最小移動数が含まれています。連続する線は、同様に、それぞれのI値とj値の最小移動数を示しています。

これを解決するには、次の手順に従います-

• 関数path_search（）を定義します。これにはi、j、nが必要です

  • temp_list：=ペア（-1、-1）で初期化された新しいマップ

  • queue_positional：=ペア（0、0）によって初期化された新しいリスト

  • ver：=[（i、j）、（-i、j）、（i、-j）、（-i、-j）、（j、i）、（j、-i）、（-j、i ）、（-j、-i）]

  • queue_positionalのサイズが0より大きい場合、実行します

    • current_element：=queue_positionalから最初の要素を削除します

    • verの各要素について、実行

      • x：=element [0] + current_element [0]

      • y：=element [1] + current_element [1]

      • -1

        • temp_list [x、y]：=current_element

        • queue_positional

          の最後にペア（x、y）を挿入します

        • xがn-1と同じで、yがn-1と同じである場合、

          • count_var：=1

          • temp_list [x、y]は（0、0）と同じではありませんが、実行

            • count_var：=count_var + 1

            • x、y：=temp_list [x、y]

          • count_varを返す

  • -1を返す

主な関数/メソッドから、次のようにします-

• ボード：=-1で初期化された新しいマップ

• 1からnの範囲のiの場合、実行します

  • 1からiの範囲のjについては、次のようにします

    • board [i、j]が-1と同じ場合、

      • board [i、j]：=path_search（i、j、n）

      • board [j、i]：=board [i、j]

    • （n-1）mod iが0と同じ場合、

      • board [i、i]：=（n-1）/ i

• 1からnの範囲のiの場合、実行します

  • 1からn-1の範囲のjの場合、実行

    • print（board [i、j]）

  • print（board [i、n-1]）

ソースコード（Python）

理解を深めるために、次の実装を見てみましょう-

from collections import defaultdict
def path_search(i, j, n):
   temp_list = defaultdict(lambda: (-1,-1))
   queue_positional = [(0, 0)]
   ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
   while len(queue_positional) > 0:
      current_element = queue_positional.pop(0)
      for element in ver:
         x = element[0] + current_element[0]
         y = element[1] + current_element[1]
         if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1):
            temp_list[x, y] = current_element
            queue_positional.append((x, y))
            if x == n - 1 and y == n - 1:
               count_var = 1
               while temp_list[x,y]!=(0,0):
                  count_var += 1
                  x, y = temp_list[x,y]
               return count_var
   return -1

def solve(n):
   board = defaultdict(lambda: -1)
   for i in range(1, n):
      for j in range(1, i):
         if board[i, j] == -1:
            board[i, j] = path_search(i, j, n)
            board[j, i] = board[i, j]
      if (n - 1) % i == 0:
         board[i, i] = (n - 1) / i

   for i in range(1, n):
      for j in range(1, n - 1):
         print(int(board[i, j]), end = ' ')
   print(int(board[i, n - 1]))

solve(6)

入力

6

出力

5  4  3  2  5
4 -1  2 -1 -1
3  2 -1 -1 -1
2 -1 -1 -1 -1
5 -1 -1 -1  1