10
$\begingroup$

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:

with squares

But is it possible while avoiding 2x2 squares of even digits?

$\endgroup$
3
  • 1
    $\begingroup$ Was this question perhaps inspired by today's GAS puzzle in the Cracking the Cryptic Discord? 😄 $\endgroup$
    – samm82
    Apr 19, 2023 at 20:50
  • $\begingroup$ 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 :/ $\endgroup$
    – mintmocha
    Apr 19, 2023 at 23:53
  • 1
    $\begingroup$ @samm82 yes indeed $\endgroup$ Apr 20, 2023 at 9:00

2 Answers 2

8
$\begingroup$

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: enter image description here


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.

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

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.

enter image description here
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.