問題の説明
今回は騎士 (ナイト) を使ったパズル「騎士の巡歴 (Knight's Tour)」を取り上げます。ナイトはチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐
│ │●│ │●│ │
├─┼─┼─┼─┼─┤ ┌─┬─┬─┐
│●│ │ │ │●│ │Ｋ│ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│●│ │ │ │●│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│ │●│ │●│ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┘
●：ナイト (K) が動ける位置 問題
図 : ナイトの巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。大きな盤面を解くのは大変なので、3 行 4 列の盤面でナイトの移動経路を求めてください。プログラムを作る前に自分で考えてみるのも面白いでしょう。
●深さ優先探索
今回は Python3 (ver 3.8.10) でプログラムを作ります。次の図を見てください。
┌─┬─┬─┐
│０│１│２│ ０──７──２
├─┼─┼─┤ │ │
│３│４│５│ ５──10──３
├─┼─┼─┤ │ │
│６│７│８│ ６──１──８
├─┼─┼─┤ │ │
│９│10│11│ 11──４──９
└─┴─┴─┘
（Ａ）盤面 （Ｂ）騎士の移動
図 : 盤面と騎士の移動
図 (A) のように、3 行 4 列盤の各マスに番号をつけて表します。すると、ナイトの移動は (B) のようにグラフで表すことができます。これならばコンピュータを使わなくても解くことができますね。プログラムも隣接リストを定義すれば簡単です。次のリストを見てください。
リスト : 騎士の巡歴
# 隣接リスト
adjacent = [
[5, 7], # 0
[6, 8], # 1
[3, 7], # 2
[2, 8, 10], # 3
[9, 11], # 4
[0, 6, 10], # 5
[1, 5, 11], # 6
[0, 2], # 7
[1, 3, 9], # 8
[4, 8], # 9
[3, 5], # 10
[4, 6] # 11
]
# 深さ優先探索
def dfs(n = 1, path = [0]):
if n == 12:
print(path)
else:
for x in adjacent[path[-1]]:
if x in path: continue
path.append(x)
dfs(n + 1, path)
path.pop()
隣接リストはリスト adjacent に定義します。あとは単純な深さ優先探索で解を探します。関数 dfs() の引数 n が手数で、path が経路を表すリストです。末尾の要素が現在地点になります。n が 12 になったら、すべての地点を訪問したので print() で path を表示します。そうでなければ、隣接リストから次の訪問先を求めて変数 x にセットします。x が path に含まれていなければ、x を path に追加して dfs() を再帰呼び出しします。戻ってきたら、path から x を削除することをお忘れなく。
これでプログラムは完成です。さっそく実行してみましょう。
>>> dfs() [0, 7, 2, 3, 10, 5, 6, 1, 8, 9, 4, 11] [0, 7, 2, 3, 10, 5, 6, 11, 4, 9, 8, 1]
2 通りの経路を見つけることができました。このプログラムでは隣接リストを使いましたが、盤面を二次元配列で表しても簡単にプログラムすることができます。
●盤面を二次元配列で表す方法
それでは盤面を二次元配列で表してみましょう。この場合、騎士の移動手順は 3 行 4 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 3 行 4 列の二次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。下図を見てください。
┌─┬─┬─┬─┬─┬─┬─┐
│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│
├─┼─┼─┼─┼─┼─┼─┤
│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│
├─┼─┼─┼─┼─┼─┼─┤
│Ｗ│Ｗ│Ｋ│ │ │Ｗ│Ｗ│
├─┼─┼─┼─┼─┼─┼─┤
│Ｗ│Ｗ│ │ │ │Ｗ│Ｗ│
├─┼─┼─┼─┼─┼─┼─┤
│Ｗ│Ｗ│ │ │ │Ｗ│Ｗ│
├─┼─┼─┼─┼─┼─┼─┤
│Ｗ│Ｗ│ │ │ │Ｗ│Ｗ│
├─┼─┼─┼─┼─┼─┼─┤
│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│
├─┼─┼─┼─┼─┼─┼─┤
│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│Ｗ│
└─┴─┴─┴─┴─┴─┴─┘
Ｋ：ナイト, Ｗ：壁
図 : 盤面の構成
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 7 行 8 列の大きさになります。壁に 0 以外の値 (1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
それではプログラムを作りましょう。最初に大域変数を定義します。
リスト : 大域変数の定義
# 騎士の移動
dx = ( 1, 2, 2, 1, -1, -2, -2, -1)
dy = (-2, -1, 1, 2, 2, 1, -1, -2)
# 盤面
board = [
[1,1,1,1,1,1,1],
[1,1,1,1,1,1,1],
[1,1,0,0,0,1,1],
[1,1,0,0,0,1,1],
[1,1,0,0,0,1,1],
[1,1,0,0,0,1,1],
[1,1,1,1,1,1,1],
[1,1,1,1,1,1,1]
]
タプル dx は騎士の x 方向の変位、dy は y 方向の変位を表します。現在の座標にこの値を加えることで、次の座標を決定します。board は盤面を表します。盤面は二次元配列で表すので、board は Python のリストで、その要素もリストになります。壁の部分は 1 に、実際の盤面は 0 に初期化しておきます。
次は探索を行う関数 dfs1() を作ります。
リスト : 騎士の巡歴 (2)
def dfs1(n = 1, x = 2, y = 2):
if board[x][y]: return
board[x][y] = n
if n == 12:
print_board()
else:
for a, b in zip(dx, dy):
dfs1(n + 1, x + a, y + b)
board[x][y] = 0
関数 dfs1() は引数として手数 n と騎士の座標 x, y を受け取ります。まず最初に、与えられた座標に移動できるかチェックします。これは board[x][y] が 0 であることを確かめればいいですね。次に、その位置に手数 n を書き込みます。n が 12であれば騎士はすべてのマスを訪れたので、関数 print_board() で盤面を出力します。
そうでなければ、次に移動するマスを選びます。for ループで dx と dy の要素を取り出して、 x と y の値に加えて dfs1() を再帰呼び出しします。それから、board は大域変数なので、dfs1() を終了するときには board[x][y] の値を 0 に戻すことをお忘れなく。
あとのプログラムは簡単なので説明は不要でしょう。詳細はプログラムリスト１をお読みくださいませ。
●実行結果
これでプログラムは完成です。さっそく実行してみましょう。スタート位置は左上隅 (2, 2) です。
>>> dfs1() 1 12 3 4 9 6 7 2 11 10 5 8 1 8 3 4 11 6 7 2 9 10 5 12
3 行 4 列盤は 2 通りの解しかありませんが、5 行 5 列盤になると重複解を含めて全部で 304 通りあります。
●騎士の周遊
ところで、騎士の巡歴は「どのマスにもちょうど一回ずつ訪れたのち最初のマスに戻ってくること」を条件にする場合があります。これを「騎士の周遊」と呼びます。この場合、3 行 4 列盤や 5 行 5 列盤には解がありません。また、N 行 M 列の盤面でマスの個数が奇数の場合も、騎士は出発点に戻ることはできません。これは簡単に証明することができます。次の図を見てください。
図 : チェスの盤面
上図に示すように、チェスの盤面は白黒の市松模様に塗り分けられています。すると、騎士は白のマスにいるときは黒のマスに、黒のマスにいるときは白のマスにしか移動できません。このため、騎士は白と黒のマスを交互に移動することになります。
左図の 5 行 5 列盤の場合、黒マスが 13 個で白マスが 12 個あります。黒マスから出発した場合、騎士は黒白交互に移動していくので、最後に騎士が到達するマスは黒になります。次に騎士が移動できる場所は白マスですが、出発点は黒マスですよね。したがって、最後のマスから出発点に戻ることは不可能であることがわかります。
では、白マスから出発した場合はどうなるのでしょう。この場合、騎士は白黒交互に移動していくので、12 番目の白マスから 12 番目の黒マスへ移動したあと、13 番目の黒マスがひとつ余ることになります。つまり、白マスから出発すると「騎士の巡歴」は解けないのです。
以上のことから、騎士が出発点に戻るには、白と黒のマスが同数必要であることがわかります。マスの個数が奇数の場合、白と黒のマスは同数ではないので騎士が出発点に戻ることは不可能、というわけです。
それでは問題です。
┌─┬─┬─┬─┬─┐ ┌─┬─┐
│ │●│ │●│ │ │Ｋ│ │
├─┼─┼─┼─┼─┤ ┌─┼─┼─┼─┐
│●│ │ │ │●│ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │×│×│ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │
├─┼─┼─┼─┼─┤ └─┼─┼─┼─┘
│ │●│ │●│ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┘
●：ナイト (K) が動ける位置 問題Ａ
図 : 騎士の周遊
騎士 (ナイト) を動かして、どのマスにもちょうど一回ずつ訪れて出発点に戻る周遊経路を求めてください。なお、ナイトは×印のマスに移動することはできません。
ちなみに、4 行 4 列の盤面には解がありませんが、6 行 6 列、8 行 8 列の盤面には解が存在します。大きな盤面を解くのは大変なので、問題 A の盤面でナイトの周遊経路を求めてください。
●プログラムの作成
それではプログラムを作りましょう。この問題は盤面が小さいので、単純な深さ優先探索で簡単に解くことができます。下図に示すように、盤面のマスに番号をつけます。
┌─┬─┐ ┌─┬─┐
│Ｋ│ │ │０│１│
┌─┼─┼─┼─┐ ┌─┼─┼─┼─┐
│ │ │ │ │ │２│３│４│５│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│ │×│×│ │ │６│×│×│７│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│ │ │ │ │ │８│９│10│11│
└─┼─┼─┼─┘ └─┼─┼─┼─┘
│ │ │ │12│13│
└─┴─┘ └─┴─┘
盤面 番号
図 : 盤面と番号の関係
あとは隣接リストを定義して、深さ優先探索で周遊経路を探索するだけです。プログラムは次のようになります。
リスト : 騎士の周遊
# 隣接リスト
adjacent1 = [
[5, 6], # 0
[2, 7], # 1
[1, 9], # 2
[7, 8, 10], # 3
[6, 9, 11], # 4
[0, 10], # 5
[0, 4, 10, 12], # 6
[1, 3, 9, 13], # 7
[3, 13], # 8
[2, 4, 7], # 9
[3, 5, 6], # 10
[4, 12], # 11
[6, 11], # 12
[7, 8] # 13
]
# 深さ優先探索
def dfs2(n = 1, path = [0]):
if n == 14 and path[-1] in adjacent1[path[0]]:
print(path)
else:
for x in adjacent1[path[-1]]:
if x in path: continue
path.append(x)
dfs2(n + 1, path)
path.pop()
隣接リストはリスト adjacent1 に定義します。関数 dfs2() は深さ優先探索で騎士の周遊経路を求めます。引数 n は訪れたマスの個数、path は経路 (リスト) を表します。周遊経路を求めるので出発点はどこでもいいのですが、今回は 0 を出発点としてます。
全部のマスを 1 回ずつ訪れると n の値は 14 になります。最後のマスから出発点 (goal) に戻ることができれば周遊経路になります。これは先頭のマスの隣接リストに末尾のマスが含まれているかチェックすればいいですね。そうであれば、print() で path を表示します。n が 14 より小さい場合は、深さ優先で騎士を進めていきます。
それでは、実行してみましょう。
>>> dfs2() [0, 5, 10, 3, 8, 13, 7, 1, 2, 9, 4, 11, 12, 6] [0, 6, 12, 11, 4, 9, 2, 1, 7, 13, 8, 3, 10, 5]
2 通りの周遊経路が表示されましたが、逆回りの経路があるので、実際の経路は次の 1 通りしかありません。
┌─┬─┐
│０│７│
┌─┼─┼─┼─┐
│６│11│４│13│
├─┼─┼─┼─┤
│１│×│×│８│
├─┼─┼─┼─┤
│10│５│12│３│
└─┼─┼─┼─┘
│２│９│
└─┴─┘
図 : 周遊経路
●ワーンスドロフの規則
「騎士の巡歴」を解くには、基本的にはすべての飛び方を試してみるしか方法がないように思われます。小さな盤面であれば単純なバックトラックで簡単に解くことができますが、大きな盤面になると時間がとてもかかることになります。ところが 参考文献『ゲームにひそむ数理』によると、とても単純な規則で騎士の経路を求めることができるそうです。規則の説明を参考文献『ゲームにひそむ数理』 (72ページ) より引用します。
[ワーンスドロフの規則]あるマスに飛び移ったとき, そのマスからさらに飛び移ることのできるすべてのマスを拾い上げる. そして, それぞれのマスからさらに何個のマスに飛び移れるかを数え, 最小の飛び方しかできないマスに飛び移る。ただし, 対象となるマスが 2 個以上あれば, そのなかの任意のマスを選ぶ.
この規則は「欲張り法」と呼ばれるアルゴリズムと同じです。簡単な例ですが、お釣を払うときに硬貨の枚数を最小にする払い方は、欲張り法で求めることができます。たとえば、765 円のお釣を払う場合、500 円硬貨 1 枚、100 円硬貨 2 枚、50 円硬貨 1 枚、10 円硬貨 1 枚、5 円硬貨 1 枚の計 6 枚が硬貨の枚数を最小にする払い方です。これは、「高額の硬貨から順番に使って払う」という方法で実現できます。つまり、高い硬貨から使っていくという点で「欲張り」なわけです。
ところが、硬貨の種類が異なると、欲張り法では最適解を求めることができない場合もあります。たとえば、25 円硬貨はあるが 5 円硬貨はないとしましょう。40 円のお釣を払う場合、欲張り法では 25 円硬貨 1 枚、10 円硬貨 1 枚、1 円硬貨 5 枚の計 7 枚になりますが、10 円硬貨 4 枚の方が枚数は少なくなりますね。このように、問題の条件によっては欲張り法で最適解を求めることはできません。したがって、欲張り法を使って問題を解く場合は、それが最適解になることを証明する必要があります。
ワーンスドロフの規則の場合、騎士の飛び方がいちばん少ないマスを選ぶところが「欲張り」なわけです。実に単純でわかりやすい規則なのですが、参考文献『ゲームにひそむ数理』によると、これで確実にすべてのマスを訪問できることはまだ証明されておらず、騎士巡歴に関する有名な未解決問題なのだそうです。
●プログラムの作成
それではプログラムを作りましょう。最近のパソコンは高性能なので、飛び移ることができるマスの数を探索のときに求めても高速に解くことができます。
リスト : 欲張り法で騎士の巡歴を解く
# 移動できるマスの個数を求める
def move_count(board, adjacent, n):
c = 0
for x in adjacent[n]:
if not board[x]: c += 1
return c if c > 0 else 9
# 経路の生成
def make_path(board, adjacent, s):
path = [s]
board[s] = 1
n = 2
while n <= len(board):
xs = [(m, move_count(board, adjacent, m)) for m in adjacent[path[-1]] if board[m] == 0]
if not xs:
# 移動先が見つからない
return []
x, _ = min(xs, key = lambda y: y[1])
board[x] = n
path.append(x)
n += 1
return path
# 欲張り法で経路を探す
def solver1(size, s):
adjacent = make_adjacent(size)
board = [0] * (size * size)
path = make_path(board, adjacent, s)
if path:
print_board(board, size)
else:
print('can not make path')
return path
関数 slover1() の引数 size が盤面の大きさ、s が出発点を表します。盤面は Python のリスト (一次元配列) で表します。board は 0 に初期化して、騎士が移動した順番をセットします。隣接リストは関数 make_adjacent() で生成し、変数 adjacent にセットします。
騎士の経路は関数 make_path() で生成します。引数に盤面 board、隣接リスト adjacent、出発点 s を渡します。最初に、経路を表す変数 path を [s] に初期化し、board[s] に 1 をセットします。変数 n は騎士が移動した順番を表します。あとは、while ループの中で、ワーンスドロフの規則に従って騎士を移動します。
騎士の現在地点は path[-1] で求めることができます。adjacent[path[-1]] から次の飛び先を取り出して変数 m にセットし、そこから移動できるマスの個数を関数 count_move() で求めます。この処理を内包表記を使って行っています。生成されるリストは変数 xs にセットします。リストの要素はタプル (マスの位置, 移動可能なマスの個数) です。
変数 xs が空リストの場合、騎士の移動先が見つからないので空リストを返します。そうでなければ、min() で飛び先の個数が最小のマス x を選び、board[x] に n をセットし、path に x を追加します。あとは n を +1 して次の移動先を求めます。
move_count() は引数 n の飛び先 x を adjacent から求め、board[x] が 0 の個数を求めます。c が 0 の場合、飛び先が無いので 8 よりも大きな値 (たとえば 9) を返します。0 を返すと、min() でそのマスを選択することになり、プログラムは正常に動作しません。ご注意ください。
あとのプログラムは簡単なので説明は割愛させていただきます。詳細はプログラムリスト２をお読みくださいませ。
●実行結果
それでは実際に試してみましょう。出発点は左上隅 (0) にしました。
>>> solver1(5, 0) 1 14 9 20 3 24 19 2 15 10 13 8 25 4 21 18 23 6 11 16 7 12 17 22 5 [0, 7, 4, 13, 24, 17, 20, 11, 2, 9, 18, 21, 10, 1, 8, 19, 22, 15, 6, 3, 14, 23, 16, 5, 12] >>> solver1(6, 0) 1 32 9 18 3 34 10 19 2 33 28 17 31 8 29 16 35 4 20 11 36 27 24 15 7 30 13 22 5 26 12 21 6 25 14 23 [0, 8, 4, 17, 28, 32, 24, 13, 2, 6, 19, 30, 26, 34, 23, 15, 11, 3, 7, 18, 31, 27, 35, 22, 33, 29, 21, 10, 14, 25, 12, 1, 9, 5, 16, 20] >>> solver1(7, 0) 1 36 17 40 3 26 29 18 43 2 37 28 39 4 35 16 41 44 25 30 27 42 19 48 31 38 5 24 15 34 45 22 47 8 11 20 49 32 13 10 23 6 33 14 21 46 7 12 9 [0, 9, 4, 13, 26, 41, 46, 33, 48, 39, 34, 47, 38, 43, 28, 15, 2, 7, 22, 35, 44, 31, 40, 27, 18, 5, 20, 11, 6, 19, 24, 37, 42, 29, 14, 1, 10, 25, 12, 3, 16, 21, 8, 17, 30, 45, 32, 23, 36] >>> solver1(8, 0) 1 16 27 22 3 18 47 56 26 23 2 17 46 57 4 19 15 28 25 62 21 48 55 58 24 35 30 45 60 63 20 5 29 14 61 34 49 44 59 54 36 31 38 41 64 53 6 9 13 40 33 50 11 8 43 52 32 37 12 39 42 51 10 7 [0, 10, 4, 14, 31, 46, 63, 53, 47, 62, 52, 58, 48, 33, 16, 1, 11, 5, 15, 30, 20, 3, 9, 24, 18, 8, 2, 17, 32, 26, 41, 56, 50, 35, 25, 40, 57, 42, 59, 49, 43, 60, 54, 37, 27, 12, 6, 21, 36, 51, 61, 55, 45, 39, 22, 7, 13, 23, 38, 28, 34, 19, 29, 44] >>> solver1(9, 0) 1 50 19 74 3 52 31 54 5 18 81 2 51 32 75 4 35 30 49 20 73 80 77 34 53 6 55 72 17 78 33 70 39 76 29 36 21 48 71 62 79 68 37 56 7 16 63 22 69 38 61 40 67 28 23 44 47 64 41 66 57 8 11 46 15 42 25 60 13 10 27 58 43 24 45 14 65 26 59 12 9 [0, 11, 4, 15, 8, 25, 44, 61, 80, 69, 62, 79, 68, 75, 64, 45, 28, 9, 2, 19, 36, 47, 54, 73, 66, 77, 70, 53, 34, 17, 6, 13, 30, 23, 16, 35, 42, 49, 32, 51, 58, 65, 72, 55, 74, 63, 56, 37, 18, 1, 12, 5, 24, 7, 26, 43, 60, 71, 78, 67, 50, 39, 46, 57, 76, 59, 52, 41, 48, 31, 38, 27, 20, 3, 14, 33, 22, 29, 40, 21, 10] >>> solver1(10, 0) 1 58 17 40 3 56 95 42 5 46 18 39 2 57 94 41 4 45 86 43 59 16 83 62 55 96 85 98 47 6 38 19 60 93 84 99 54 91 44 87 15 82 63 80 61 92 97 88 7 48 20 37 74 77 100 79 66 53 90 29 73 14 81 64 75 68 89 28 49 8 36 21 76 69 78 65 52 67 30 27 13 72 23 34 11 70 25 32 9 50 22 35 12 71 24 33 10 51 26 31 [0, 12, 4, 16, 8, 29, 48, 69, 88, 96, 84, 92, 80, 61, 40, 21, 2, 10, 31, 50, 71, 90, 82, 94, 86, 98, 79, 67, 59, 78, 99, 87, 95, 83, 91, 70, 51, 30, 11, 3, 15, 7, 19, 38, 17, 9, 28, 49, 68, 89, 97, 76, 57, 36, 24, 5, 13, 1, 20, 32, 44, 23, 42, 63, 75, 56, 77, 65, 73, 85, 93, 81, 60, 52, 64, 72, 53, 74, 55, 43, 62, 41, 22, 34, 26, 18, 39, 47, 66, 58, 37, 45, 33, 14, 6, 25, 46, 27, 35, 54]
盤面の大きさが 5 - 10 の場合、ワーンスドロフの規則で騎士の経路を求めることができました。Python / Tkinter で図に表すと次のようになります。
図 : 8 行 8 列盤
図 : 9 行 6 列盤
図 : 10 行 10 列盤
ところで、今回は出発点を 0 にしましたが、出発点の選び方によっては経路を生成できないことがあります。以下のプログラムで確認することができます。
リスト : 経路を生成できない出発点を表示する
def not_make_position(size):
adjacent = make_adjacent(size)
for x in range(size * size):
board = [0] * (size * size)
path = make_path(board, adjacent, x)
if not path:
print(x, end=' ')
print()
>>> not_make_position(6) 15 >>> not_make_position(8) 44 >>> not_make_position(10) 21 61 >>> not_make_position(12) 22 91 96 101 113 126
size が 6, 8, 10, 12 の場合、周遊コースを生成できるので、どの地点から出発しても経路を生成できると思ったのですが、そうではないようです。ワーンスドロフの規則では解けない場合があるのかもしれません。それとも、M.Hiroi のプログラムに何か問題があるのか、ちょっとよくわかりませんでした。何かお気づきの点がありましたら、ご教示お願いいたします。
●周遊コースへの変換
求めた経路が周遊コースになっていない場合、周遊コースに変換する簡単な方法があります。たとえば、下図のような 6 行 6 列盤の経路を周遊コースに変換してみましょう。
図 : 6 行 6 列盤の騎士の経路 (1)
┌─┬─┬─┬─┬─┬─┐ │32│１│24│15│30│７│ ├─┼─┼─┼─┼─┼─┤ │23│14│31│８│25│16│ ├─┼─┼─┼─┼─┼─┤ │２│33│０│17│６│29│ ├─┼─┼─┼─┼─┼─┤ │13│22│35│26│９│18│ ├─┼─┼─┼─┼─┼─┤ │34│３│20│11│28│５│ ├─┼─┼─┼─┼─┼─┤ │21│12│27│４│19│10│ └─┴─┴─┴─┴─┴─┘ 図：6 行 6 列盤の騎士の経路 (2)
右の図は騎士が跳ぶ順番を表していて、スタート (0番目) から飛び移れる地点を赤で、ゴール (35番目) から飛び移れる地点を青で示しています。ここで、12 番目と 13 番目に注目してください。13 番目の位置はスタートに飛び移ることができ、12 番目からはゴールに飛び移ることができます。
ここがポイントです。騎士はスタートから 12 番目まで移動し、ここでゴール (35番目) に飛び移ることができます。そして、経路を逆順にたどっていけば、13 番目の位置に到達しスタートに戻ることができます。これで、経路を周遊コースに変換することができました。これを図に表すと次のようになります。
12 13
↓ ↓
14─１─12─25─33─29─16─５─９─22─35─27─31×18─７─３─11─15
↑ │ │ │
└───────────────────────┼─┘ │
│ │
┌───────────────────────┘ │
↓ │
20─24─13─０─８─９─17─28─32─21─10─２─６─19─30─26─34─23
図 : 周遊コースへの変換
また、12 番目と 13 番目だけではなく、2 番目と 3 番目または 8 番目と 9 番目でも同じように変換することができます。
図 : 6 行 6 列盤の周遊コース
ところで、今回はうまく周遊コースに変換できましたが、ワーンスドロフの規則では、この方法で変換できない経路が生成される場合もあります。プログラムで周遊コースを生成する場合、変換できない経路であれば出発地点を変更して別経路を生成する、などの工夫が必要になるでしょう。ご注意くださいませ。
●プログラムの作成
このアルゴリズムをそのままプログラムすると、次のようになります。
リスト : 欲張り法で巡回路を探す
# 巡回路の生成
def make_circuit(board, adjacent, path):
if path[0] in adjacent[path[-1]]:
return path
for p1 in adjacent[path[0]]:
for p2 in adjacent[path[-1]]:
if board[p2] + 1 == board[p1]:
# 付け替える位置を発見
a = path[:board[p2]]
b = path[board[p2]:]
b.reverse()
return a + b
return []
def solver2(size):
adjacent = make_adjacent(size)
for x in range(size * size):
board = [0] * (size * size)
path = make_path(board, adjacent, x)
if not path: continue
circuit = make_circuit(board, adjacent, path)
if circuit:
for i, p in enumerate(circuit):
board[p] = i + 1
print_board(board, size)
draw(size, circuit, True)
return circuit
関数 solver2() の引数 size は盤面の大きさを表します。solver2() は make_path() で経路を生成し、それを関数 make_circuit() で巡回路 (周遊コース) に変換します。経路や巡回路を生成できなかった場合、出発点を変更して新しい経路を生成します。
make_circuit() は最初に引数 path が巡回路になっているかチェックします。そうであれば、path をそのまま返します。次の for ループで経路を付け替える位置を探します。スタートからの飛び先を p1 にセットし、ゴールからの飛び先を p2 にセットします。board[p2] の次の地点が board[p1] と等しい場合、巡回路に変換することができます。経路の後半部分をコピーして、それを reverse() で反転します。あとは、経路の前半部分と反転した後半部分を連結すれば OK です。
●実行結果
それでは実際に試してみましょう。
>>> solver2(6) 1 12 35 26 3 10 34 25 2 11 16 27 13 36 15 28 9 4 24 33 8 17 20 29 7 14 31 22 5 18 32 23 6 19 30 21 [0, 8, 4, 17, 28, 32, 24, 20, 16, 5, 9, 1, 12, 25, 14, 10, 21, 29, 33, 22, 35, 27, 31, 18, 7, 3, 11, 15, 23, 34, 26, 30, 19, 6, 2, 13] >>> solver2(8) 4 1 6 21 60 45 16 19 7 22 3 44 17 20 59 46 2 5 64 61 40 47 18 15 23 8 43 48 63 32 41 58 36 49 62 27 42 39 14 31 9 24 35 38 33 28 57 54 50 37 26 11 52 55 30 13 25 10 51 34 29 12 53 56 [1, 16, 10, 0, 17, 2, 8, 25, 40, 57, 51, 61, 55, 38, 23, 6, 12, 22, 7, 13, 3, 9, 24, 41, 56, 50, 35, 45, 60, 54, 39, 29, 44, 59, 42, 32, 49, 43, 37, 20, 30, 36, 26, 11, 5, 15, 21, 27, 33, 48, 58, 52, 62, 47, 53, 63, 46, 31, 14, 4, 19, 34, 28, 18] >>> solver2(10) 4 1 6 31 28 89 64 33 26 37 7 30 3 90 49 32 27 36 63 34 2 5 100 29 88 65 54 59 38 25 99 8 91 48 57 50 87 62 35 60 92 47 98 77 66 55 58 53 24 39 9 80 93 56 51 74 69 86 61 20 46 97 76 73 78 67 52 21 40 23 81 10 79 94 75 70 85 68 19 16 96 45 12 83 72 43 14 17 22 41 11 82 95 44 13 84 71 42 15 18 [1, 20, 12, 0, 21, 2, 10, 31, 50, 71, 90, 82, 94, 86, 98, 79, 87, 99, 78, 59, 67, 88, 69, 48, 29, 8, 16, 4, 23, 11, 3, 15, 7, 19, 38, 17, 9, 28, 49, 68, 89, 97, 85, 93, 81, 60, 41, 33, 14, 35, 54, 66, 47, 26, 45, 53, 34, 46, 27, 39, 58, 37, 18, 6, 25, 44, 65, 77, 56, 75, 96, 84, 63, 55, 74, 62, 43, 64, 72, 51, 70, 91, 83, 95, 76, 57, 36, 24, 5, 13, 32, 40, 52, 73, 92, 80, 61, 42, 30, 22]
図 : 6 行 6 列盤
図 : 8 行 8 列盤
図 : 10 行 10 列盤
このように、ワーンスドロフの規則を使うと大きな盤面でも高速に「騎士の周遊」を解くことができます。
●プログラムリスト１
#
# knight.py : 騎士の巡歴と周遊
#
# Copyright (C) 2022 Makoto Hiroi
#
# 隣接リスト
adjacent = [
[5, 7], # 0
[6, 8], # 1
[3, 7], # 2
[2, 8, 10], # 3
[9, 11], # 4
[0, 6, 10], # 5
[1, 5, 11], # 6
[0, 2], # 7
[1, 3, 9], # 8
[4, 8], # 9
[3, 5], # 10
[4, 6] # 11
]
# 深さ優先探索
def dfs(n = 1, path = [0]):
if n == 12:
print(path)
else:
for x in adjacent[path[-1]]:
if x in path: continue
path.append(x)
dfs(n + 1, path)
path.pop()
# 騎士の移動
dx = ( 1, 2, 2, 1, -1, -2, -2, -1);
dy = (-2, -1, 1, 2, 2, 1, -1, -2);
# 盤面
board = [
[1,1,1,1,1,1,1],
[1,1,1,1,1,1,1],
[1,1,0,0,0,1,1],
[1,1,0,0,0,1,1],
[1,1,0,0,0,1,1],
[1,1,0,0,0,1,1],
[1,1,1,1,1,1,1],
[1,1,1,1,1,1,1]
]
# 盤面の表示
def print_board():
for y in range(2, 6):
for x in range(2, 5):
print('{:2d}'.format(board[y][x]), end=' ')
print()
print()
# 深さ優先探索
def dfs1(n = 1, x = 2, y = 2):
if board[x][y]: return
board[x][y] = n
if n == 12:
print_board()
else:
for a, b in zip(dx, dy):
dfs1(n + 1, x + a, y + b)
board[x][y] = 0
#
# 騎士の周遊
#
# 隣接リスト
adjacent1 = [
[5, 6], # 0
[2, 7], # 1
[1, 9], # 2
[7, 8, 10], # 3
[6, 9, 11], # 4
[0, 10], # 5
[0, 4, 10, 12], # 6
[1, 3, 9, 13], # 7
[3, 13], # 8
[2, 4, 7], # 9
[3, 5, 6], # 10
[4, 12], # 11
[6, 11], # 12
[7, 8] # 13
]
def dfs2(n = 1, path = [0]):
if n == 14 and path[-1] in adjacent1[path[0]]:
print(path)
else:
for x in adjacent1[path[-1]]:
if x in path: continue
path.append(x)
dfs2(n + 1, path)
path.pop()
●プログラムリスト２
#
# knight2.py : 騎士の周遊 (ワーンスドロフの規則 : 欲張り法の一種)
#
# Copyright (C) 2022 Makoto Hiroi
#
import tkinter as tk
# 描画
def draw(size, xs, flag):
root = tk.Tk()
c0 = tk.Canvas(root, width = 30 * size + 20, height = 30 * size + 20)
c0.pack()
for y in range(size):
for x in range(size):
if (y + x) % 2 == 0:
color = 'white'
else:
color = 'black'
x1 = x * 30 + 10
y1 = y * 30 + 10
c0.create_rectangle(x1, y1, x1 + 30, y1 + 30, fill = color)
s = -1 if flag else 0
for i in range(s, size * size - 1):
y1 = (xs[i] // size) * 30 + 30
x1 = (xs[i] % size) * 30 + 30
y2 = (xs[i + 1] // size) * 30 + 30
x2 = (xs[i + 1] % size) * 30 + 30
c0.create_line(x1, y1, x2, y2, fill = 'cyan', width = 2.0)
root.mainloop()
# ナイトの移動量
dx = ( 1, 2, 2, 1, -1, -2, -2, -1)
dy = (-2, -1, 1, 2, 2, 1, -1, -2)
# 隣接リストの生成
def make_adjacent(size):
size2 = size * size
zs = []
for y in range(size):
for x in range(size):
xs = []
for a, b in zip(dx, dy):
x1 = x + a
y1 = y + b
if 0 <= x1 < size and 0 <= y1 < size:
xs.append(y1 * size + x1)
zs.append(xs)
return zs
# 盤面の表示
def print_board(board, size):
for i, n in enumerate(board):
print('{:3d}'.format(n), end=' ')
if (i + 1) % size == 0: print()
print()
# 移動できる場所の個数を求める
def move_count(board, adjacent, n):
c = 0
for x in adjacent[n]:
if not board[x]: c += 1
return c if c > 0 else 9
# 経路の生成
def make_path(board, adjacent, s):
path = [s]
board[s] = 1
n = 2
while n <= len(board):
xs = [(m, move_count(board, adjacent, m)) for m in adjacent[path[-1]] if board[m] == 0]
if not xs:
# 移動先が見つからない
return []
x, _ = min(xs, key = lambda y: y[1])
board[x] = n
path.append(x)
n += 1
return path
# 巡回路の生成
def make_circuit(board, adjacent, path):
if path[0] in adjacent[path[-1]]:
return path
for p1 in adjacent[path[0]]:
for p2 in adjacent[path[-1]]:
if board[p2] + 1 == board[p1]:
# 付け替える位置を発見
a = path[:board[p2]]
b = path[board[p2]:]
b.reverse()
return a + b
return []
# 欲張り法で経路を探す
def solver1(size, s):
adjacent = make_adjacent(size)
board = [0] * (size * size)
path = make_path(board, adjacent, s)
if path:
print_board(board, size)
draw(size, path, False)
else:
print('can not make path')
return path
def not_make_position(size):
adjacent = make_adjacent(size)
for x in range(size * size):
board = [0] * (size * size)
path = make_path(board, adjacent, x)
if not path:
print(x, end=' ')
print()
# 欲張り法で巡回路を探す
def solver2(size):
adjacent = make_adjacent(size)
for x in range(size * size):
board = [0] * (size * size)
path = make_path(board, adjacent, x)
if not path: continue
circuit = make_circuit(board, adjacent, path)
if circuit:
for i, p in enumerate(circuit):
board[p] = i + 1
print_board(board, size)
draw(size, circuit, True)
return circuit