Paper by Martin L. 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 Martin Demaine.
These pages are generated automagically from a
Last updated November 20, 2018 by