Paper by Erik D. Demaine

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.

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.

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

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

The paper is 14 pages.

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 23, 2024 by Erik Demaine.