# Hitori and graph connectivity

Hitori is a Sudoku-like game.

These are its rules:

1. It consists on an $$n\times n$$ matrix. Its terms are integer numbers from $$1$$ to $$n$$. Let's say that each term is in a square.

2. The player must mark every square as white or black.

3. No two white squares in the same row or column can have the same number.

4. No two black squares can share a side.

5. The set of white squares is connected (two squares are connected iff they share a side).

6. The solution, that is, the coloring of the squares, is unique.

My question is about the ratio of black squares. I have played a good number of games and this ratio seems bounded around 30%, but I don't have the knowledge to find a precise good bound and prove it. I'd like to prove it myself.

The lower bound seems related with the 3rd rule. That is, you mark a square as black because you know that other square with the same number in the same row or column is white. There is no other reason for a square to be black.

The upper bound seems related to 4th, 5th and 6th rules. That is, you mark a square as white because it is adjacent to a black square, because being it black would make the set of white squares disconnected or simply because there is no white squares with the same number in the same row or column.

My thoughts so far: The theorems that I have searched about connectivity of graphs are about minimal cuts to make the graph disconnected. But this is about maximal cuts to make the graph connected.

On the other hand, for $$n=3$$ I have found these boards (0 is white and 1 is black): $$\begin{bmatrix}1&0&0\\0&1&0\\0&0&0\end{bmatrix}$$ $$\begin{bmatrix}1&0&1\\0&0&0\\1&0&1\end{bmatrix}$$ But I suspect that the bounds for the ratio can be improved as $$n$$ is increasing.

Thus, my question is: what graph theory should I study to find these bounds?

The lower bound seems related with the 3rd rule. That is, you mark a square as black because you know that other square with the same number in the same row or column is white. There is no other reason for a square to be black.

Actually, the key to the lower bound is rule 6: the uniqueness rule. To see this, note that any solution where a white square is not forced to be white because of rules 4 or 5 is not a unique solution, because it can apparently be made black without violating any of the rules, and so that would be a solution as well.

So yes, rule 3 will force for there to be black squares at all, but rule 6 is the one that will really tell you how many blacks there should be at a minimum in order for the solution to be unique.

For example, Rule 6 definitely rules out any solution with a $$3 \times 3$$ region of all whites, or else you could make the middle one black and have another solution: it would not create any two adjacent black squares, and all white cells keep connected. Also note that Rule 6 rules out any $$1 \times 1$$ Hitori boards, since making that square either white or black would both constitute a solution.

The way to get the most white squares (and thus the least black squares) without getting multiple solutions (i.e. without being able to make any further square black) is to have the black squares force as many white squares as possible, and for that, you want to use the following general pattern:

Note that this pattern has every black not at the edge force its $$4$$ neighboring squares to be white (rule 4), while no two blacks force the same square to be white, meaning that you cannot get a higher ratio of whites. The picture below illustrates this: every black is in the middle of a swiss cross consisting of $$5$$ squares, which can be used to tile the board.

If this was an infinite board, you would get one black for every $$5$$ squares, and so the absolute lower bound is $$20$$%.

Now, for finite boards there still are some edge/corner pieces that are not forced white by the black ones. For the above $$8 \times 8$$ board any actual solution would have to look something like:

And now you're at $$25$$%. I note that you got $$2$$ out of $$9$$ for $$n=3$$, which is $$22$$%.... so I suspect that the lower bound will go slightly up and down depending on the specific $$n$$, but that it will tend to get closer and closer to $$20$$% as $$n$$ gets larger and larger.

For the upper bound, you of course want to do the opposite: have the white squares be forced by multiple black squares. As such, two basic fill patterns are:

(every white is forced by $$2$$ blacks)

and:

(half of white are forced by $$3$$ blacks, and other half by $$1$$)

For an infinite board that gets you $$1$$ out of $$3$$ squares for both patterns, i.e. $$33.3$$%. Of course, none of these two are actual solutions, since not all whites are connected, and so for an actual board you'd have to take out some blacks again, and you'd get something like:

or:

The second pattern seems to actually work a little better ... for this $$8 \times 8$$ board, you have $$19$$ out of $$64$$ blacks, i.e. almost $$30$$%. Now, I note that for $$n=3$$ you got $$4$$ black squares out of $$9$$, i.e. $$44$$%, but this is really an exceptional situation. For $$n=4$$, the best you can do is $$5$$ black squares, and so with $$5$$ out of $$16$$ you are below $$33.3$$% ... For $$n=5$$, you can get back to $$9$$ out of $$25$$ (i.e. A little over $$33.3$$%), but I bet that for any higher $$n$$ you cannot get over $$33.3$$%. As $$n$$ gets higher and higher, though, the upper bound should get closer and closer to $$33.3$$%

Now, you could probably generate some exact formula for specific $$n$$'s (probably involving ceilings and/or floor functions) using these patterns, but I'll leave that up to you.