DS-1-5 ひとりにしてくれ数(DS-1.COMP学生シンポジウム,シンポジウムセッション)

概要

論文の詳細を見る
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 an 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/31+1.
一般社団法人電子情報通信学会の論文
2012-03-06