清見 礼

We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant; for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one; we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.708------------------------------We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant; for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one; we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.708------------------------------

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 ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.695------------------------------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 ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.695------------------------------

The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.