カーブデータの基本

基本的な話ではあるが、カーブデータの記号について、書く。

図1 できないことを証明したい
カーブデータで、図1の状況を考える。記号が左上隅のマス(オレンジ色のマス)をとれないことは、直感的に明らかである。もう少し論理的に説明する方法を説明する。

図2 カーブデータはマスを埋めるパズルである

まず前提として、カーブデータはマスを埋めるパズルである。図2で、斜線のマスは、記号によって「占有される」マスとなる。

図3 2種類のマスがある

先ほどの斜線のマスだが、2種類に分類することができる。すなわち、線が直進しているマス(薄青色)と、それ以外のマス(オレンジ色)である。

図4 直進は消滅することができる

直進は「いくらでも伸びることができる」というのがカーブデータの性質であるが、実は「消滅することもできる」。これは重要なことである。

図5 記号の辺と頂点は、マスの種類と対応する

これも言うまでもないことだが、記号自体にも、対応する「辺」と「頂点」がある。一般に辺は1対n対応(n=0, 1, 2, ...)になるのに対して、頂点は必ず1対1で対応する。

図5 まずは記号を辺と頂点にする

丁寧に理詰めする場合は、まず図形を辺と頂点の構成として見直す。最初の図1の問題について考えてみる。左上の隅のマスが、この記号によって取られるマスだとすると、それは「辺のマス」か「頂点のマス」のいずれかとなる。ここで、上と左の壁は線の通過を禁止しているため、「辺のマス」にはならない。したがって「頂点のマス」になることが示される。既に示した通り、頂点は1対1対応するため、図5のオレンジ色の頂点の内のいずれかひとつが、私ですよ、と手を挙げる必要がある。

図6 勾配をつけてコーナー頂点を探す

次のステップは、図形の9つの頂点の内、どれが盤面の隅に出張できるか考えることである。壁の制約から考えると、頂点から上向きもしくは左向きの辺が出ていない、というのが必要条件になることがわかる。これを言葉通りに探すのは少しやりにくいので、私は個人的に図6のイメージを使っている。

図6では、右下から左上に向かって、大きな薄い緑色の矢印を描いている。これは、矢印の向きに坂道(下り坂)になっていることを意図している。どこかの頂点から始めたとき、坂道を下るように辺に沿って移動していく。そうすると、いくつかの頂点で動けなくなる。それらの頂点を赤色で示している。候補としては、この手順で得られる3点だけを考えればよい。この考え方は盤面の隅だけでなく、L字型の壁が疑似的に生じているような状況でも使用することができる。個人的にはこれでだいぶ見つけやすくなるのだが、わかりやすいかどうかは、人によるかもしれない。

今回はここまで。基本的な話を書いたつもりである。いずれ、もう少し高度な話も書きたいところだが、現時点では言語化できていない部分が多い。