チェスの駒が盤面上のすべての位置に到達するための最小移動回数を求める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

上図は、5×5 のチェス盤上で駒が位置 (3, 3) にいるときに取り得る移動先を示したものです。

出力の1行目には、駒が (1,1) から (1,5) の各マスへ到達するために必要な最小移動回数が含まれています。続く行も同様に、対応する i と j の値ごとの最小移動回数を示しています。

解法のアプローチ

この問題は、キューを利用した幅優先探索（BFS）によって効率的に解くことができます。具体的な手順は以下の通りです。

• 関数 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 := 要素[0] + current_element[0]

      • y := 要素[1] + current_element[1]

      • -1 < x < n かつ -1 < y < n かつ temp_list[x, y] が (-1, -1) と等しい場合

        • temp_list[x, y] := current_element

        • (x, y) を queue_positional の末尾に追加する

        • 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]

          • return count_var

  • return -1

メイン関数では、以下の処理を行います。

• board := -1 で初期化された新しいマップ

• i を 1 から n の範囲で繰り返します。

  • j を 1 から i の範囲で繰り返します。

    • 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

• i を 1 から n の範囲で繰り返します。

  • j を 1 から n - 1 の範囲で繰り返し、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