WEKO3
-
RootNode
アイテム
Hoffmanパズル解の列挙と一般化に関する研究
https://ipsj.ixsq.nii.ac.jp/records/72921
https://ipsj.ixsq.nii.ac.jp/records/729215e3412f3-ff54-4f66-ab73-16b418cac917
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2011-02-28 | |||||||
タイトル | ||||||||
タイトル | Hoffmanパズル解の列挙と一般化に関する研究 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | On the Hoffman Puzzle and its generalization | |||||||
言語 | ||||||||
言語 | eng | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
北陸先端科学技術大学院大学 | ||||||||
著者所属 | ||||||||
北陸先端科学技術大学院大学 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Japan Advanced Institute of Science and Technology | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Japan Advanced Institute of Science and Technology | ||||||||
著者名 |
後藤, 新
上原, 隆平
× 後藤, 新 上原, 隆平
|
|||||||
著者名(英) |
Arata, Goto
Ryuhei, Uehara
× Arata, Goto Ryuhei, Uehara
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 大きさ (a + b + c)×(a + b + c)×(a + b + c) の箱に大きさ a×b×c の直方体のブロックを27個詰め込むパズルは Hoffman パズルと呼ばれている.これは D. G. Hoffman が 1978 年に提案したパズルで,非常に難しいパズルとして知られていて,21 通りの解を持つことがわかっている.ホフマンパズルでは辺の長さに (a + b + c)/4 < a < b < c という条件をおいている.2004 年に D. E. Knuth はこの条件を緩めて (a + b + c)/4 = a < b < c とし,(a,b,c) = (3,4,5) のとき,28 個目のブロックが入ることを示した.しかしその詳細はよくわかっていない.本研究では Knuth の拡張したパズルを解析し,28 個目のブロックが入るための条件を明らかにした.また 28 個目のピースが入る場合のすべての解を示した.さらに 29 個以上は入らないことを証明した. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | The packing problem of 27 blocks of size a×b×c into a box of size (a + b + c)×(a + b + c)×(a + b + c)is called the Hoffman puzzle. This puzzle was proposed by D. G. Hoffman in 1978, and it is well known as a “difficult” puzzle that has 21 solutions. In the Hoffman puzzle, the lengths should satisfy the condition (a + b + c)/4 < a < b < c. In 2004, D. E. Knuth loosened the condition to (a + b + c)/4 = a < b < c, and showed that we can pack the 28th block in the case (a; b; c) = (3; 4; 5). However, more details are not known. In this paper, we analyze this extended Hoffman-Knuth puzzle, and investigate the condition that the 28th block can be packed. We also show all solutions of this puzzle, and prove that we cannot pack the 29th block. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
研究報告アルゴリズム(AL) 巻 2011-AL-134, 号 18, p. 1-4, 発行日 2011-02-28 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |