-
- Suzuki Akira
- Graduate School of Information Sciences, Tohoku University CREST, JST
-
- Kiyomi Masashi
- International College of Arts and Sciences, Yokohama City University
-
- Otachi Yota
- School of Information Science, Japan Advanced Institute of Science and Technology
-
- Uchizawa Kei
- Graduate School of Science and Engineering, Yamagata University
-
- Uno Takeaki
- National Institute of Informatics
この論文をさがす
抄録
<p>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.</p>
収録刊行物
-
- Journal of Information Processing
-
Journal of Information Processing 25 (0), 695-707, 2017
一般社団法人 情報処理学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282680270834560
-
- NII論文ID
- 130005990920
- 170000148847
-
- NII書誌ID
- AN00116647
-
- ISSN
- 18827764
- 18826652
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可