Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, and Rudolf Fleischer, “Solitaire Clobber”, Theoretical Computer Science, volume 313, number 3, February 2004, pages 325–338. Special issue of selected papers presented at the Schloss Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, 2002.

BibTeX

@Article{Clobber_TCS,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer},
  TITLE         = {Solitaire Clobber},
  JOURNAL       = {Theoretical Computer Science},
  journalurl    = {https://www.journals.elsevier.com/theoretical-computer-science},
  VOLUME        = 313,
  NUMBER        = 3,
  MONTH         = {February},
  YEAR          = 2004,
  PAGES         = {325--338},
  NOTE          = {Special issue of selected papers presented at the
                   Schloss Dagstuhl Seminar on Algorithmic Combinatorial
                   Game Theory, 2002.},

  length        = {15 pages},
  papers        = {Clobber_CGames2002; Clobber_TR2002},
  replaces      = {Clobber_CGames2002},
  doi           = {https://dx.doi.org/10.1016/J.TCS.2003.02.001},
  dblp          = {https://dblp.org/rec/journals/tcs/DemaineDF04},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1016/j.tcs.2003.02.001">ScienceDirect</A>, and as <A HREF="https://arXiv.org/abs/cs/0204017">arXiv:cs/0204017</A>.},
  updates       = {Ivars Peterson wrote an article describing these results,
                   &ldquo;<A HREF="http://www.sciencenews.org/20020427/mathtrek.asp">Getting
                   Clobbered</A>&rdquo;,
                   <I><A HREF="http://www.sciencenews.org/">Science
                   News</A></I> 161(17), April 27, 2002.},
}

Abstract:

Clobber is a new two-player board game. In this paper, we introduce the one-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 two 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. We also show that 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 from ScienceDirect, and as arXiv:cs/0204017.

Updates:

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

Length:

The paper is 15 pages.

Availability:

The paper is available in PostScript (336k), gzipped PostScript (134k), and PDF (157k).

See information on file formats.

[Google Scholar search]

Related papers:

Clobber_CGames2002 (Solitaire Clobber)

Clobber_TR2002 (Solitaire Clobber)