Paper by Erik D. Demaine

Reference:

Aviv Adler, Michael Biro, Erik Demaine, Mikhail Rudoy, and Christiane Schmidt, “Computational complexity of numberless Shakashaka”, in Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), Kingston, Ontario, Canada, August 10–12, 2015.

BibTeX

@InProceedings{NumberlessShakashaka_CCCG2015,
  AUTHOR        = {Aviv Adler and Michael Biro and Erik Demaine and Mikhail Rudoy and Christiane Schmidt},
  TITLE         = {Computational complexity of numberless {Shakashaka}},
  BOOKTITLE     = {Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015)},
  bookurl       = {http://research.cs.queensu.ca/cccg2015/},
  ADDRESS       = {Kingston, Ontario, Canada},
  MONTH         = {August 10--12},
  YEAR          = 2015,

  withstudent   = 1,
  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/AdlerBDRS15},
  ee            = {http://research.cs.queensu.ca/cccg2015/CCCG15-papers/19.pdf},
}

Abstract:

Shakashaka, like Sudoku, is a pencil-and-paper puzzle. In this paper we show that Shakashaka is NP-complete in the case of numberless black squares.

Availability:

The paper is available in PDF (2760k).

See information on file formats.

[Google Scholar search]