組合せゲーム・パズル ミニプロジェクト [HP]

第9回ミニ研究集会

[日時・場所] [位置付け等] [プログラム] [各講演の概要と発表資料]

日時  2014年2月28日(金) 9:30〜17:30

 

場所  北陸先端科学技術大学院大学 I3-I4講義室 [地図]

宿泊について

 

位置付け等

プログラム


(1) 09:30 -- 09:50
ヒントの少ないナンプレの作り方
早川友康(タイムインターメディア)

(2) 09:50 --10:10
正多面体の展開図のパッキング問題について
○堀山貴史, 古岡泰成 (埼玉大)

休憩 20分

(3) 10:30 -- 10:50
ペンシルパズルの大道芸ステージショーへの応用
baLLjugglermoka(フリーパズル研究家兼ジャグラー)

(4) 10:50 -- 11:10
穴を許した一般化フィルマットのASP完全性
○鈴木裕章,上嶋章宏(大阪電通大)

休憩 20分

(5) 11:30 --11:50
HIDATOの整数計画モデル
永井杏奈,宇野裕之(大阪府立大学)

(6) 11:50 -- 12:10
あみだくじを数え上げる省領域アルゴリズムについて
○中嶋章裕,斎藤寿樹,山口一章,増田澄男(神戸大)

昼食休憩 80分

(7) 13:30-13:50
The Computational Complexity of the Game of SET and its Theoretical Applications
Michael Lampis(京大),○Valia Mitsou(CUNY)

(8) 13:50 -- 14:10
色数と盤面の幅を限定したぷよぷよの必勝性
○島田陽,武永康彦(電通大)

休憩 20分

(9) 14:30 -- 14:50
異なる手の間に引分けのある一般化ジャンケンにおける引分け数と不敗手数
○伊藤大雄,塩野芳直(電通大)

(10) 14:50 --15:10
三角取りの多項式時間解法とNP完全性の研究
堀山貴史(埼玉大),清見礼(横浜市立大),岡本吉央(電通大),◯上原隆平(JAIST),宇野毅明(NII),宇野裕之(大阪府立大),山内由紀子(九州大)

(11) 15:10 --15:25
魔方陣に関する未解決問題
宇野裕之(大阪府立大学)

---

16:00 -- 17:30
JAISTギャラリー パズルコレクション 見学

 

各講演の概要と発表資料

1. ヒントの少ないナンプレの作り方:早川友康(タイムインターメディア)

16x16のヒント数56のナンプレと
25x25のヒント数153のナンプレを生成した。
これらのナンプレの作り方について報告する。[発表資料(pdf)]

2. 正多面体の展開図のパッキング問題について:○堀山貴史, 古岡泰成 (埼玉大)

立方体の11種類の展開図を、7x11 の長方形の盤面に、
重なりなく詰め込むパズルは、箱詰めパズルの一種である。
また、小田原充宏により、正八面体の11種類の展開図を
詰め込むパズルとして、解が一意に定まる (対称解を合わせて
2通りしか解のない) 盤面が公表されている。本発表では、
ZDD (Zero-suppressed Binary Decision Diagram) を用いて、
これらのパッキング問題の解を列挙するアルゴリズムを提案する。
また、上記の2つを含めた様々な盤面について、計算機実験の
結果を示す。

3. ペンシルパズルの大道芸ステージショーへの応用:baLLjugglermoka(フリーパズル研究家兼ジャグラー)

大道芸ステージでは、ジャグリング、マジック、アクロバット等、物理的な動きを観せています。
逆に、物理的な動きがない種目の例として、ペンシルパズルがあります。
本講演では、物理的動きのないものを演技構成に組み込むための手法の一つとして、
ペンシルパズルの大道芸ステージの演技構成への組み込み方法について報告します。[発表資料(pptx)]

4. 穴を許した一般化フィルマットのASP完全性:○鈴木裕章,上嶋章宏(大阪電通大)

 本研究では,ペンシルパズル“フィルマット”の計算複雑さを解析する.
このパズルは,四角格子の盤面に対し所定のルールに従い境界線を引くこ
とで,盤面をいくつかの畳に分割するものである.畳の大きさは幅1マスx
長さ1〜4マスに限定されている.
 盤面には数字の書かれたマスがいくつか存在する.数字の書かれたマス
は数字分の大きさの畳で覆われなければならず,数字の書かれたマスを
複数覆う畳はあってはならない.また,同じ大きさの畳が隣接しないこと,
境界線を十字に引けないこと,という条件がある.通常は盤面の全てのマ
スを畳で覆わなければならない.
 本研究では,どの畳にも覆われないマス(穴)の存在を許容し,穴の
位置が予め与えられた入力盤面でのフィルマットの別解問題(ASP)の計算
複雑さを議論する.この問題がASP完全であるか否かは未解決である.
本発表では,穴を許したフィルマットのASP完全性を,Circuit-SATからの
多項式時間一対一還元により証明する.

5. HIDATOの整数計画モデル:永井杏奈,宇野裕之(大阪府立大学)

