#computational-complexity

「一つの鍵と、一つの扉」を守れるか——ダンジョン生成が苦手なこと、色を積むだけのパズルがNP困難になる理由

今日は2本。IEEE CoG 2026(マドリード、9月2日発表)の「Evolutionary Wave Function Collapse」は、迷路やダンジョンを生成する定番手法WFCに進化計算を組み合わせ、迷路のつながりやすさは伸ばせても、「鍵と扉をちょうど1組」のような盤面全体にまたがる制約は依然として苦手だと示した。もう1本、TU Wien(オーストリア)のLinus Klockerによる論文は、色付きスタックを合体させて消すだけのスマホパズル『Hexasort』が、色を1種類に絞り盤面を木構造まで単純化してもNP困難であり続けることを証明している。生成する側と、難しさを証明する側。どちらも「パズルの難しさはどこに宿るか」という同じ問いに違う角度から答えている。