A problem about Yin-Yang puzzles

Question

In a Yin-Yang puzzle, one must fill every cell with either a black circle or a white circle according to the following rules:

1. All cells with black circles form an edge-connected region. All cells with white circles form an edge-connected region.
2. No 2x2 square of cells is entirely filled with circles of the same colour.

Below are two Yin-Yang "puzzles". Which of them, if either, has a unique solution? (Naturally, give a full proof.)

Answer 1

The puzzle on the left has many solutions, while the one on the right has no solutions.

I'll start by dealing with the rightmost puzzle.

As Gareth McCaughan observed, the outside of the board consists of a contiguous group of white squares and a contiguous group of black squares; if there were more than two contiguous white groups on the border, then there would be more than two black groups, and the path connecting the white groups would separate the black groups.

Call the two vertices on the boundary where white meets black A and B, where A is the near the given clues. Imagine starting at point A, and following the border of the black region until you reach point B.

• The path you are tracing must touch every interior vertex at least once. If it didn't, that would mean there was no color change around that vertex, which means it is surrounded by a 2x2 solid square.

• The path cannot visit any interior vertex twice. This would mean that the 2x2 square around the vertex was colored like a checkerboard. But then the path connecting the opposite white squares would have to separate the black ones, so this can't happen.

Therefore, the boundary path visits every interior vertices exactly once.

Here comes the contradiction. Color the vertices of this grid black and white in checkerboard fashion, so A is black. The boundary path must alternate between black and white, and visits all 81 interior vertices, plus A and B, for 83 vertices total. This means it must visit 41 white vertices, all in the interior. But there are only 40 white vertices in the interior! Therefore, this puzzle has no solution.

This also shows that a solution to the left puzzle is given by any Hamiltonian path on the interior vertices which starts near the given clues and ends near the border, of which there are many.

Answer 2

Grid 1

has a solution but the solution is not unique. You can change the bottom right corner to a white dot, and the grid is still correct.

Grid 2

does not have a solution, in order to follow the rules, a black dot would need to be placed below the initial white dot. This then forces the dots onto even columns, and due to the edge to edge requirement means that we'll always end up with a 2x2 square.

Explanation for grid 2.

So you're forced to place a black dot where the black square is. You then have to connect these two black dots edge-to-edge without blocking white sections from being edge to edge. Your options are to place a black dot where the gray square is, or go around. Because the white dots need to be connected you can't just block off the edge and do a row with alternating columns from the gray dot (you either have 2 white spaces -green, or white gets trapped at the top -blue). And you can't run down the side because you won't be able to connect to the forced black dot position without block a white path -purple. The black dots are forced to stay in alternating inner squares, and because of the one odd square, it means you always end up with a 2x2 section.

Which of them, if either, has a unique solution?

Neither.

Answer 3

Super-duper-incomplete answer

Emma has already dealt with the left-hand grid. What about the right-hand one?

First, here is a useful theorem:

In a completed yin-yang grid, the cells around the outside edge either are all the same colour or consist of a contiguous group of whites and a contiguous group of blacks. Proof: If not then we must have W,B,W,B in some order (perhaps separated by other cells) around the edge. Then the two W must connect and the two B must connect, but they can't both do so.

Now, suppose we have a solution for the RH grid. Consider

how many contiguous white cells there are around the edge. If we make the number either 1 or 2 then the remainder of the edge must be filled with black cells, and then it's easy to see that the 1-case and the 2-case look exactly the same apart from the state of the top left cell, and in particular neither of these options can yield a unique solution because if one works then the other does too.

Therefore,

if the RH puzzle has a unique solution then the number of contiguous white cells around the edge must be >2; the <=2 case yields either no solution or more than one. Putting three contiguous white cells in that corner requires that the cell one in from the corner must be black; this in turn requires that we have at least four contiguous white cells on the edge since otherwise they are isolated from the rest of the grid.

This leads fairly easily to

these two cases (obtained by splitting according to whether the group of contiguous black cells around the edge has size 1 or size >1), exactly one of which must lead to a solution if the RH puzzle has a unique solution: @ @ + + . . . . . . @ @ + @ @ @ @ @ @ @ @ + + @ . . . . . . @ + + . . . . . + @ @ . . . . . . . . . @ . . . . . . . . @ . . . . . . . . . . @ . . . . . . . . @ . . . . . . . . . . @ . . . . . . . . @ . . . . . . . . . . @ . . . . . . . . @ . . . . . . . . . . @ . . . . . . . . @ . . . . . . . . . . @ . . . . . . . . @ . . . . . . . . . . @ + . . . . . . + @ . . . . . . . . . . @ @ @ @ @ @ @ @ @ @

but at this point I am stuck for the moment because

for neither of these can I see a contradiction, a clear path to a unique solution, or a proof of multiple solutions.

