Yin-Yang Puzzles are NP-complete
Erik Demaine |
@ | MIT |
Jayson Lynch |
@ | U. Waterloo |
Mikhail Rudoy |
@ | LeapYear Tech. |
Yushi Uno |
@ | Osaka Prefecture U. |
Grid Graph Connected Partition
- Given a partially 2-colored $m \times n$ grid graph
- Complete so that each color class is connected
- Theorem: NP-complete [DLRU 2021]
oX...
.....
Xo.XX
.....
...XX
oXXXX
ooooX
XooXX
XXXXX
XXXXX
Grid Graph Tree Partition
- Given a partially 2-colored $m \times n$ grid graph
- Complete so that each color class is a tree
- Theorem: NP-complete [DLRU 2021]
oX...
.....
Xo.XX
.....
...XX
oXXXX
ooooX
XoXXX
XoooX
XXXXX
Yin-Yang Puzzles
- Complete $m \times n$ board with black/white circles:
- Each color of circles orthogonally connected
- No $2\times 2$ square is all the same color
oX...
.....
Xo.XX
.....
...XX
oXXXX
ooooX
XoXXX
XoooX
XXXXX
Yin-Yang $\approx$ Tree Partition
- Roughly equivalent to Grid Graph Tree Partition
- Without $2 \times 2$ rule, roughly equivalent to
Grid Graph Connected Partition
oX...
.....
Xo.XX
.....
...XX
oX...
.....
Xo.XX
.....
...XX
Yin-Yang $\approx$ Tree Partition
- Connectivity properties are the same. Acyclic?
| 2. No $2 \times 2$ $\Rightarrow$ no 4-cycle | 3. Lemma: no alternating $2 \times 2$ |
4. $>4$-cycle separates, except at the boundary |
| XX XX | oX Xo | ooo oXo ooo |
Our Results
- Yin-Yang is NP-complete
- Grid Graph Tree Partition is NP-complete
- Yin-Yang without $2 \times 2$ rule is NP-complete
- Grid Graph Connected Partition is NP-complete
- Reductions from Tree-Residue Vertex Breaking (TRVB)
- Yin-Yang font
Yin-Yang Font
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXoXo
oXoXoooXo
oXoXXXXXo
oXoooooXo
oXoXoXoXo
oXoXoXoXo
oXXXoXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oooXoooXo
oXXXoXoXo
oooXoXXXo
oXXXooooo
oooXoXXXo
oXXXoXoXo
oooXoooXo
oXXXXXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXoXo
oXoXoXXXo
oXoXooooo
oXoXoXXXo
oXoXXXoXo
oXoooooXo
oXoXXXXXo
oXooooooo
ooooooooo
oXXXXXXXo
ooXooooXo
oXXXXXoXo
ooXooooXo
oXXXXXoXo
ooXooooXo
oXXXXXoXo
oooooooXo
oXXXXXXXo
ooXoooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXXXo
oXoXooooo
oXoXXXXXo
oXoXooooo
oXoXXXXXo
oXoooooXo
oXoXXXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXXXo
oXoXooooo
oXoXXXXXo
oXoooooXo
oXoXXXXXo
oXoXoXoXo
oXoXoXoXo
oXooooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXXXo
oXoXooooo
oXoXoXXXo
oXoXoXoXo
oXoXXXoXo
oooooooXo
oXXXXXXXo
oXooooooo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoXoXoXo
oXoooooXo
oXoXXXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXXXoXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oooXoXooo
oXXXoXXXo
oooXoXooo
oXXXoXXXo
oooXoXooo
oXXXoXXXo
oooXoXooo
oXXXoXXXo
oooXooooo
ooooooooo
oXXXXXXXo
oXoooXoXo
oXXXoXoXo
oooooXoXo
oXXXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoooXoXo
oXXXXXoXo
oooooooXo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoXoooXo
oXoXXXXXo
oXoXooooo
oXoXXXXXo
oXoXoooXo
oXoXoXoXo
oXoXoXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oXoXoXoXo
oXoXoXoXo
oXoXoXooo
oXoXoXXXo
oXoXooooo
oXoXXXXXo
oXooooooo
oXXXXXXXo
oXooooooo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXXXoXo
oXooooooo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoXoooXo
oXoXXoXXo
oXooXooXo
oXXoXXoXo
oXoooXoXo
oXoXoXoXo
oXXXoXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXoXo
oXoXoXoXo
oXoXoXoXo
oXoooXoXo
oXXXXXoXo
oooooooXo
oXXXXXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oooXoooXo
oXXXoXoXo
oooXoXoXo
oXXXoXoXo
oooXoXoXo
oXXXoXXXo
oooXooooo
oXXXXXXXo
oooXooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoooXo
oXoXXXXXo
oXoooooXo
oXXXXXoXo
oooooooXo
ooooooooo
oXXXXXXXo
oooXoooXo
oXXXoXoXo
oooXoXXXo
oXXXoXooo
oooXoXXXo
oXXXoXoXo
oooXoXoXo
oXXXoXoXo
oooXooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXoXXXXXo
oXooooooo
oXXXXXXXo
oooooooXo
oXXXXXoXo
oXoooooXo
oXXXXXXXo
oXooooooo
ooooooooo
oXXXXXXXo
oXoXoXoXo
oXoXoXoXo
oooXoXooo
oXXXoXXXo
oooXoXooo
oXXXoXXXo
oooXoXooo
oXXXoXXXo
oooXooooo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXXXoXo
oXooooooo
oXXXXXXXo
oXooooooo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoXXXoXo
oXooXooXo
oXXoXoXXo
ooXoXoXoo
oXXoXoXXo
ooXoooXoo
oXXXoXXXo
oooXooooo
ooooooooo
oXoXXXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXoXoXoXo
oXXXoXXXo
oXooooooo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoooooXo
oXXXXXXXo
ooooXoooo
oXXXXXXXo
oXoooooXo
oXoXoXoXo
oXXXoXXXo
oXooooooo
ooooooooo
oXXXoXXXo
oXoXoXoXo
oXoXoXoXo
oXoXXXoXo
oXoooooXo
oXXXoXXXo
oooXoXooo
oXoXoXoXo
oXXXoXXXo
oooXooooo
ooooooooo
oXXXXXXXo
oXoooooXo
oXXXXXoXo
oooooooXo
oXXXXXXXo
oXooooooo
oXoXXXXXo
oXoooooXo
oXXXXXXXo
oXooooooo
Yin-Yang Font
.........
.........
...ooo...
..o...o..
..oX.o...
..o......
...o.o...
..o.o.o..
....o....
..XXo.X..
oX.......
.........
.........
.o.X.o...
....o....
.o.Xo.X..
.....ooo.
.oo.o.X..
....o....
.oo..o...
..X......
oX.......
.........
.........
...ooo...
..o...o..
..o.o....
..o..ooo.
..o...X..
..o.X..X.
.......X.
..o.XXX..
oXo......
.........
.........
..X.oo...
......o..
..X.oo...
......o..
.oX.oo...
......o..
.ooooo...
...X.....
.oX......
.........
.....XX..
...o...X.
..o..XX..
..o.oooo.
..o......
..oX.ooo.
..o......
...ooo.X.
..o......
oX.o.....
.........
......X..
...oo..X.
..o.XXX..
..oX.....
..o.XXX..
.......X.
..o.X.X..
..oX.X.X.
..o......
oX.o.....
.........
......X..
...oo..X.
..o...X..
..o..ooo.
..o.o.X..
..o.o....
..o...o..
.o.ooo...
..X......
oX.......
.........
..X.o.X..
....oX.X.
..o.o....
...o.o...
..o......
..o.oX.X.
..o.oX.X.
....oX.X.
..XXo.X..
oX.......
.........
..X.X....
...X.X.o.
..X......
...X.X.o.
..X..XX..
.o.X.X...
......X..
.o.X.X...
..X...X..
...X.....
.........
.........
..oo..o..
....o.o..
.ooo..o..
..X.o.o..
.X.Xo.o..
....o.o..
...o..o..
......o..
......oXo
.........
....o.X..
..o.o....
..o..o...
..o......
..oX.ooo.
..o......
..o..o...
..o.o....
..o.o.X..
oX.o.....
.........
..X...X..
.X.Xo....
.X.Xo.o..
.X.Xo..o.
....o....
..o..ooo.
..o......
...ooooo.
..X..X...
oX.......
.........
..X.o.X..
.X.Xo....
.X.Xo.o..
....o.o..
..o.o.o..
..o.o.o..
..o...o..
..oX.Xo..
..o.X.o..
oX.o.....
.........
....o....
..o.o.o..
..o.o....
..oX.o...
...o.....
...o..o..
.........
....oX.X.
..XXo.X..
oX.......
.........
.........
...ooo...
..o.X.o..
..o...o..
..o.o.o..
...o..o..
......o..
.ooooo...
..X....X.
oX.......
.........
.........
.oo..o...
....o.o..
.oo.o.o..
....o....
.oo.oX.X.
..X.o.X..
...X.ooo.
..X.X....
...X.....
.........
.........
...ooo...
..o.X.o..
..o...o..
..o.o.o..
..o..o...
..o......
...ooo...
......o..
.....o.Xo
......o..
.........
.oo..o...
..X.o.o..
...Xo....
..X.oX.o.
.o.Xo.X..
....o....
.o.Xo.o..
..X.o.o..
...X.o...
.........
.........
...oooo..
..o......
...ooooo.
.........
.ooooo...
..XX..o..
.X...o...
..XX.....
oX.......
.........
....X....
..oX.Xo..
..oX.Xo..
.o.X.X.o.
.X....X..
.o.X.X...
..X...X..
...X.X...
..X...X..
...X.....
.........
..X.o.X..
....oX.X.
..o.oX.X.
..o.oX.X.
..o.oX.X.
..o......
..o.X.o..
...ooooo.
..X......
oX.......
.........
.........
..oX.Xo..
..o...o..
.........
...o.o...
.o.o.o.o.
...o.o...
..X....o.
....o..X.
...Xo....
.........
..o.X....
..oX.X.X.
..oX.X.X.
..o..X.X.
..o.oX.X.
..o.oX.X.
..o.oX.X.
....oX.X.
..XXo.X..
oX.......
.........
....o....
..o.o.o..
...o.o...
...X.....
.o.oX.oo.
...X.....
...o.o...
..o.o....
..X.o.X..
oX.......
.........
....o.X..
..o.oX.X.
..o.o....
..o...o..
...o.o...
....o....
.o..o..o.
....o.o..
.XX.o....
...X.o...
.........
.........
..oooo...
......o..
.ooooo...
.........
...ooooo.
..o..XX..
...o...X.
..X..XX..
oX.......
https://erikdemaine.org/fonts/yinyang/
https://erikdemaine.org/fonts/yinyang/cccg.html
.................................
....XXX.o.XXXXX.o.......o.XXXXX..
.......XoX.....Xo..ooo..oX.....X.
..o.X..XoX..X..Xo.o.X...oX..XXX..
..oX..X.oX.X..X.o.oX..X.o....ooo.
..oX.....X.X......oX......o.o.X..
..oX..X.oX.X..XXo.oX..X.o.o.o....
..o.X.oXoX..X..Xo.o.X.o.o.o...o..
.......XoX.....Xo..ooo...o.ooo...
o.o.XXX.o..XXXX.o.o.....o.XXXXX.o
...ooooo...ooooo...ooooo.X.......
X...............................X
https://erikdemaine.org/fonts/yinyang/cccg.html
ooooooooooooooooooooooooooooooooo
oXXXXXXXoXXXXXXXoXXXXXXXoXXXXXXXo
oXoooooXoXoooooXoXoooooXoXoooooXo
oXoXXXoXoXoXXXoXoXoXXXoXoXoXXXXXo
oXoXoXXXoXoXoXXXoXoXoXXXoXoXooooo
oXoXoooooXoXoooooXoXoooooXoXoXXXo
oXoXoXXXoXoXoXXXoXoXoXXXoXoXoXoXo
oXoXXXoXoXoXXXoXoX.XXXoXoXoXXXoXo
oXoooooXoXoooooXoXoooooXoooooooXo
oXoXXXXXoXoXXXXXoXoXXXXXoXXXXXXXo
oXoooooooXoooooooXoooooooXooooooo
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
History of Yin-Yang Puzzles
- Published in 1994 in Japanese puzzle magazine Puzzler as “白丸黒丸” /
“しろまるくろまる” (“Shiromaru-Kuromaru”)- Meaning: “white circle / black circle”
- Introduced many times
- “Yin-Yang” seems most popular today
Complexity of Puzzles
- $>30$ pencil & paper puzzles proved NP-hard
- Many relate to other problems in TCS:
- Numberlink [Kotsuma & Takenaga 2010] —
vertex disjoint paths - Spiral Galaxies [DLS 2015], Tatamibari [ABDDLL 2020] — partition into rectangles
- Slitherlink [Yato & Seta 2003], The Witness [ABDHHKLR'18] — Hamiltonian path
- Masyu [Friedman 2002] — angle-restricted tours
- Path Puzzles [BDDHKK 2020] — discrete tomography
- Numberlink [Kotsuma & Takenaga 2010] —
Related Graph Partitioning
- Often looking for partitions which are connected, balanced, and compact
- NP-complete to find balanced partition in grid graphs for:
- 2 colors in weighted graphs, even with only three rows [BLLS 1998]
- 3 colors in unweighted graphs [BNP 2018]
- $k$ colors in solid grid graphs [Feldmann 2013]
- Polynomial-time algorithms for approximating balanced partitions in planar graphs [HZGX 2021]
Tree-Residue Vertex Breaking (TRVB) [Demaine & Rudoy 2018]
- Reduce from TRVB in 4-regular planar multigraphs, which is NP-complete
- Given a graph, is there a set of vertices that can be broken so the resulting graph is a tree?
Tree-Residue Vertex Breaking (TRVB) [Demaine & Rudoy 2018]
- Reduce from TRVB in 4-regular planar multigraphs, which is NP-complete
- Given a graph, is there a set of vertices that can be broken so the resulting graph is a tree?
Grid Graph Connected Partition / Yin-Yang without $2 \times 2$ Rule
ooooo
XX.oo
oo.XX
XX.oo
oo.XX
ooooo
TRVB vertex
ooooo
XX%oo
oo%XX
XX%oo
oo%XX
ooooo
Unbroken vertex
ooooo
XX0oo
oo0XX
XX0oo
oo0XX
ooooo
Broken vertex
Tiling the Gadgets ($9 \times 9$)
oooooXooo
oooooXooo
XXX.oXoXX
ooo.XXoXo
oXX.oooXo
oXo.XXXXo
oXooooooo
oXXXXXooo
oooooXooo
Tilable vertex gadget
ooooooooo
ooooooooo
oooooXXXX>
oooooXooo
oooooXooo
oooooXooo
oooooXooo
oooooXooo
oooooXooo
Tilable corner gadget
Full Reduction Example
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
oooooooooooooooooooooooXXXXXXXXXXXXXXXXXXXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
ooooooooooooooXXXXXXX.oXoXXXXXXXXooooooooXooo
ooooooooooooooXoooooo.XXoXooooooXooooooooXooo
ooooooooooooooXooooXX.oooXooooooXooooooooXooo
ooooooooooooooXooooXo.XXXXooooooXooooooooXooo
ooooooooooooooXooooXooooooooooooXooooooooXooo
ooooooooooooooXooooXXXXXooooooooXooooooooXooo
ooooooooooooooXooooooooXooooooooXooooooooXooo
ooooooooooooooXooooooooXooooooooXooooooooXooo
ooooooooooooooXooooooooXooooooooXooooooooXooo
oooooXXXXXXX.oXoXXXXX.oXoXXXXX.oXoXXXXXXXXooo
oooooXoooooo.XXoXoooo.XXoXoooo.XXoXoooooooooo
oooooXooooXX.oooXooXX.oooXooXX.oooXoooooooooo
oooooXooooXo.XXXXooXo.XXXXooXo.XXXXoooooooooo
oooooXooooXooooooooXooooooooXoooooooooooooooo
oooooXooooXXXXXooooXXXXXooooXXXXXoooooooooooo
oooooXooooooooXooooooooXooooooooXoooooooooooo
oooooXooooooooXooooooooXooooooooXoooooooooooo
oooooXooooooooXooooooooXooooooooXoooooooooooo
oooooXooooooooXXXXXXX.oXoXXXXXXXXoooooooooooo
oooooXooooooooooooooo.XXoXooooooooooooooooooo
oooooXoooooooooooooXX.oooXooooooooooooooooooo
oooooXoooooooooooooXo.XXXXooooooooooooooooooo
oooooXoooooooooooooXooooooooooooooooooooooooo
oooooXoooooooooooooXXXXXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXXXXXXXXXXXXXXXXXXXooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
Full Reduction Example
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
oooooooooooooooooooooooXXXXXXXXXXXXXXXXXXXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
oooooooooooooooooooooooXoooooooooooooooooXooo
ooooooooooooooXXXXXXX%oXoXXXXXXXXooooooooXooo
ooooooooooooooXoooooo%XXoXooooooXooooooooXooo
ooooooooooooooXooooXX%oooXooooooXooooooooXooo
ooooooooooooooXooooXo%XXXXooooooXooooooooXooo
ooooooooooooooXooooXooooooooooooXooooooooXooo
ooooooooooooooXooooXXXXXooooooooXooooooooXooo
ooooooooooooooXooooooooXooooooooXooooooooXooo
ooooooooooooooXooooooooXooooooooXooooooooXooo
ooooooooooooooXooooooooXooooooooXooooooooXooo
oooooXXXXXXX0oXoXXXXX%oXoXXXXX0oXoXXXXXXXXooo
oooooXoooooo0XXoXoooo%XXoXoooo0XXoXoooooooooo
oooooXooooXX0oooXooXX%oooXooXX0oooXoooooooooo
oooooXooooXo0XXXXooXo%XXXXooXo0XXXXoooooooooo
oooooXooooXooooooooXooooooooXoooooooooooooooo
oooooXooooXXXXXooooXXXXXooooXXXXXoooooooooooo
oooooXooooooooXooooooooXooooooooXoooooooooooo
oooooXooooooooXooooooooXooooooooXoooooooooooo
oooooXooooooooXooooooooXooooooooXoooooooooooo
oooooXooooooooXXXXXXX%oXoXXXXXXXXoooooooooooo
oooooXooooooooooooooo%XXoXooooooooooooooooooo
oooooXoooooooooooooXX%oooXooooooooooooooooooo
oooooXoooooooooooooXo%XXXXooooooooooooooooooo
oooooXoooooooooooooXooooooooooooooooooooooooo
oooooXoooooooooooooXXXXXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXoooooooooooooooooXooooooooooooooooooooo
oooooXXXXXXXXXXXXXXXXXXXooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooo
Grid Graph Tree Partition /
Yin-Yang with $2 \times 2$ Rule
XoXoXoXoXoX
XoooooXoooX
XoX.X.X.XoX
XoXoXoXoXoX
Xo.......oX
X.oXoXoXo.X
X.oXoXoXo.X
Xo.......oX
XoXoXoXoXoX
XoXoXoXoXoX
XoXoXoXoXoX
TRVB vertex gadget
Grid Graph Tree Partition /
Yin-Yang with $2 \times 2$ Rule
XoXoXoXoXoX
XoooooXoooX
XoX%X%X%XoX
XoXoXoXoXoX
Xo0000000oX
X%oXoXoXo%X
X0oXoXoXo0X
Xo%%%%%%%oX
XoXoXoXoXoX
XoXoXoXoXoX
XoXoXoXoXoX
Unbroken vertex
XoXoXoXoXoX
XoooooXoooX
XoX0X0X0XoX
XoXoXoXoXoX
Xo%%%%%%%oX
X0oXoXoXo0X
X%oXoXoXo%X
Xo0000000oX
XoXoXoXoXoX
XoXoXoXoXoX
XoXoXoXoXoX
Broken vertex
Tiling the Gadgets ($16 \times 16$)
XoXoXoXoXoXoXoXo
XoooooooooXoXoXo
XoXXXXXXXXXoXoXo
XoXoXoooooXoooXo
XoXoXoX.X.X.XoXo
XoXoXoXoXoXoXoXo
XoXoXo.......oXo
XoXoX.oXoXoXo.Xo
XoXoX.oXoXoXo.Xo
XoXoXo.......oXo
ooXoooXoXoXoXooo
XoXXXXXoXoXoXXXX>
XoooooooXoXoXoXo
XXXXXXXXXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
Tilable vertex gadget
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXooooooo
XoXoXoXoXoXXXXXX
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXo
Tilable corner gadget
Full Reduction Example
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooooooooXoooooooooooooooooooooXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooXoooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX.X.X.XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo.......oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX.oXoXoXo.XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX.oXoXoXo.XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo.......oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoooooooooXoooXoXoXoXoooooooooooooooXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXoXXXXXoXoXoXXXXXXXXXXXXXXXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoooooooooXoXoXoXoooooooooXoXoXoXoooooooooXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoooooXoooXoXoXoXoooooXoooXoXoXoXoooooXoooXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoX.X.X.XoXoXoXoXoX.X.X.XoXoXoXoXoX.X.X.XoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXo.......oXoXoXoXo.......oXoXoXoXo.......oXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoX.oXoXoXo.XoXoXoX.oXoXoXo.XoXoXoX.oXoXoXo.XoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoX.oXoXoXo.XoXoXoX.oXoXoXo.XoXoXoX.oXoXoXo.XoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXo.......oXoXoXoXo.......oXoXoXoXo.......oXoXoXoXoXoXoXoXoXo
XoXoXoXoXoooooooooXoooXoXoXoXoooooXoooXoXoXoXoooooXoooXoXoXoXoooooooooooooXoXoXo
XoXoXoXoXoXXXXXXXoXXXXXoXoXoXXXXXoXXXXXoXoXoXXXXXoXXXXXoXoXoXXXXXXXXXXXXXXXoXoXo
XoXoXoXoXoXoXoXoXoooooooXoXoXoXoXoooooooXoXoXoXoXoooooooXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooXoooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX.X.X.XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo.......oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX.oXoXoXo.XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX.oXoXoXo.XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo.......oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooXoooXoXoXoXoooooooooooooXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXoXXXXXoXoXoXXXXXXXXXXXXXXXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoooooooooooooooooooooooooooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
Full Reduction Example
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooooooooXoooooooooooooooooooooXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooXoooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX%X%X%XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo0000000oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX%oXoXoXo%XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX0oXoXoXo0XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo%%%%%%%oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoooooooooXoooXoXoXoXoooooooooooooooXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXoXXXXXoXoXoXXXXXXXXXXXXXXXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoooooooooXoXoXoXoooooooooXoXoXoXoooooooooXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoooooXoooXoXoXoXoooooXoooXoXoXoXoooooXoooXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoX0X0X0XoXoXoXoXoX%X%X%XoXoXoXoXoX0X0X0XoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXo%%%%%%%oXoXoXoXo0000000oXoXoXoXo%%%%%%%oXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoX0oXoXoXo0XoXoXoX%oXoXoXo%XoXoXoX0oXoXoXo0XoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoX%oXoXoXo%XoXoXoX0oXoXoXo0XoXoXoX%oXoXoXo%XoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXo0000000oXoXoXoXo%%%%%%%oXoXoXoXo0000000oXoXoXoXoXoXoXoXoXo
XoXoXoXoXoooooooooXoooXoXoXoXoooooXoooXoXoXoXoooooXoooXoXoXoXoooooooooooooXoXoXo
XoXoXoXoXoXXXXXXXoXXXXXoXoXoXXXXXoXXXXXoXoXoXXXXXoXXXXXoXoXoXXXXXXXXXXXXXXXoXoXo
XoXoXoXoXoXoXoXoXoooooooXoXoXoXoXoooooooXoXoXoXoXoooooooXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooXoooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX%X%X%XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo0000000oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX%oXoXoXo%XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoX0oXoXoXo0XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo%%%%%%%oXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooXoooXoXoXoXoooooooooooooXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXoXXXXXoXoXoXXXXXXXXXXXXXXXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoooooooooooooooooooooooooooooooXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
XoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXoXo
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
Open Problems
- ASP- or #P-complete?
- Our reduction is parsimonious, so results for TRVB would suffice
- FPT with respect to the number of initial clues?
- Easy with respect to unfilled squares
- Yin-Yang on hexagonal or triangular grids?
- Graph/Tree partition in other special graphs?
- Fun with more colors? (Still NP-hard)