電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2019-12-13 17:25
アンチスライドパズルの解析
木村健斗天野一幸荒木徹也群馬大COMP2019-43
抄録 (和) $n$を正整数とする.
$ntimes ntimes n$の箱と指定されたある形のピースが与えられたとき,
同じ形のピースを箱に詰め,
全てのピースがどんな方向にも動かないように詰め方を求める問題を考える.
この問題は最少のピース数で実現できる詰め方を見つけることが目標となっている.
このような問題をアンチスライドパズルと呼ぶ.
%天野ら(JIP'15, Article No. 3)がこの問題を整数計画問題として定式化している.
%その後,
木村と天野(組合せゲーム・パズル第14回)はピースの形によって最少のピース数が$Theta(n^3), Theta(n^2), Theta(n)$に分類されると予想している.
本稿では最少のピース数が$Theta(n^2)$と予想された3種類のピースに対して解析し,
それぞれ$O(n^2)$個のピースからなる一般的な詰め方を与える.
さらに, $ntimes n$の平面とT字型ピースを用いた2次元の問題に対して,$n$が$3$で割り切れるか否かで,
その最適な詰め方が大きく異なる形状となることを明らかにする.より詳細には,
$n$が3の倍数でないとき, 最少のピース数は$2n/3 - O(1)$個であることを示し,また,
$n$が3の倍数であるとき, この値がほぼ$n$個となることの実験結果,および,
このようなギャップが生じる要因を示す命題を与える. 
(英) Let $n$ be a positive integer.
Given an $ntimes ntimes n$ box and a number of pieces of some specified shape,
we consider how to pack the pieces such that none of the pieces in the box can slide in any direction.
The objective of the problem is to find a packing with a minimum number of pieces.
The problem is called the ``anti-slide'' puzzle.
Kimura and Amano (Combinatorial Games and puzzles 14th)
conjectured that the minimum number of pieces contained in such packing is one of $Theta(n^3)$, $Theta(n^2)$ or $Theta(n)$,
depending on the shape of the pieces.
In this paper, we analyze the anti-slide puzzle for three shapes in the second group.
For each of these three shapes, we give
the general structure of an anti-slide packing consisting of $O(n^2)$ pieces.
In addition, we reveal that, for a 2-dimensional $ntimes n$ box and the T-shape pieces,
the size of an optimal packing is quite different depending on $n$ modulo $3$.
キーワード (和) アンチスライドパズル / 下界 / 整数計画ソルバ / / / / /  
(英) anti-slide / lower bound / IP solver / / / / /  
文献情報 信学技報, vol. 119, no. 340, COMP2019-43, pp. 101-107, 2019年12月.
資料番号 COMP2019-43 
発行日 2019-12-06 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2019-43

研究会情報
研究会 COMP  
開催期間 2019-12-13 - 2019-12-13 
開催地(和) 群馬大学 伊香保研修所 
開催地(英) Ikaho Seminar House, Gunma University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2019-12-COMP 
本文の言語 日本語 
タイトル(和) アンチスライドパズルの解析 
サブタイトル(和)  
タイトル(英) The Analysis of Anti-slide 
サブタイトル(英)  
キーワード(1)(和/英) アンチスライドパズル / anti-slide  
キーワード(2)(和/英) 下界 / lower bound  
キーワード(3)(和/英) 整数計画ソルバ / IP solver  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 木村 健斗 / Kento Kimura / キムラ ケント
第1著者 所属(和/英) 群馬大学 (略称: 群馬大)
Gunma University (略称: Gunma Univ.)
第2著者 氏名(和/英/ヨミ) 天野 一幸 / Kazuyuki Amano / アマノ カズユキ
第2著者 所属(和/英) 群馬大学 (略称: 群馬大)
Gunma University (略称: Gunma Univ.)
第3著者 氏名(和/英/ヨミ) 荒木 徹也 / Tetsuya Araki / アラキ テツヤ
第3著者 所属(和/英) 群馬大学 (略称: 群馬大)
Gunma University (略称: Gunma Univ.)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2019-12-13 17:25:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2019-43 
巻番号(vol) IEICE-119 
号番号(no) no.340 
ページ範囲 pp.101-107 
ページ数 IEICE-7 
発行日 IEICE-COMP-2019-12-06 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会