1. Introduction
Choco Banana is played on a rectangular grid of cells, where some of the cells contain a number (see Fig. 1(a)). The purpose of the puzzle is to paint some of the cells in black (see Fig. 1(f)) according to the following rules [1]: (1) Each set of connected black cells must form a rectangle area. (In Fig. 1(f), there are seven rectangle areas including three square areas.) (2) Each set of connected white cells must not form a rectangle area or a square area. (3) Each number indicates the number of cells of the connected area containing that number.
 |
Fig. 1 (a) Initial configuration of a Choco Banana puzzle. (b)-(f) are the progress from the initial configuration to a solution. |
Figure 1(a) is an initial configuration of a Choco Banana puzzle. From Figs. 1(b)-(f), the reader can understand basic techniques for finding a solution. (b) Cells having number \(1\) or \(2\) must be colored black. All cells which are adjacent to a black cell \(1\) or a black rectangle of size \(2\) must not be colored black (see nine white squares in Fig. 1(b)). Cell \(a\) must be colored black because of the following reason: If cell \(a\) is white, then the number \(6\) in a white square will belong to a connected white area of size at least \(8\). (c) Cells \(b,c\), and \(d\) must be white. Cell \(3\) must be colored black, since the two cells having numbers \(6\) and \(3\) cannot belong to a single connected area. (d) Cell \(3\) forms a \(1\times3\) rectangle area, which is surrounded by white cells. Cell \(e\) must not be colored black, since cell \(f\) cannot form a white square area. Hence, cell \(e\) is white. Similarly, cell \(g\) is also white. (e) A connected white area of \(6\) cells is surrounded by black cells. A set of \(2\times2\) cells forms a black area containing number \(4\). (f) is a solution.
In this paper, we study the computational complexity of the decision version of the Choco Banana puzzle. The instance of the Choco Banana puzzle problem is a rectangular grid of cells, where some of the cells contain a number. The problem is to decide whether there is a solution to the instance. It is clear that the Choco Banana puzzle problem belongs to NP, since the puzzle ends when every cell is colored black or white.
Theorem 1: The Choco Banana puzzle problem is NP-complete.
In 2009, a survey of games, puzzles, and their complexities was reported by Hearn and Demaine [4]. In a chapter of this book, the authors survey Nikoli’s pencil puzzles which have been proved to be NP-complete. After the publication of this book, a lot of Nikoli’s pencil puzzles were shown to be NP-complete. Recently, Double Choco [3], Five Cells and Tilepaint [5], Sukoro [6], Tatamibari [2] Yajisan-Kazusan and Stained Glass [7] were shown to be NP-complete.
2. NP-Completeness of Choco Banana
2.1 Positive Planar 1-in-3-SAT
Let \(U=\{x_1,x_2,\ldots,x_n\}\) be a set of Boolean variables. Boolean variables take on values \(0\) (false) and \(1\) (true). A clause over \(U\) is a set of variables over \(U\), such as \(\{x_1,x_2,x_3\}\). A clause is satisfied by a truth assignment if and only if exactly one of its members is true under that assignment.
An instance of positive planar 1-in-3-SAT is a collection \(C=\{c_1,c_2,\ldots,c_m\}\) of clauses over \(U\) such that (i) \(|c_j|=3\) for each \(c_j\in C\) and (ii) the graph \(G=(V,E)\), defined by \(V=U\cup C\) and \(E=\{\,(x_i,c_j)\mid\mbox{$x_i\in c_j\in C$}\,\}\), is planar. The positive planar 1-in-3-SAT problem asks whether there exists some truth assignment for \(U\) that simultaneously satisfies all the clauses in \(C\). This problem is known to be NP-complete [8].
For example, \(U=\{x_1,x_2,x_3,x_4,x_5\}\), \(C=\{c_1,c_2,c_3\}\), and \(c_1=\{x_1,x_2,x_4\}\), \(c_2=\{x_1,x_3,x_5\}\), and \(c_3=\{x_2,x_3,x_4\}\) provide an instance of positive planar 1-in-3-SAT. For this instance, the answer is “yes,” since there is a truth assignment \((x_1,x_2,x_3,x_4,x_5)=(0,1,0,0,1)\) satisfying all clauses.
2.2 Reduction from Positive Planar 1-in-3-SAT to Choco Banana
We present a polynomial-time transformation from an arbitrary instance \(C\) of positive planar 1-in-3-SAT to a Choco Banana puzzle such that \(C\) is satisfiable if and only if the puzzle has a solution.
Variable \(x_i\) is transformed into a variable gadget as shown in Fig. 2(a). Each cell having number \(1\) forms a black square area of size \(1\), which is surrounded by white cells (see black and white squares in Fig. 2(b)).
 |
Fig. 2 (a) Variable gadget for \(x_i\). (b) Each cell \(1\) forms a black square area. Cells \(a\) and \(b\) cannot belong to a single white area. (c) Solution corresponding to assignment \(x_i=0\). (d) Solution corresponding to \(x_i=1\). |
Consider Fig. 2(b). Assume (for contradiction) that both of cells \(a\) and \(b\) are white. Then, they belong to a white area of size at least \(8\). However, that white area contains cells having number \(5\), a contradiction. Hence, there are two possible cases: Cell \(a\) is black and cell \(b\) is white (see Fig. 2(c)), and cell \(a\) is white and cell \(b\) is black (see Fig. 2(d)).
Consider Fig. 2(c). If cell \(a\) is colored black, then cell \(b\) must be white so that cell \(b\) and its four neighbors form a white area of size \(5\). Thus, cells \(c,d\), and \(e\) must be colored black. Also, cell \(f\) (resp. \(g\)) must be white, since the cell between \(e\) and \(f\) (resp. \(e\) and \(g\)) cannot form a \(1\times1\) white square area. By continuing this observation, cells \(a,e,i,k,\cdots\) are colored black, and cells \(b,h,j,\cdots\) are white. This corresponds to the assignment \(x_i=0\).
Similarly, in Fig. 2(d), cells \(b,h,j,\cdots\) are colored black, and cells \(a,e,i,k,\cdots\) are white. This corresponds to the assignment \(x_i=1\).
Figure 3(a) is a branch gadget. In Fig 3(b), if cell \(a\) is colored black, then cells \(b\) and \(c\) are also colored black. Similarly, in Fig 3(c), if cell \(a\) is white, then cells \(b\) and \(c\) are also white. The green area of Fig. 3(a) can also be used as a right turn gadget. The left turn gadget can be constructed in a similar manner.
 |
