Is there a way to complete a sudoku where you have to make sure all even digits are orthogonally connected to all the others, while avoiding 2x2 squares of even digits?
It is known to be possible when 2x2 squares are permitted - see, for example, the following arrangement:
But is it possible while avoiding 2x2 squares of even digits?
It is...
...not possible. Via mixed integer linear programming, I have concluded that the minimum number of 2x2 squares is 2, as in the example.
If you relax the problem to consider only parity of the digits (4 even and 5 odd per row, column, or 3x3 box),...
...the minimum number of 2x2 squares is still 2.
If you omit the 3x3 box constraints, it is...
...possible:
By request, here are the details about how I enforced connectivity of the subgraph induced by the even nodes. I often use dynamically generated "node separator" constraints, but for this problem a compact, flow-based formulation performed much better. Construct an undirected graph with node set $N$ and edge set $E$. Here, $|N|=81$ and $|E|=144$. Now let arc set $A=E \cup \{(j,i):(i,j)\in E\}$, so $|A|=288$. The idea is to select one even node as the root and send one unit of flow from the root to each of the other even nodes. For $i\in N$, let binary decision variable $e_i$ indicate whether node $i$ is an even node, and let binary decision variable $r_i$ indicate whether node $i$ is the root node. For $(i,j)\in A$, define nonnegative flow variable $f_{ij}$. The constraints are:
\begin{align} \sum_{i \in N} r_i &= 1 \\ r_i &\le e_i &&\text{for $i \in N$} \\ \sum_{(i,j) \in A} f_{ij} - \sum_{(j,i) \in A} f_{ji} &= 4\cdot9\cdot r_i - e_i &&\text{for $i \in N$} \\ f_{ij} &\le (4\cdot 9-1) e_k && \text{for $(i,j) \in A$ and $k \in \{i,j\}$} \\ e_i &\in \{0,1\} &&\text{for $i\in N$} \\ r_i &\in \{0,1\} &&\text{for $i\in N$} \\ f_{ij} &\ge 0 &&\text{for $(i,j)\in A$} \\ \end{align}
By symmetry, you can optionally limit the choice of root nodes to the first five nodes in the top row.
By modifying the connectivity rule, I was able to find many solutions.
This was to allow connectivity to wrap at the edges – a toroidal board.
Here is one of them.
The methodolgy was to write a C program:
Step 1: make a list of 118 blocks size 3x3 containing 4 'even' cells.
Step 2: permute those blocks to make a list of 103974 strips size 3x9.
Step 3: permute those strips to make a 9x9 grid.
Each step excluded perms with isolated cells or 2x2 blocks with the known neighbours, and impossible row or column counts of 'even' cells.
Step 4: check that all these 'even' cells connect.
Step 5: fill in the sudoku grid with odd and even numbers.
The first solution fell out in less than a minute.
The modified rule also applies to 2x2 blocks – there are none which connect via edges.
