技術と魚

雑感と備忘録

ピクロスと数学〜実は奥が深いゲーム

ピクロスというゲームがある。縦列と横列にそれぞれ数字が並び、数字の数だけ黒マスが連続する。数字が２つ並ぶときは、間に白マスが存在する。この数字をもとにすべての黒マスを特定するゲームだ。一度は見たことがあると思う。

Jupiter社が開発しているNintendo SwitchのピクロスSというゲームソフトがある。このゲームの一つの特徴は 「確定列を知らせる」 という機能があることだ。行または列の制約から○または✗が確定可能なものが存在する場合、その列の数字を青く表示して教えてくれる。

f:id:norainu234:20170828131917j:plain
数字が青くなっているのが確定列 （My Nintendo Storeより転載）

確定列内の確定可能なマスを確定すると、新たな確定列が生じるという流れで、このゲームに収録される問題は（おそらくすべて）クリアすることができるようになっている。

ここで 「いかなる問題も、この確定列を確定し続けるという方法で解けるのかどうか」 を誰しも疑問に思うだろう。え？思わないって？

今回はこれについて考えたい。

曖昧な議論をしても意味がないので数学的に定義をしていく。まず、マスの大きさが縦横に N \times M のサイズをとりうる。 N \times M サイズの問題の集合を、 (N,M)-Problem ということにする。(N,M)-Problemの解は、 N \times M サイズの○✗絵になる。すべての N \times M サイズの絵の集合を (N,M)-Image ということにする。

(N,M)-Imageを一つとれば、そこから (N,M)-Problem を簡単に作ることができる。この写像を F_{N,M} あるいは単に F で表すとする。

F_{N,M} : \text{(N,M)-Image} \rightarrow \text{(N,M)-Problem}

p \in \text{(N,M)-Problem} と im \in \text{(N,M)-Image} に対し F(im) = p であるとき、 imは問題 pの解であるという。

[事実] 解を2つ以上持つ(N,M)-Problemが存在する。数学的に言えば、Fは単射でない。

例

以下の(2,2)-Problem

# 1 1
1 _ _
1 _ _

は次の2つの(2,2)-Imageが解となる。

# 1 1
1 o x
1 x o

# 1 1
1 x o
1 o x

このことから、必ずしも解が一意には決まらないものがあるとわかった。一意に解けるという性質は重要だから特別な定義を与える。

解が唯一である(N,M)-Problemを、唯一解を持つ (N,M)-Problemといい、 (N,M)-Solvable で表そう。つまり、(N,M)-Solvableの元pを一つとれば、 F(im)=pとなる (N,M)-Image の元 im が唯一つ存在する。

ゲームの製作者は唯一解を持つ問題を収録したいし、ユーザはある現実的なアルゴリズムに沿って唯一解を解ける必要がある。ゲームには唯一解を持つ問題が収録されていると仮定して、特定のアルゴリズムでが必ず解に到達できるかどうか、というのが焦点となる。まずはアルゴリズムについて定義しておく。

任意の(N,M)-Solvableを入力とし、(N,M)-Imageを出力して終了するか失敗するようなアルゴリズムを、Solverということにしよう。Solverに対して次の性質を定義しておく。

  • 健全性 任意の唯一解を持つ問題 p \in \text{(N,M)-Solvable}を入力し、解imを出力して終了した場合、 F(im)=pであること
  • 完全性 任意の唯一解を持つ問題 p \in \text{(N,M)-Solvable}を入力したとき、必ず F(im)=p を満たす解imを出力して終了する

完全であれば健全であるが、健全だったとしても完全とは限らない。

ここで自明で完全なSolverとして、 総当りアルゴリズム がある。(N,M)-Imageそのものが有限なので、それらを一つずつ問題に変換して一致するかどうかを見るだけだ。当然のことながら計算量は O(2^{N \times M}) 相当なので現実的でない。

次にピクロスSのように、確定列を確定し続けるというSolverを考える。このSolverを SimpleSolver と呼ぶことにしよう。この手順は細かく定義しないが、おおよそ次の通り。

  • (1) すべての行と列を次の通り走査する
  • (1-1) 与えられた行または列内で可能な配置をすべて計算する
  • (1-2) (1-1)で洗い出したどの配置をとっても○または✗が決まっているマスを確定する
  • (2) 未確定なマスが存在しない場合 → 解を返して終了
  • (3) (1)の結果確定するマスが存在した → (1)に戻る
  • (4) (1)の結果確定するマスが一つもなかった → 失敗

さて「SimpleSolverは完全か？」を考えよう。ようやくもとの関心事を言語化できた。

[結論] SimpleSolverは完全ではない

例 (4,4)-Problem

# 2 1 2 2
2 _ _ _ _
2 _ _ _ _
2 _ _ _ _
1 _ _ _ _

を考える。

初順の時点で、SimpleSolverはステップ(1)で確定マスを見つけることができず、ステップ(4)で失敗する。

しかし、この問題の解は唯一以下しかないので、(4,4)-Solvableである

# 2 1 2 2
2 x x o o
2 x x o o
2 o o x x
1 o x x x

つまり、確定列を確定し続けてもクリアできない問題が作れることがわかった。ちなみに上記の様な問題の解き方としてこの界隈で「仮定法」と呼ばれている方法がある。

仮に左上のマスをoであると仮定してみる

# 2 1 2 2
2 o _ _ _
2 _ _ _ _
2 _ _ _ _
1 _ _ _ _

周辺の条件からいくつか決定できる

# 2 1 2 2
2 o o x x
2 o _ _ _
2 x _ _ _
1 x _ _ _

しかし、(2,2)マスはoもxも入れられず、条件を満たすことができない

# 2 1 2 2
2 o o x x
2 o ? _ _
2 x _ _ _
1 x _ _ _

よって左上のマスはxになる

# 2 1 2 2
2 x _ _ _
2 _ _ _ _
2 _ _ _ _
1 _ _ _ _

ここまで分かれば、SimpleSolverで解ける

この例が示すことは、縦横の一つの列の条件からではなく、 2つ以上の列の条件をみないと判断できない局面がある ということだ。一見単純に見えるピクロスの奥深さが感じられる。

この延長で以下のようなことを調べても面白いかもしれないので、後は暇な人に託す。

  • (N,M)-Problemが(N,M)-Solvableかどうかの効率的な判定方法
  • より完全に近い現実的なSolverの検討
  • Solverのレベル分けや、難易度を表す不変量の構成

余談

このピクロスSをやる前にスーファミの「マリオのスーパーピクロス」をやっていたんだけど、確定列機能なんてものはなく、仮定法を使いまくっていた。ピクロスSでは確定列機能があるので、実はマリオも確定列が見えていればもっと単純にクリアできたのでは？と思った。しかし、「明らかにマリオの方がムズかった！」という体感があったので、その何とも言えない違和感を解決したくなってこんなことを風呂場で小一時間考えてしまった。

ところでマリオのピクロスには複数解のある問題が混ざっていて、別解にたどり着いた場合はクリアにならない。こんなことが起きてしまうぐらい、(N,M)-Solvableかどうかの判定はきっと難しい。それに対して、ピクロスSはSimpleSolverで解ける程度の問題しかなく、しかもユーザもある程度達成感を持てる。しかもSimpleSolverで解けたかどうかを確認すれば問題の妥当性をチェックできる。難易度にこだわらないで簡単な問題しか作らないほうが製作者はお金が儲かるかもしれない。