Paper by Erik D. 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.

BibTeX

@TechReport{Clobber_TR2002,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer},
  TITLE         = {Solitaire Clobber},
  NUMBER        = {HKUST-TCSC-2002-05},
  NUMBERURL     = {http://www.cs.ust.hk/tcsc/RR/2002-05.ps.gz},
  INSTITUTION   = {Hong Kong University of Science and Technology},
  MONTH         = {April},
  YEAR          = 2002,

  LENGTH        = {14 pages},
  PAPERS        = {Clobber_TCS; Clobber_CGames2002},
  COMMENTS      = {This paper is also available as
                   <A HREF="http://arXiv.org/abs/cs.DM/0204017">
                   arXiv:cs.DM/0204017</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>, and from <A HREF="https://doi.org/10.1007/978-3-540-40031-8_13">SpringerLink</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 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), and from SpringerLink.

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)