概要
さまざまな問題を解決するためには,適切なアルゴリズムを判断したり,ときには自分で生み出したりできる力が必要です。そして,自在に使いこなせるようになるためには,知識をためるだけではなく実践してみることも大切です。
本書では,「テンパズル」「数独」「4×4オセロ」といったさまざまなパズルのソルバーを実装することで,楽しく効率的にアルゴリズムの設計力が磨けます。各アルゴリズムの概要は,図解でしっかり解説。数学的解法といった発展的な内容も盛り込みました。競技プログラミングに挑戦したい方の第一歩としてもお勧めの1冊です。
こんな方におすすめ
- 楽しくアルゴリズムを学びたい人
- 競技プログラミングに興味がある人
著者から一言
パズルは,論理的思考と試行錯誤によって楽しく解くことを目的とした問題のことです。頭を使う娯楽として,古くから世界中で親しまれてきました。じっくり考えることで少しずつ問題の構造が見えていき,最後にこれしかないという答えに到達するおもしろさ。じっくり考えてもなかなか答えが見つからず,それでも諦めずに考え続けることで閃く瞬間が訪れる喜び。パズルは,そんな楽しい時間と心地よい達成感を私たちにもたらしてくれます。
一方,アルゴリズムは問題を解くための手順のことです。世の中には,アルゴリズムの力で解決されている問題が数多くあります。カーナビは「現在地から目的地へと至る経路を求める」という問題を解いていますし,diffコマンドは「与えられた2つの文書の差分を求める」という問題を解いています。アルゴリズムのもつ優れた特徴として,解きたい問題において想定されるどのようなケースに対しても「同じ方法で」答えを導けることが挙げられます。数独を解くアルゴリズムを正しく実装すれば,どんな数独の問題を入力しても答えを出力するソルバーとなるのです。
本書では,パズルのソルバーを作ることをとおして,アルゴリズムを考える力を楽しく鍛えます。各節の冒頭では,さまざまなパズルを紹介します。まずは実際に手を動かして,それらのパズルを楽しく考察してみましょう。虫食算,数独,オセロなど,古くから広く親しまれてきたパズルは,ただ楽しいだけではなく,アルゴリズムを考える力を鍛えるのに役立つ要素を多く含んでいます。たとえば数独を解くとき,「このマスにはこの数字は入らない」「この数字はこのマスには入らない」といった考え方を活用する方は多いでしょう。これらの考え方は,アルゴリズムの世界では「探索の枝刈り」ともとらえられます。このことからもわかるように,パズルを考察して,ソルバーを実装していくうちに,アルゴリズム的思考力も自然に体得できるのです。
本書に掲載するソルバーは,パズルを解くのに必要最小限の機能のみを備えたものです。より高速化したり,機能を追加したり,例外処理を加えたりなど,工夫の余地が大いにあります。ぜひこれらのソルバーを改良して,読者のオリジナルのソルバーを作ってみてください。