ペンシルパズルHIDATOについて,その解を表現する整数計画モデルを提案する.
その上で,そのモデルにおける定式化を数理計画ソルバを用いて解き考察を行う.

6. あみだくじを数え上げる省領域アルゴリズムについて:○中嶋章裕,斎藤寿樹,山口一章,増田澄男(神戸大)

近年,あみだくじ数え上げ問題が盛んに研究されており,現在,縦線の数が15本の場合まで知られている.
しかし,従来法は大量のメモリを消費する ため,現代の計算機では縦線の数が16本以上の場合を数え上げ
るのは困難である.そこで,本研究では従来法を基礎とし,様々な計算機環境を想定し てあみだくじを数
え上げる,省領域のアルゴリズムを提案する.提案法では,決定グラフの一種である多値決定グラフ(MDD)
を分割構築すること で,様々な計算機環境でも対応可能なメモリ量で実行できるようにした.本発表では
提案法として,あみだくじ数え上げの省領域アルゴリズムの紹介と 解析結果,今後の展開や方針について
述べる.[発表資料(pptx)]

7. The Computational Complexity of the Game of SET and its Theoretical Applications:Michael Lampis(京大),○Valia Mitsou(CUNY)

The game of SET is a popular card game in which the objective is to form Sets using cards from a special deck.
In this talk we analyse single- and multi-round variations of this game from the computational complexity point
of view and establish interesting connections with other classical computational problems, such as Perfect
Multi-Dimensional Matching, 3-Set Packing, and Independent Edge Dominating Set. Finally we present a 2-player
version of the game, for which we show a close connection to the game Arc Kayles.[発表資料(pdf)]

8. 色数と盤面の幅を限定したぷよぷよの必勝性:○島田陽,武永康彦(電通大)

落ち物パズルゲームは、パズルのブロックが次々とゲームの盤面に落ちていき、
プレイヤーがブロックを操作して、適当な場所に落としていくパズルゲームであ
る。本研究では、ぷよぷよという落ち物パズルゲームについて、ぷよの色数や盤
面の幅を変化させた場合の必勝性について研究を行った。プレイヤーが上手くぷ
よを消滅させられなければ、ぷよはどんどん積み上がっていき、ある一定の高さ
に達した時点でゲームオーバーとなってしまう。本研究では、一人用のぷよぷよ
について、どのような入力列に対しても一定の高さ以下で永遠にプレイできると
き必勝であるとした。そして、出現するぷよの色数を定めた場合、盤面の幅がい
くつあれば必勝であるかを考察した。また、盤面の幅に対して、最悪のケースに
おいてプレイヤーが無限にぷよを積み上げてしまうには、何色のぷよが出現すれ
ば十分かを考察した。

9. 異なる手の間に引分けのある一般化ジャンケンにおける引分け数と不敗手数:○伊藤大雄,塩野芳直(電通大)

3手のジャンケンをn手に一般化したジャンケンの性質を考察する。
ジャンケンにおいて、ある手xの代わりに出して不利になる事の無い手yのことを、
xに「優越する」手と呼び、それに優越する手が存在する手を「無駄な」手と呼ぶ。
無駄な手の無いジャンケンを「効率的な」ジャンケンと呼ぶ。
効率的なジャンケンについては伊藤によって2010年にいくつか性質が明らかに
なっているが、今回は異なる手の間に引分けがあるジャンケンについて考察した。
(世界には異なる手の間に引分けが定義されている5手のジャンケンも存在する。)
 本研究では、効率的なn手のジャンケンにおいて引分け対の最大数は (nC2)-n+1
であることを証明した。さらに、引分けが存在する場合には、どの手にも負けない手
(不敗手)が存在しうる。そこで不敗手がどこまで多くなりうるかを考察した。その結果、
不敗手以外の手の数がo(n)となる(つまりほとんど全てが不敗手となる)ような
効率的なn手のジャンケンが存在することを示した。

10. 三角取りの多項式時間解法とNP完全性の研究:堀山貴史(埼玉大),清見礼(横浜市立大),岡本吉央(電通大),◯上原隆平(JAIST),宇野毅明(NII),宇野裕之(大阪府立大),山内由紀子(九州大)

主に関西地区で遊ばれている古い遊びに「三角取り」と呼ばれているものが
ある.これは二人ゲームで,dots-and-boxes に少し似ている.
まずはじめに,一般の位置にある点集合が与えられ,プレイヤーは交互に
線分を引いて三角形分割を構成する.ある三角形は,最後の一辺を
引いたプレイヤーのものとなる.より多くの三角形を作った方が勝つ.
本発表では,このゲームの二つの特別なケースを考える.
まず点集合が凸配置であった場合,先手必勝であることを示す.
これは実際に非自明な必勝手順を示すことで証明する.
次にある程度ゲームが進んだ盤面から始めた一人ゲーム版を考えて,
これがNP完全であることを示す.[発表資料(pptx)]

11. 魔方陣に関する未解決問題:宇野裕之(大阪府立大学)

世界的によく知られて人気がある魔方陣には,まだ多くの未解決問題が存在する.
それらのいくつかを紹介する.

世話役 伊藤大雄、岡本吉央(電気通信大学)