ぷよぷよと計算の複雑さ

study

第2回ぷよマスターズで準優勝した松金氏の発表。
どちらかというと「なぞぷよ」のネタ。盤面は可能な限り広くとった上での四色+おじゃまぷよ連鎖数判定問題がNP完全という話。3-PARTITIONでYESなら連鎖数判定問題でk連鎖可能なインスタンスが作れて、逆に連鎖数判定問題でk連鎖可能なら3-PARTITIONでもYESなインスタンスが作れるという筋。

参考文献によると、

  • ぷよぷよ全消判定問題はNP完全。
  • 初期配置が空の2色全消判定問題はPらしい。
  • 2色連鎖数判定問題は……紹介されてたか?

ふむ、面白い。