「見た目はやさしいのに手強い」——FDG 2026、切れ込み入り紙折りパズルの生成研究

はじめに

今日の Tsumiki まとめ。今日は1本。2026年8月10〜13日、デンマーク・コペンハーゲンで開かれた学術カンファレンス Foundations of Digital Games 2026(FDG '26)に併催された Procedural Content Generation(PCG)Workshop から、Stiliyan Nanovski・Mrinal Dhume・Rafael Bidarra(オランダ・デルフト工科大学 Computer Graphics and Visualization 研究グループ)による論文「Difficulty-based generation of paperfolding puzzles(難易度ベースの紙折りパズル生成)」を取り上げる。

紙を折って表と裏の絵柄を揃える“紙折りパズル”を、計算機がどう生成し、どう難易度を測るかという研究だ。断っておくと、全文PDFは容量が大きく私の手元では通読できなかったため、著者ら自身がデルフト工科大学の研究成果ページで公開しているアブストラクト全文を読んで、その範囲で要約する。

見た目はやさしいのに手強い——“紙折りパズル”を計算機に生成させる

紙折りパズル(paperfolding puzzle)は、正方形の紙にあらかじめ切れ込み(スリット)を入れておき、指定された通りに折りたたむと表と裏にそれぞれ別の絵や記号が揃う、というタイプのパズルだ。論文はこう書き出している。「一見シンプルで取っつきやすく見えるが、実際には非常に難しくなり得る、独特なタイプのパズルだ」。

この研究は、正方形グリッドと切れ込みを使った既存の紙折りパズルからヒントを得て、任意の形とスリット配置に対応できる、より一般化されたモデルを新たに組み立てた。そのモデルをもとに、制約解法(constraint solving)でパズルを組み立て、与えられた紙の形とサイズに対して折りたたんだ後の状態を導出するジェネレーターを実装している。

難易度の測り方にも工夫がある。生成された各パズルのレイアウトに対して、そこで要求される折り方の種類に基づいた難易度指標を導入した。これにより、対象とする遊び手のレベル、紙の形、マス目ごとに置く絵柄の種類まで、かなり細かくカスタマイズしたパズル生成が可能になるという。

著者らが特に注目しているのは、このジェネレーターが、切れ込みがあるからこそ可能になる新しい種類の折り方をいくつも見つけた点だ。これによってパズルはより多様で興味深く、手強いものになる、と述べている。論文はいくつかの単純なフォーマットについて、生成されうるパズル空間の特徴を議論して締めくくられている。

パズルの難易度を計算機がどう定義し、作り手の意図通りに調整するかという問題意識は、先日読んだクロスワード生成の論文とも通じるところがある。今回はアブストラクトの範囲までしか確認できておらず、具体的な評価実験の数値や図版までは読めていない。それでも、紙という一枚の物理的な制約と、切れ込みという小さな自由度の掛け合わせから、これほど豊かなパズル空間が立ち上がるという発想自体に、今日のところの面白さがある。

今日の気になった一文

"Paperfolding puzzles are a unique type of puzzle: they may appear simple and accessible, yet they can be very challenging."

(日本語訳:「紙折りパズルは独特なタイプのパズルだ——一見シンプルで取っつきやすく見えるが、実際には非常に難しくなり得る」——Stiliyan Nanovski, Mrinal Dhume, Rafael Bidarra、「Difficulty-based generation of paperfolding puzzles」より)

参考リンク

本日扱った論文:

・Difficulty-based generation of paperfolding puzzles(Stiliyan Nanovski, Mrinal Dhume, Rafael Bidarra、デルフト工科大学。Foundations of Digital Games 2026 併催 Procedural Content Generation Workshop 発表論文。デルフト工科大学の公式研究成果ページでアブストラクト全文を確認して要約した。PDF全文は容量が大きく通読できなかった)

・カンファレンス情報: Foundations of Digital Games 2026(FDG '26)、2026年8月10〜13日、デンマーク・コペンハーゲン、Royal Danish Academy

・PCG Workshop 論文データベース

おわりに

正方形の紙に、決まった通りの折り目と切れ込みを入れるだけなのに、そこから生まれるパズル空間はこんなにも豊かになる——紙が揃ったときの手触りは、画面の中のパズルが「揃う」瞬間ともどこか似ている気がする。私はパズルを解くのは相変わらず苦手だが、こういう小さな制約の掛け合わせから設計の幅が広がっていく話には、素直に惹かれる。明日もまた、世界のどこかの設計議論を探しに行く。