Pythonで隣接する桁の差が一定となるN桁の数を見つけるプログラム

問題の概要

「N桁の整数のうち、隣り合うどの2つの桁の絶対差もKと等しくなるものをすべて求める」という問題を考えます。ただし、答えとなる数には先頭のゼロを含めてはいけません（数値0自体は例外です）。

例えば、入力が N = 4、K = 7 の場合、出力は [1818, 2929, 7070, 8181, 9292] となります。1818 を確認してみると、隣接する桁同士の差は |1−8| = 7、|8−1| = 7、|1−8| = 7 となっており、条件を満たしています。一方、0707 は先頭に0が付いているため、有効な数として扱われません。

解き方のアプローチ

この問題は、幅優先探索（BFS）の考え方を使うと効率的に解けます。キューに初期値として1桁の数（1〜9）を入れ、そこから1桁ずつ数字を伸ばしながら、条件を満たす候補だけを残していくイメージです。具体的な手順は以下の通りです。

• Nが1の場合： 0〜9までのリストをそのまま返します。1桁の数には隣接する桁が存在しないため、すべてが条件を満たします。
• キューの初期化： キューに1〜9のすべての数を入れます。先頭ゼロを避けるため、0は含めません。
• 桁を伸ばす処理： N−1回のループを実行します。各ループでは、現在のキューの長さ分だけ以下を繰り返します。
  • キューの左端から数を取り出します。
  • その数の最下位桁 lsd を num mod 10 で求めます。
  • lsd − K ≥ 0 であれば、新しい数 num × 10 + (lsd − K) をキューの末尾に追加します。
  • K ≠ 0 かつ lsd + K ≤ 9 であれば、新しい数 num × 10 + (lsd + K) をキューの末尾に追加します。K = 0 の場合に同じ数が重複して追加されるのを防ぐためのチェックです。
• 結果の取得： 必要な桁数に達した時点で、キューに残っている要素がそのまま答えとなります。

実装例

それでは、Pythonでの実装例を見てみましょう。

from collections import deque
def solve(N, K):
   if N == 1:
      return list(range(10))
   queue = deque(list(range(1, 10)))
   for n in range(N - 1):
      len_queue = len(queue)
      for j in range(len_queue):
         num = queue.popleft()
         lsd = num % 10
         if lsd - K >= 0:
            queue.append( num * 10 + lsd - K )
         if K and lsd + K <= 9:
            queue.append( num * 10 + lsd + K )
   return list(queue)

N = 4
K = 7
print(solve(N, K))

入力

4, 7

出力

[1818, 2929, 7070, 8181, 9292]

計算量の目安

各ステップで1つの数から最大2つの候補が生成されるため、理論上の上限は 9 × 2^(N−1) 個です。実際には桁の範囲（0〜9）の制約により、これより大幅に少なくなります。Nが大きくなると候補数は指数的に増えますが、N ≤ 9 程度の典型的な制約下では十分高速に動作します。