Paper by Erik D. Demaine

Reference:
Erik D. Demaine, Martin L. Demaine, and Rudolf Fleischer, “Solitaire Clobber”, Technical Report HKUST-TCSC-2002-05, Hong Kong University of Science and Technology, April 2002.

Abstract:
Clobber is a new two-player board game. In this paper, we introduce the 1-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white and black moves. We show that a checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones. For boards with at least two rows and columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones. But in general it is NP-complete to decide whether an arbitrary Clobber configuration can be reduced to a single stone.

Comments:
This paper is also available as arXiv:cs.DM/0204017 of the Computing Research Repository (CoRR).

Updates:
Ivars Peterson wrote an article describing these results, “Getting Clobbered”, Science News 161(17), April 27, 2002.

Length:
The paper is 14 pages.

Availability:
The paper is available in PostScript (228k) and gzipped PostScript (81k).
See information on file formats.
[Google Scholar search]

Related papers:
Clobber_TCS (Solitaire Clobber)
Clobber_CGames2002 (Solitaire Clobber)


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 25, 2017 by Erik Demaine.