Sankaku-tori: An old Western-japanese game played on a point set

Takashi Horiyama, Takashi Iizuka, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi

研究成果: ジャーナルへの寄稿学術誌査読

1 被引用数 (Scopus)


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.

ジャーナルJournal of information processing
出版ステータス出版済み - 8月 2017

!!!All Science Journal Classification (ASJC) codes

  • コンピュータ サイエンス(全般)


「Sankaku-tori: An old Western-japanese game played on a point set」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。