A Tale of Two Puzzles: Towers of Hanoi and Spin-Out

• Item type: Journal(1)
• 公開日: 2013-05-15
• タイトル: A Tale of Two Puzzles: Towers of Hanoi and Spin-Out
• タイトル / 言語: en
• タイトル: A Tale of Two Puzzles: Towers of Hanoi and Spin-Out
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：パズルの数理] puzzles, graphs, algorithms, Towers of Hanoi, Spin-Out, iterated complete graphs
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Computer Science, Kelley Engineering Center, Oregon State University
• 著者所属: Department of Mathematics, University of Oregon
• 著者所属: Computer Science, Kelley Engineering Center, Oregon State University
• 著者所属(英): en
• 著者所属(英): Computer Science, Kelley Engineering Center, Oregon State University
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, University of Oregon
• 著者所属(英): en
• 著者所属(英): Computer Science, Kelley Engineering Center, Oregon State University
• 著者名: Paul, Cull; Leanne, Merrill; Tony, Van
• 著者名(英): Paul, Cull; Leanne, Merrill; Tony, Van
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Once upon a time, there were two puzzles. One was the Towers of Hanoi invented or introduced by Eduardo Lucas in 1883. The other was Spin-Out patented by William Keister in 1972. There are many stories about these puzzles. Some of these stories hint or claim that these puzzles have an intimate relationship with the Gray codes invented by Frank Gray in 1947. Here, we wish to show how these puzzles can be generalized and crossed to give puzzles for every base and for every number of pieces. The Gray relationship will become clearer when we describe the graphs associated with the puzzles and the graph labelings induced by the puzzles. These labelings will have the Gray property in the appropriate base. Counter to claims that Gray counting is needed to solve these puzzles, we describe counting algorithms which solve these puzzles using a standard binary counter. We also give recursive and iterative algorithms for these puzzles.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.21(2013) No.3 (online); DOI http://dx.doi.org/10.2197/ipsjjip.21.378; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Once upon a time, there were two puzzles. One was the Towers of Hanoi invented or introduced by Eduardo Lucas in 1883. The other was Spin-Out patented by William Keister in 1972. There are many stories about these puzzles. Some of these stories hint or claim that these puzzles have an intimate relationship with the Gray codes invented by Frank Gray in 1947. Here, we wish to show how these puzzles can be generalized and crossed to give puzzles for every base and for every number of pieces. The Gray relationship will become clearer when we describe the graphs associated with the puzzles and the graph labelings induced by the puzzles. These labelings will have the Gray property in the appropriate base. Counter to claims that Gray counting is needed to solve these puzzles, we describe counting algorithms which solve these puzzles using a standard binary counter. We also give recursive and iterative algorithms for these puzzles.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.21(2013) No.3 (online); DOI http://dx.doi.org/10.2197/ipsjjip.21.378; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 54, 号 5, 発行日 2013-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764