Answer 4

Quite incomplete:

It is pretty easy to show on grid2 that:

If the grid was 4x4, there would be no solution. Partition the grid to 4 2x2 squares, and we know each square requires at least 1 black and 1 white. Plus the middle 4 require at least 1 black, 1 white. Now consider top left square. It can have black on the bottom left or right. If it is bottom left, this forces black X all over the edge as proven by gareth. This leads to one of the squares having 4 black, or having 4 whites in the central square.

Now, bottom right of the top left being black means the following image:

 o o x .
 o x a b
 o . . .
 . . . .
 

Now, let's consider what color can the a have - it is obviously x, as if it was o, those x (or o) could not be connected. Now this in turn leads to b being o. And this is just again the mirror image of the first case. So, there is no solution.

Now I assume the above should probably generalize

to no solution in the 10x10 grid. No proof for that, but it seems likely from the 4x4 case. I would probably have to do induction and consider N+2 and prove this for all even N.

The nice bit is that you need to take care of just 2x2 squares that start from the top left corner and those which are shifted by 1 in both directions - no need to consider 2x2 that are shifted by 1 in just one direction. Those won't be a problem.

Answer 5

Incomplete answer. I attempt to prove the theorem in a very roundabout way. It is easy to intuitively understand the theorem, but I would love if someone could simplify this formal proof.

Theorem:

Any complete board consists of contiguous paths, 1 cell thick, where the path is surrounded by other paths, each 1 cell thick.

From Rule 1:

Let us define contiguous paths. For any black cell, moving in cardinal directions, you are able to reach any other black cell, without landing on a white cell. For any white cell, moving in cardinal directions, you are able to reach any other white cell, without landing on a black cell.

Property of path.

The contiguous path must never "fold in" on itself. Imagine the contiguous path as a snake. Let us define some terms.

Snake head position.

The cell the snake head is currently on, in the board (e.g. a black cell).

Snake heading.

The cardinal direction the snake head is pointing at. The snake head can turn left or right, changing the direction it is pointing (e.g. if initially point left, and turn left, then finally point down).

Property of snake heading.

When there is a one-cell gap between snake head position and any part of the snake body, the snake heading cannot be in the direction of the snake body. Snake body is defined later. As we shall see, this property is a consequence of no snake squares and no snake loops allowed (which are themselves a consequence of Rule 1 and Rule 2).

Snake movement and Snake body.

There are cells neighboring the snake head position. On movement, one of these cells will be chosen. Which cell will be chosen depends on the snake heading (e.g. snake is heading down, and snake moves, then the cell directly downwards of the snake head position will be chosen). The snake head position updates to the chosen cell. The chosen cell is colored the same color as the previous snake head position. The previous snake head position is now part of the snake body. Also, current snake heads are part of the snake body.

Snake initialization.

Let's say the snake starts in the center cell of the board, initial heading up.

Snake square.

The following snake movement results in a 2 x 2 square. Snake move. Snake turn right. Snake move. Snake turn right. Snake move. Similar sequences under rotational symmetry are not allowed under Rule 2.

Snake loop.

If the snake moves such that the snake head position is beside the snake body, then we have formed a loop. A loop is where the snake head and the snake body form a circular path. Starting from the head and moving along cardinal directions along the body, and without backtracking, we are able to reach the head again. For example, snake move, snake move, snake turn right, snake move, snake move, snake turn right, snake move, snake move, snake turn right, snake move. The center of the loop is separate from other cells of the same color. Hence under Rule 1, loops are not allowed.

Snake branching (not essential to theorem, but I hope helps in solving this puzzle).

For any snake head position, the snake is able to duplicate its head. Each of the heads must have a unique snake heading. We can change the heading and move each duplicated head separately. The snake does not duplicate its body: all previous duplicated heads will be added to the same body. This defines path branching.

Snake bounding (also not essential).

Imagine the opposite action of branching. When many snake heads meet at the same cell, they can bind together into one head. Also, they can bound then branch, for example, snake heads come in from up and down, and bind together. Then, the one snake head branches into two, and exits left and right.

Lemma 1.

The snake must be one cell thick. Proof: no snake squares are allowed.

Lemma 2.

The snake is surrounded by walls of opposite color as the snake. Proof: since snake squares and snake looping are not allowed, the snake head / body must not be on either of the two sides of the snake. For example, if the snake is black, then it must be surrounded by white cells.

Conclusion.

Since this theorem must hold true no matter the color of the snake, we can reapply Lemma 2 for both walls of the snake. For example, if the snake is black, the walls are white. If we imagine the white walls are white snakes, then by Lemma 1, the white walls must be one cell thick. By Lemma 2, the white walls must be surrounded by black walls. By recursively applying Lemma 1 and 2, the theorem is proven.