License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.16
URN: urn:nbn:de:0030-drops-159867
Go to the corresponding LIPIcs Volume Portal

Ito, Takehiro ; Kawahara, Jun ; Minato, Shin-ichi ; Otachi, Yota ; Saitoh, Toshiki ; Suzuki, Akira ; Uehara, Ryuhei ; Uno, Takeaki ; Yamanaka, Katsuhisa ; Yoshinaka, Ryo

Sorting Balls and Water: Equivalence and Computational Complexity

LIPIcs-FUN-2022-16.pdf (0.8 MB)


Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP . We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

BibTeX - Entry

  author =	{Ito, Takehiro and Kawahara, Jun and Minato, Shin-ichi and Otachi, Yota and Saitoh, Toshiki and Suzuki, Akira and Uehara, Ryuhei and Uno, Takeaki and Yamanaka, Katsuhisa and Yoshinaka, Ryo},
  title =	{{Sorting Balls and Water: Equivalence and Computational Complexity}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-159867},
  doi =		{10.4230/LIPIcs.FUN.2022.16},
  annote =	{Keywords: Ball sort puzzle, recreational mathematics, sorting pairs in bins, water sort puzzle}

Keywords: Ball sort puzzle, recreational mathematics, sorting pairs in bins, water sort puzzle
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI