パズルで鍛えるアルゴリズム力
技術評論社
著者：大槻兼資
はじめに
第1章 アルゴリズム入門
1-1 テンパズル 〜力まかせ探索
テンパズル
パズルに挑戦
テンパズルを解くアルゴリズム
コラム スタックとキュー Part 1
コラム コンピュータの計算力
テンパズルソルバーの実装
テンパズルの掘り下げ
まとめ
パズルの解答
コラム アルゴリズムとプログラムの違い
もう一歩 トランプゲーム「四則」
1-2 小町算 〜再帰関数
小町算
手で解いてみる
小町算を解くアルゴリズム
コラム 再帰呼び出しの効率化
小町算ソルバーの実装
まとめ
もう一歩 小町算の問題を作る
1-3 虫食算 〜枝刈り
虫食算
パズルに挑戦
虫食算を解くアルゴリズム
枝刈り
コラム 組合せ爆発
虫食算ソルバーの部品の準備
虫食算ソルバーの実装
まとめ
パズルの解答
もう一歩 虫食算を作る
第2章 グラフアルゴリズム
2-1 数独 〜深さ優先探索1
数独
数独の手筋の紹介
グラフ
コラム ケーニヒスベルクの橋と四色問題
数独を解くアルゴリズム
数独ソルバーの部品の準備
数独ソルバーの実装
高速化のための工夫
まとめ
パズルの解答
コラム 数独の最小ヒント数は17
もう一歩 数独を作る 〜山登り法
2-2 覆面算 〜深さ優先探索2
覆面算
コラム パズルの巨匠紹介 Part 1：デュードニー
パズルに挑戦
コラム 言葉パズルで覆面算を作る！
覆面算ソルバーの実装
覆面算を作るアルゴリズム
リストアップ法による覆面算メイカーの実装
ワイルドカード法による覆面算メイカーの実装
まとめ
パズルの解答
もう一歩 虫食算と覆面算の融合！
2-3 迷路 〜幅優先探索
迷路
コラム パズルとは何か
迷路に関連するパズル
今回解く問題の設定
迷路ソルバーの実装
コラム サム・ロイドの『ハンモック・パズル』
グラフ上の幅優先探索
コラム スタックとキュー Part 2
油分け算への応用
まとめ
パズルの解答
もう一歩 碁石拾い
第3章 発展的なアルゴリズム
3-1 15パズル 〜反復深化A*
15パズル
コラム サム・ロイドの『14-15パズル』
手で解いてみる
コラム 一般サイズの15パズル
15パズルソルバーの方針
反復深化深さ優先探索
反復深化A*
15パズルソルバーの実装
まとめ
コラム ルービックキューブのGod’s Number
3-2 4×4オセロ 〜ゲーム探索
4×4オセロ
「ゲームを解く」ということ
各ゲームの解析状況
手で解いてみる
ゲーム解析をグラフ探索で考える
ゲーム探索の実装
4×4オセロソルバーの実装
まとめ
3-3 編集距離 〜動的計画法
編集距離
パズルに挑戦
コラム 編集距離の実応用
編集距離をグラフで表す
動的計画法
編集距離ソルバーの実装
コラム アルゴリズムの計算量
まとめ
パズルの解答
コラム ダイクストラ法
3-4 ドミノタイリング 〜マッチング
ドミノタイリング
コラム パズルの巨匠紹介 Part 2：ロイド
手で解いてみる
コラム テトロミノ
二部マッチング問題への帰着
二部マッチング問題の解法
ドミノタイリングソルバーの実装
まとめ
本書全体のまとめ
ブックガイド
索引