作品紹介・あらすじ
さまざまな問題を解決するためには、適切なアルゴリズムを判断したり、ときには自分で生み出したりできる力が必要です。そして、自在に使いこなせるようになるためには、知識をためるだけではなく実践してみることも大切です。
本書では、「テンパズル」「数独」「4×4オセロ」といったさまざまなパズルのソルバーを実装することで、楽しく効率的にアルゴリズムの設計力が磨けます。各アルゴリズムの概要は、図解でしっかり解説。数学的解法といった発展的な内容も盛り込みました。競技プログラミングに挑戦したい方の第一歩としてもお勧めの1冊です。
■■■第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：ロイド
■手で解いてみる
■コラム テトロミノ
■二部マッチング問題への帰着
■二部マッチング問題の解法
■ドミノタイリングソルバーの実装
■まとめ
感想・レビュー・書評
関連する本
