Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno, “Computational complexity and an integer programming model of Shakashaka”, in Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, to appear.

BibTeX

@InProceedings{Shakashaka_CCCG2013,
  AUTHOR        = {Erik D. Demaine and Yoshio Okamoto and Ryuhei Uehara and Yushi Uno},
  TITLE         = {Computational complexity and an integer programming model of {Shakashaka}},
  BOOKTITLE     = {Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)},
  bookurl       = {https://cs.uwaterloo.ca/conferences/cccg2013/},
  ADDRESS       = {Waterloo, Ontario, Canada},
  MONTH         = {August 8--10},
  YEAR          = 2013,
  PAGES         = {to appear},

  length        = {6 pages},
  unrefereed    = 1,
  papers        = {Shakashaka_IEICE},
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineOUU13},
  ee            = {https://cccg.ca/proceedings/2013/papers/paper_7.pdf},
}

Abstract:

Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions if #P-complete. Next we formulate Shakashaka as an integer programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.

Length:

The paper is 6 pages.

Availability:

The paper is available in PostScript (1167k), gzipped PostScript (406k), and PDF (344k).

See information on file formats.

[Google Scholar search]

Related papers:

Shakashaka_IEICE (Computational complexity and an integer programming model of Shakashaka)