(1) 10:20-10:45
シャカシャカと整数計画法
岡本吉央 (電通大)(2) 10:45-11:10
シャカシャカはNP完全
エリック・ドメイン (MIT)，上原隆平 (JAIST)，宇野裕之 (大阪府立大)(3) 11:10-11:35
ペンシルパズル「一本線」のヒント数の扱いに関する解析
村岡真澄 (フリーパズル研究家兼ジャグラー)(4) 11:35-12:00
商用パズルの作成支援および自動生成：四角に切れ、橋をかけろ
藤原博文 ((株)タイムインターメディア 知識工学センター)---
昼食休憩 90分
---(5) 13:30-13:55
ペンローズタイリング上をとぶグライダー
塚本靖之 (京大)(6) 13:55-14:20
単貧民と偶然手番感度
西野順二，西野哲朗 (電通大)(7) 14:20-14:45
接待をする麻雀クライアントの開発とその評価
安西諒祐, 大西建輔 (東海大)---
休憩 15分
---(8) 15:00-15:25
一般化川渡り問題の多項式時間可解性
伊藤大雄 (電通大)，Stefan Langerman (ULB)，吉田悠一 (NII)(9) 15:25-15:50
Morpion Solitaire： 最大手数の新しい上界
岡本拓馬，辰雄一，大和雅英 (大阪府立大)，河村彰星 (東大)，宇野裕之 (大阪府立大)(10) 15:50-16:15
タントリックスの解の列挙について
萩原優樹，堀山貴史 (埼玉大)，宇野裕之 (大阪府立大)---
休憩 15分
---(11) 16:30-16:55
タントリックス： 計算機による人間の記録への挑戦
辰雄一，岡本拓馬，永井杏奈，宇野裕之 (大阪府立大)，堀山貴史 (埼玉大)(12) 16:55-17:20
タイルの形状を2種に制限したTantrix MatchのNP完全性
柳谷不比等，小林嗣東，上嶋章宏 (大阪電通大)(13) 17:20-17:45
非隣接性を有する組合せパズルの計算複雑さ
浅野竜男，上嶋章宏 (大阪電通大)---
[懇親会]
会場・時間は後日発表します。
会場予約の都合上、懇親会の参加には事前登録が必要です。ご協力をお願いします。->[登録ページ]（２月２１日〆切）
シャカシャカは『パズル通信ニコリ』2008年夏号で
初登場した，Guten氏によって考案されたペンシル
パズルである．本発表ではシャカシャカを整数計画
問題として定式化して，実際に解いてみる．その
結果，非商用ソルバーでも大きなサイズの問題を
簡単に解けることが分かった．[発表資料(pdf)]2. シャカシャカはNP完全：エリック・ドメイン (MIT)，上原隆平 (JAIST)，宇野裕之 (大阪府立大)
シャカシャカは，パズル製作会社ニコリにより比較的最近考案された
新しいペンシルパズルである．他の多くのペンシルパズルと同様，
シャカシャカがNP完全であることを示す．[発表資料(pdf)]3. ペンシルパズル「一本線」のヒント数の扱いに関する解析：村岡真澄 (フリーパズル研究家兼ジャグラー)
一本線はbaLLjugglermoka（自分）によって考案され、パズル通信ニコリ137号で
登場したニコリオリジナルペンシルパズルである。今回の発表では一本線のヒント
数と解のユニーク性の関係について簡単な例を幾つか紹介する。 [発表資料(pptx)]4. 商用パズルの作成支援および自動生成：四角に切れ、橋をかけろ：藤原博文 ((株)タイムインターメディア 知識工学センター)
従来、パズル作家が手作りしていたパズルの問題を、コンピュータでの作成支援から
自動生成までの研究を行い、書籍・雑誌・携帯などに提供してきました。
ナンプレ（数独）は既に手作り以上のレベルに達していますが、今回は説明を略し、
現在開発中の、ナンバーエリア（四角に切れ）とBridges（橋をかけろ）の解説とデモを
行います。
ナンバーエリア（四角に切れ）は、問題作成支援システムですが、対話的に解いたとß
きの状況を表示し、問題の対話的変更を支援します。ソルバーは、与えられた数字(ペグ)
と、マスと、複数マスの塊(島)の管理を行うことだけで実現しています。また、商用利用
のため、多くの問題をバランス良く作るための支援機能もあります。
Bridges（橋をかけろ）のソルバーは、連結グラフの総次数は２の倍数になることを
手筋化することだけでほぼできています。自動生成は、連結グラフの自動生成と、単一
解にする部分に分かれています。
A1サイズの「合体ナンプレ」と「四角に切れ」の展示も行います。
[発表資料(pdf), 付属資料-NA(pdf), 付属資料-BR(pdf)]5. ペンローズタイリング上をとぶグライダー：塚本靖之 (京大)
2種類の菱形によるペンローズタイリング上の状態数3のセルオートマトンで、グライダーが存在するものを構成する。
またこれを元に、状態数4のセルオートマトンで計算万能性を持つものを構成する。
計算万能性の証明において、タイリングの性質上、信号の同期が問題となる。
グライダー銃、レセプターなどを配置し、その問題を解決して論理ゲートを作る手法を紹介したい。
単貧民は大貧民のルールを１枚出しのみに縮小したゲームであり、多人数不完全情報ゲームの一種である。
このとき未知情報の相手の配布状態を推定することは、最良着手の決定に重要と思われるが、実際には関係が弱い
ことがわかっている。この未知情報への探索結果の依存性の度合いを偶然手番感度と呼び数値的に定義した。
比較的小枚数の単貧民について全探索を行ない、実験的に偶然手番感度を計った結果について報告する。[発表資料(ppt)]7. 接待をする麻雀クライアントの開発とその評価：安西諒祐, 大西建輔 (東海大)
麻雀は, 老若男女だれでも楽しく遊べる遊戯として, 愛好されている.
そのため, 様々なプログラムが作成され, ネット上での対戦ができる
場もある. 最近では, UCT探索を用いたクライアントやSVMを用いた評
価値の研究などもおこなわれている. これらの研究目的は, 強いクラ
イアントを作成することである.一方, ゲームでは, 必ずしも強いクライアントだけが必要となるわけ
ではない. 時には個性的なクライアントも必要となる. 例えば麻雀で
は、特定の役を目指すものや鳴きつづけるものなどもあると, ゲーム
としての楽しさが増す.本研究では, 他のプレイヤを接待をする, つまり特定のプレイヤに対
して, 有利となるような牌を捨てる支援クライアントの作成をおこな
った. このクライアントは, 常に支援する牌を捨てるだけなく, 時と
しては自ら上がることもある. このクライアントがどの程度, 支援を
することができたのか, 支援クライアントであるかを見破られるかの
実験をおこない, 評価をおこなった. [発表資料(pdf)]8. 一般化川渡り問題の多項式時間可解性：伊藤大雄 (電通大)，Stefan Langerman (ULB)，吉田悠一 (NII)
昨年度の本研究会で一般化川渡り問題の定式化法を発表したが
そので述べた予想である「この定式化の下で広いクラスの部分問題が
多項式で解ける」ことを肯定的に解いたので報告する。[発表資料(pdf)]9. Morpion Solitaire： 最大手数の新しい上界：岡本拓馬，辰雄一，大和雅英 (大阪府立大)，河村彰星 (東大)，宇野裕之 (大阪府立大)
Morpion Solitaire は古典的な数理パズルである．パズルの目的はプレイ可能な
最大手数を競うもので，そのルールによりいくつかの変種が存在する．
本研究では，その一つの変種における最大手数の上界値を見積もる新しい手法を提案し，
あわせて新しい上界値を示す．10. タントリックスの解の列挙について：萩原優樹，堀山貴史 (埼玉大)，宇野裕之 (大阪府立大)
タントリックスは、10種類の六角形のタイルを用いるパズルである。
各タイルには、赤・青・黄の３本の線が描かれており、この線のい
ずれかにより六角形の各辺は他の辺と結ばれている。また、タイル
には、1〜10のタイル番号が順に番号付けられていると共に、赤・
青・黄のいずれかのタイル指定色が関連付けられている。整数 n が
チャレンジ番号として与えられると、タイル番号 i のタイルを
(n - i)/10 + 1 (小数以下切り捨て) 枚だけ用いる。パズルの解は、
以下の制約を満たす必要がある。(1) n mod 10 で指定されるタイル
の指定色で、n 枚からなるループができていること。(2) タイルの
辺同士が接する場合には、線の色が同じであること。本講演では、
ZDD (Zero-Suppressed Binary Decision Diagram) を用いて、タント
リックスの解を列挙する取り組みについて報告する。11. タントリックス： 計算機による人間の記録への挑戦：辰雄一，岡本拓馬，永井杏奈，宇野裕之 (大阪府立大)，堀山貴史 (埼玉大)
タントリックス（ディスカバリー）は，3色三本のラインが描かれた六角形のタイルを
規則的に並べて，特定の1色で一本のループをつくるパズルで，できるだけ長い
ループを作ることを目的とする．このパズルに対して，既存の研究では計算機による
求解は人間の記録に及ばない．本研究では計算機による新たな解法を提案し，
人間の記録に挑戦する．12. タイルの形状を2種に制限したTantrix MatchのNP完全性：柳谷不比等，小林嗣東，上嶋章宏 (大阪電通大)
Tantrix Matchの計算複雑さを解析する．本パズルは正六角形のタイル
を下記ルールに従い，六角格子の盤面に配置するパズルである．
タイルに描かれる路の組み合わせは4種類あり，各路は4色で色付けさ
れており，路の色付け制限などを考慮した全56種類のタイルを用いる
ことが一般的である．
このタイルが手持ちタイルとして複数枚与えられ，数枚の動かせない
タイルがすでに配置され，手持ちタイルを配置できる場所が定められ
た盤面に対し，隣接するタイルの路が同色になるような全手持ちタイ
ルの配置を目的としたパズルである．通常，終了時にタイルに囲まれ
たタイルの配置されない場所（穴）は存在しない．
本問題の路の組み合わせを制限せず，穴を許し使用するタイルを13種類
に制限した場合のNP完全性が証明されている．一方で，路の組み合わせ
を制限した場合のNP完全性は証明されていない．本発表では，穴を許し
路の組み合わせを2種17枚に制限した. [発表資料(pdf)]13. 非隣接性を有する組合せパズルの計算複雑さ：浅野竜男，上嶋章宏 (大阪電通大)
本研究では，四角格子盤面へのタイル配置型のペンシルパズルに対し，
制約条件としてタイルの非隣接性を持つか否かの分類に注目して，解の
一意性を判定する別解問題の計算複雑さ証明の取り扱い難さについて
議論する．隣接性を有するタイプの「LITS」，非隣接性を有するタイプ
の「のりのり」と「島国」という3つのパズルを題材に，それぞれのNP完
全性およびASP完全性の証明に対する取り組みを発表する．LITSでは2x2
以外の4細胞生物(全4種)を，のりのりでは2細胞生物(全1種)をそれぞれ
タイルとして扱い，島国では固定したタイル形状はなく要求を満たすサ
イズのひと塊の領域を割り当てる．但し，LITSではタイル全体での連結
性が要求され，のりのり・島国ではタイルの非隣接性を満たさなければ
ならない．本発表では，個々の問題のNP完全性について簡素に証明を示
し，タイルの非隣接性の有無に伴う多項式時間一対一還元実現の容易さ
/困難さについての考察を述べる．[発表資料(pdf)]
世話役 伊藤大雄、岡本吉央（電気通信大学）