ナイト・ツアーとグラフ巡歴パズル

Q: ナイト・ツアーとグラフ巡歴パズルとは何ですか？

チェス盤上の各マスを頂点 V、ナイトの合法手で移動できるマス同士を結ぶ辺を E とする無向グラフ G=(V, E) において、全頂点をちょうど一度だけ通る路を**ハミルトン路（Hamiltonian Path）**、閉路をなす場合を**ハミルトン閉路（Hamiltonian Cycle）**と呼びます。

Q: ナイト・ツアーとグラフ巡歴パズルは社会やプログラミングでどのように使われていますか？

Warnsdorffのヒューリスティクスによるナイトツアー・ソルバー: バックトラッキングの爆発を回避し、貪欲法で一発解を導出するTypeScript実装です。物流巡回やプリント基板の経路探索に応用されます。

チェスの騎士で全マスを1度ずつ踏破せよ。ハミルトン路と貪欲探索の極致

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: チェスのナイトの動き（縦2横1または縦1横2）だけで、盤上のすべてのマスを一度だけ訪れる経路をナイト・ツアー（Knight's Tour）と呼ぶ。
2: 素朴な総当たり（全探索）を行うと天文学的な計算量でフリーズする（NP完全クラス）。
3: 1823年に考案された「ヴァルンスドルフの規則（次の手数が最も少ないマスへ優先して進む）」を用いると、一瞬で解が見つかる。

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

9世紀のインドやアラブの文献にも登場する歴史的な数学パズル。チェスの「ナイト（桂馬）」の変則的なL字ジャンプを用いて、盤面の全マスを『重複なくちょうど1回ずつ』すべて訪問できるか？という問題です。グラフ理論における「ハミルトン路（Hamiltonian Path）問題」の代表格であり、巡回セールスマン問題（TSP）など現代の難関最適化アルゴリズムの基礎となっています。

身につく武器・思考力

バックトラッキング（深さ優先探索での後戻り）の概念と、Warnsdorffヒューリスティクス（局所的な候補数が少ないものから選ぶ貪欲法）という実用的な探索最適化の知恵が身につきます。

実社会・ITでの活躍現場

•回路基板（PCB）の穴あけドリルの最短移動経路最適化
•配送トラック・ドローンの巡回ルート配送最適化（TSP問題）
•ゲームAIの迷路踏破・バックトラッキング探索エンジン

Layer 1 — 直感・シミュレーター

5×5のチェス盤をクリックして、ナイトをL字型にジャンプさせて全25マスの踏破を目指してください。行き詰まったら「1手戻す」や、「AI解法（貪欲アルゴリズム）」を押すことで瞬時に自動踏破されるスマートなアルゴリズムを体感できます。

グラフ探索パズル：ナイト・ツアー（騎士巡歴）

チェスのナイトで 5×5 の全25マスを重複なく踏破せよ！

踏破数: 1 / 25 マス次の合法手候補: 2 箇所

緑色の点線マスが「桂馬跳び（L字型）」で次に進める候補地です。

直感チェック！ミニクイズ

ナイト・ツアーを高速に解く「ヴァルンスドルフの規則（ヒューリスティクス）」の基本方針として正しいものはどれでしょうか？

Layer 2 — 定義・受験・証明

定義

チェス盤上の各マスを頂点 $V$ 、ナイトの合法手で移動できるマス同士を結ぶ辺を $E$ とする無向グラフ $G=(V, E)$ において、全頂点をちょうど一度だけ通る路を**ハミルトン路（Hamiltonian Path）**、閉路をなす場合を**ハミルトン閉路（Hamiltonian Cycle）**と呼びます。

公式・数理モデル

G = (V, E), \quad |V| = N \times N, \quad \deg(v) \in \{2, 3, 4, 6, 8\}

証明・導出

一般のグラフにおけるハミルトン路の存在判定はNP完全問題です。しかし、正方格子盤上のナイトグラフにおいては、奇数×奇数の盤面（例: 5×5）では市松模様の白マスの数と黒マスの数の差が 1 となるため、ハミルトン閉路（元の位置に戻るツアー）は存在せず、開いたハミルトン路のみが存在することが二部グラフの性質から直ちに証明されます。

押さえておきたいポイント

グラフ理論におけるハミルトン路問題の具体例
Warnsdorffの規則（次数が最小の隣接頂点を貪欲選択）により線形時間に近い高速性で解ける
白黒の二部グラフ（Bipartite Graph）の性質により、毎手必ずマスの色が交互に入れ替わる

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

Warnsdorffのヒューリスティクスによるナイトツアー・ソルバー

バックトラッキングの爆発を回避し、貪欲法で一発解を導出するTypeScript実装です。物流巡回やプリント基板の経路探索に応用されます。

1const MOVES = [
2  [-2, -1], [-2, 1], [-1, -2], [-1, 2],
3  [1, -2],  [1, 2],  [2, -1],  [2, 1]
4];
5
6export function solveKnightTour(size: number = 5): number[][] | null {
7  const board: number[][] = Array.from({ length: size }, () => Array(size).fill(0));
8  let r = 0, c = 0;
9  board[r][c] = 1;
10
11  function getDegree(row: number, col: number): number {
12    let count = 0;
13    for (const [dr, dc] of MOVES) {
14      const nr = row + dr, nc = col + dc;
15      if (nr >= 0 && nr < size && nc >= 0 && nc < size && board[nr][nc] === 0) {
16        count++;
17      }
18    }
19    return count;
20  }
21
22  for (let step = 2; step <= size * size; step++) {
23    const candidates: [number, number, number][] = [];
24    for (const [dr, dc] of MOVES) {
25      const nr = r + dr, nc = c + dc;
26      if (nr >= 0 && nr < size && nc >= 0 && nc < size && board[nr][nc] === 0) {
27        candidates.push([nr, nc, getDegree(nr, nc)]);
28      }
29    }
30
31    if (candidates.length === 0) return null; // 手詰まり
32    // 候補次数が最小のマスを優先
33    candidates.sort((a, b) => a[2] - b[2]);
34    const [nextR, nextC] = candidates[0];
35    board[nextR][nextC] = step;
36    r = nextR;
37    c = nextC;
38  }
39
40  return board;
41}