# Orthogonally connecting even sudoku digits avoiding squares

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?

• Was this question perhaps inspired by today's GAS puzzle in the Cracking the Cryptic Discord? 😄 Apr 19 at 20:50
• Supposing it were possible, can someone find a good upper bound for the maximum path between any two even numbers? Thirty-six seems a tad too large for my program :/ Apr 19 at 23:53
• @samm82 yes indeed Apr 20 at 9:00

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...

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.

• The ILP was done with the full Sudoku rules? Apr 20 at 2:17
• Yes, although I can also try a relaxation that uses only parity (4 evens per row, column, or 3x3 box). Apr 20 at 2:19
• How long did it take to reach the conclusion? Apr 20 at 2:21
• 20 minutes for the original problem, 1 minute for the parity relaxation. Apr 20 at 2:28
• Woah. I'm curious how you efficiently encoded the single connected component constraint. My SMT program with bitvectors and bools never terminated. Apr 20 at 7:17

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.

• I would have liked to find a symmetrical solution (of odd/even cells), but could not. Apr 22 at 19:23