組み合わせ爆発の問題を解こう その1 – 問題編
2012-09-14Mathematics
Google Developepr Dayという、Googleが開催するエンジニアのお祭りがあります。今年は無いみたいで残念ですが…。さて、このお祭りに参加するためには、Googleが出題する問題を解かなければいけません(Dev Quizと呼ばれています)。この問題の出来によって、参加の可否が決まりますので、エンジニアじゃない人が参加するのはなかなか大変だったりします…。
さて、去年のDev Quizから、最後の問題にして、最大の難問である「スライドパズル」をご紹介いたします。
まずは、問題から。
幅が 3 マスから 6 マスで、高さが 3 マスから 6 マスのボードが与えられます。 各マスは、パネルが置かれているか、壁があるか、空白であるかのいずれかです。 パネルには 1 から 9 あるいは A から Z のいずれかの文字が書かれており、同じ文字の書かれたパネルは存在しません。 壁は 0 個以上存在し、空白のマスはただ 1 つだけ存在します。 例えば、次のようなボードが与えられます。ここで、壁は = で、空白は 0 で表されています。
4 0 = 2 1 5 = 8 6 空白は、上下左右のマスのパネルと入れ替えることができます。上のマスのパネルと入れ替えることを U とよび、同様に、下左右のマスのパネルと入れ替えることをそれぞれ D, L, R とよぶものとします。壁を空白やパネルと入れ替えることはできません。
パズルを解くというのは、与えられたボードの各マスを操作して、ゴール状態に持っていくことです。
ゴール状態とは、上の行から各行順番に、左から右に 1, 2, 3, 4, …, 9, A, …, Z という順にパネルが並び、最も右下のマスに空白が配置された状態のことです。壁のあるマスに対応するパネルは存在しません。例えば、左上のマスが壁であれば、ボード上に 1 のパネルは存在しません。
例えば、上で与えられたボードのパズルを解くと以下のようになります。
4 0 = 2 1 5 = 8 6 ↓
1 2 = 4 5 6 = 8 0 スライドパズル – Google Developer Day 2011 Japan DevQuiz より、一部改変して引用。
実際の出題は、スライドパズルが5000問与えられて、5000問の問題を通して、スライドできるパネルの数が限定されていました。つまり、闇雲にスライドパズルを解いてはいけないんですね。できるだけスライドさせる回数を少くしなければいけません。また、この5000問の問題を、1週間程度で解かなければいけないため、自力では難しいでしょうし、実際に解いた時に使ったプログラムも提出しなければいけませんでした。
さて、実際に解いてみました。
これが最初の状態です。背景が黄色のマスが空白、灰色が壁、左色の数字は、完成時に入っている数字を表しています。
空白のマスを下に移動させました。
次に左。
上
右
下
右
下。これで完成ですね。
これ以外の動かし方もあるかもしれませんが、例題は7回スライドさせることで完成しました。次回から、解き方を考えてみたいと思います。
Dev Quizは、挑戦しがいのある問題が出題されていて、頭の体操にはとても良かったので、今年(2012年)開催されなかったことはちょっと残念でした。なお、こういった問題は、Top Coderのサイトなどでたくさん出題されています。Top Coderで名前が目立てば、IT系の企業からいろいろと声がかかることでしょう。
Topic
- Mathematics (15)
- Natural Language Processing (1)