Paper by Martin L. 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)