TY - GEN
T1 - Hitori number
AU - Suzuki, Akira
AU - Uchizawa, Kei
AU - Uno, Takeaki
PY - 2012
Y1 - 2012
N2 - Hitori is a popular "pencil-and-paper" puzzle game. In n-hitori, we are given an n ×n rectangular grid of 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 hold: 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 defined as follows: For every integer n≥2, 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. We then prove that ⌈(2n-1)/3⌉ ≤ h(n)≤2⌈n/ 3⌉+1.
AB - Hitori is a popular "pencil-and-paper" puzzle game. In n-hitori, we are given an n ×n rectangular grid of 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 hold: 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 defined as follows: For every integer n≥2, 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. We then prove that ⌈(2n-1)/3⌉ ≤ h(n)≤2⌈n/ 3⌉+1.
UR - http://www.scopus.com/inward/record.url?scp=84861964920&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861964920&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-30347-0_33
DO - 10.1007/978-3-642-30347-0_33
M3 - Conference contribution
AN - SCOPUS:84861964920
SN - 9783642303463
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 334
EP - 345
BT - Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings
T2 - 6th International Conference on Fun with Algorithms, FUN 2012
Y2 - 4 June 2012 through 6 June 2012
ER -