Linear time algorithms for Clobber

Details Linear time algorithms for Clobber Linear time algorithms for Clobber

2007-03-12

arxiv.org/abs/cs/0703054v1

Computer Science

Computer Science and Game Theory

Scientific paper

We prove that the single-player game clobber is solvable in linear time when played on a line or on a cycle. For this purpose, we show that this game is equivalent to an optimization problem on a set of words defined by seven classes of forbidden patterns. We also prove that, playing on the cycle, it is always possible to remove at least 2n/3 pawns, and we give a conformation for which it is not possible to do better, answering questions recently asked by Faria et al.

Affiliated with

Also associated with

No associations

Rating

Linear time algorithms for Clobber does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear time algorithms for Clobber, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear time algorithms for Clobber will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285734