Hitori Numbers

• Item type: Journal(1)
• 公開日: 2017-08-15
• タイトル: Hitori Numbers
• タイトル / 言語: en
• タイトル: Hitori Numbers
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：離散と計算の幾何・グラフ・ゲーム] Hitori, pencil-and-paper puzzle, unique solution
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Information Sciences, Tohoku University／CREST, JST
• 著者所属: International College of Arts and Sciences, Yokohama City University
• 著者所属: School of Information Science, Japan Advanced Institute of Science and Technology
• 著者所属: Graduate School of Science and Engineering, Yamagata University
• 著者所属: National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University / CREST, JST
• 著者所属(英): en
• 著者所属(英): International College of Arts and Sciences, Yokohama City University
• 著者所属(英): en
• 著者所属(英): School of Information Science, Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Yamagata University
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者名: Akira, Suzuki; Masashi, Kiyomi; Yota, Otachi; Kei, Uchizawa; Takeaki, Uno
• 著者名(英): Akira, Suzuki; Masashi, Kiyomi; Yota, Otachi; Kei, Uchizawa; Takeaki, Uno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Hitori is a popular “pencil-and-paper” puzzle defined as follows. In n-hitori, we are given an n × n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label; Rule 2) Painted squares are never (horizontally or vertically) adjacent; Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori numberwhich are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number $\bar{h}(n)$ is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⎾(2n-1)/3⏋ ≤ h(n) ≤ 2⎾n/3⏋+1 for n ≥ 2 and ⎾(4n2-4n+11)/5⏋ ≤ $\bar{h}(n)$ ≤ (4n2+2n-2)/5 for n ≥ 3.; ------------------------------; 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.25(2017) (online); DOI http://dx.doi.org/10.2197/ipsjjip.25.695; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Hitori is a popular “pencil-and-paper” puzzle defined as follows. In n-hitori, we are given an n × n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label; Rule 2) Painted squares are never (horizontally or vertically) adjacent; Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori numberwhich are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number $\bar{h}(n)$ is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⎾(2n-1)/3⏋ ≤ h(n) ≤ 2⎾n/3⏋+1 for n ≥ 2 and ⎾(4n2-4n+11)/5⏋ ≤ $\bar{h}(n)$ ≤ (4n2+2n-2)/5 for n ≥ 3.; ------------------------------; 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.25(2017) (online); DOI http://dx.doi.org/10.2197/ipsjjip.25.695; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 58, 号 8, 発行日 2017-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764