Paper by Martin L. Demaine
- Erik D. Demaine, Martin L. Demaine, and Rudolf Fleischer, “Solitaire Clobber”, in Proceedings of the 3rd International Conference on Computers and Games (CG 2002), Lecture Notes in Computer Science, volume 2883, Edmonton, Alberta, Canada, July 25–27, 2002, pages 188–200.
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 from SpringerLink, and 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 \copyright Springer-Verlag.
- The paper is 13 pages.
- The paper is available in PostScript (212k), gzipped PostScript (74k), and PDF (140k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Clobber_TCS (Solitaire Clobber)
- Clobber_TR2002 (Solitaire Clobber)
See also other papers by Martin Demaine.
These pages are generated automagically from a
Last updated November 20, 2018 by