Fig. 3 (a) Branch gadget. (b,c) Branch gadget when \(x_i\in\{0,1\}\). (The green area of this figure can also be used as a right turn gadget.) |
Figure 4(a) is a clause gadget for \(c_j=\{x_{i_1},x_{i_2},x_{i_3}\}\). In the figure, there are one yellow area and three red areas. The yellow area is composed \(52\) white cells. Each red area is of size \(5\). The yellow area contains cells having number \(62\).
 |
Fig. 4 (a) Clause gadget for \(c_j=\{x_{i_1},x_{i_2},x_{i_3}\}\). (b) There is a solution to this gadget when exactly one of \(x_{i_1}\), \(x_{i_2}\), and \(x_{i_3}\) is \(1\). (c) This is an invalid black-white-coloring of cells. If at least two of \(x_{i_1}\), \(x_{i_2}\), and \(x_{i_3}\) are \(1\), there is no solution to this gadget. (d) This is an invalid black-white-coloring of cells. If \((x_{i_1},x_{i_2},x_{i_3})=(0,0,0)\), there is no solution to this gadget. |
Suppose that exactly one of \(x_{i_1}\), \(x_{i_2}\), and \(x_{i_3}\) is \(1\) (see Fig. 4(b)). Then, the yellow and red areas contain \(62\) white cells, where \(62=52+5+5\). Thus, Fig. 4(b) is a valid black-white-coloring of cells.
On the other hand, suppose that at least two of \(x_{i_1}\), \(x_{i_2}\), and \(x_{i_3}\) are \(1\) (see Fig. 4(c)). In this case, the yellow and red areas contain at most \(57\) white cells, where \(57=52+5\) \((<62)\). Therefore, Fig. 4(c) is an invalid black-white-coloring of cells.
Suppose \((x_{i_1},x_{i_2},x_{i_3})=(0,0,0)\) (see Fig. 4(d)). In this case, the yellow and red areas contain \(67\) white cells, where \(67=52+5+5+5\) \((>62)\). Therefore, Fig. 4(d) is also an invalid black-white-coloring of cells.
Figure 5 is a Choco Banana puzzle transformed from positive planar 1-in-3-SAT \(C=\{c_1,c_2,c_3\}\), where \(c_1=\{x_1,x_2,x_4\}\), \(c_2=\{x_1,x_3,x_5\}\), and \(c_3=\{x_2,x_3,x_4\}\). From the solution of the puzzle of Fig. 5, one can see that the assignment \((x_1,x_2,x_3,x_4,x_5)=(0,1,0,0,1)\) satisfies all clauses of \(C\).
 |
Fig. 5 Choco Banana puzzle transformed from positive planar 1-in-3-SAT \(C=\{c_1,c_2,c_3\}\), where \(c_1=\{x_1,x_2,x_4\}\), \(c_2=\{x_1,x_3,x_5\}\), and \(c_3=\{x_2,x_3,x_4\}\). From this figure, \(C\) is satisfied when \((x_1,x_2,x_3,x_4,x_5)=(0,1,0,0,1)\). (The reader should see this figure on a big-screen PC.) |
References
[1] https://www.nikoli.co.jp/en/puzzles/choco-banana/
URL
[2] A. Adler, J. Bosboom, E.D. Demaine, M.L. Demaine, Q.C. Liu, and J. Lynch, “Tatamibari is NP-complete,” Proc. 10th International Conference on Fun with Algorithms, LIPICS, vol.157, pp.1:1-1:24, 2021. DOI: 10.4230/LIPIcs.FUN.2021.1
CrossRef
[3] D. Ðurić, “Double Choco is NP-complete,” arXiv:2203.02815, pp.1-35, 2022. DOI: 10.48550/arXiv.2203.02815
CrossRef
[4] R.A. Hearn and E.D. Demaine, Games, Puzzles, and Computation, A K Peters Ltd., MA, 2009. DOI: 10.1201/b10581
CrossRef
[5] C. Iwamoto and T. Ide, “Five cells and tilepaint are NP-complete,” IEICE Trans. Inf. & Syst., vol.E105-D, no.3, pp.508-516, March 2022. DOI: 10.1587/transinf.2021FCP0001
CrossRef
[6] C. Iwamoto and S. Oda, “Computational complexity of Sukoro,” IEICE Trans. Inf. & Syst. (Japanese Edition), vol.J106-D, no.5, pp.357-361, 2023. DOI: 10.14923/transinfj.2022JDL8010
CrossRef
[7] C. Iwamoto and R. Takaishi, “Yajisan-Kazusan and stained glass are NP-complete,” The 23rd Japan-Korea Joint Workshop on Algorithms and Computation, Nagoya, Japan, June 2023.
[8] W. Mulzer and G. Rote, “Minimum-weight triangulation is NP-hard,” J. ACM, vol.55, no.2, pp.1-29, 2008. DOI: 10.1145/1346330.1346336
CrossRef
