Return to Answer

397

$\begin{matrix}2&8&8&2&7&5\\6&1&3&7&5&3\\4&3&1&0&4&1\\2&9&5&8&2&4\\0&6&9&2&3&6\\3&0&1&7&6&1\\\end{matrix}$

I used integer linear programming as follows. Let $C=\{1,\dots,6\}^2$ be the set of cells, and let $D=\{0,\dots,9\}$ be the set of digits. Let $P=\{(i_1,j_1,i_2,j_2,i_3,j_3)\}$ be the set of paths of length three ($|P|=1460$), and let $T \subseteq \{(d_1,d_2,d_3)\in D^3: d_1 \not= 0\}$ be the set of digit triples to be covered. (The one- and two-digit numbers will take care of themselves if we cover $100=(1,0,0)$ through $199=(1,9,9)$.) For $(i,j)\in C$ and $d\in D$, let binary decision variable $x_{i,j,d}$ indicate whether cell $(i,j)$ contains digit $d$. For $p \in P$ and $t\in T$, let binary decision variable $y_{p,t}$ indicate whether path $p$ contains digit triple $t$. The constraints are: \begin{align} \sum_d x_{i,j,d} &= 1 &&\text{for $(i,j)\in C$} \tag1 \\ \sum_p y_{p,t} &\ge 1 &&\text{for all $t$} \tag2 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_1,j_1,d_1} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag3 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_2,j_2,d_2} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag4 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_3,j_3,d_3} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag5 \end{align} Constraint $(1)$ forces each cell to contain exactly one digit. Constraint $(2)$ forces each digit triple to appear at least once. Constraints $(3)$ through $(5)$ enforce that, if a path contains a digit triple, each cell in the path contains the corresponding digit.

The idea is to take $T$ to be a large set of consecutive numbers starting from $100$ and find a feasible solution. The one above came from $T=\{(d_1,d_2,d_3)\in D^3: d_1 \not= 0 \land 100d_1+10d_2+d_3 \le 396\}$.

397

$\begin{matrix}2&8&8&2&7&5\\6&1&3&7&5&3\\4&3&1&0&4&1\\2&9&5&8&2&4\\0&6&9&2&3&6\\3&0&1&7&6&1\\\end{matrix}$

I used integer linear programming as follows. Let $C=\{1,\dots,6\}^2$ be the set of cells, and let $D=\{0,\dots,9\}$ be the set of digits. Let $P=\{(i_1,j_1,i_2,j_2,i_3,j_3)\}$ be the set of paths of length three ($|P|=1460$), and let $T \subseteq \{(d_1,d_2,d_3)\in D^3: d_1 \not= 0\}$ be the set of digit triples to be covered. (The one- and two-digit numbers will take care of themselves if we cover $100=(1,0,0)$ through $199=(1,9,9)$.) For $(i,j)\in C$ and $d\in D$, let binary decision variable $x_{i,j,d}$ indicate whether cell $(i,j)$ contains digit $d$. For $p \in P$ and $t\in T$, let binary decision variable $y_{p,t}$ indicate whether path $p$ contains digit triple $t$. The constraints are: \begin{align} \sum_d x_{i,j,d} &= 1 &&\text{for $(i,j)\in C$} \tag1 \\ \sum_p y_{p,t} &\ge 1 &&\text{for all $t$} \tag2 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_1,j_1,d_1} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag3 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_2,j_2,d_2} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag4 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_3,j_3,d_3} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag5 \end{align} Constraint $(1)$ forces each cell to contain exactly one digit. Constraint $(2)$ forces each digit triple to appear at least once. Constraints $(3)$ through $(5)$ enforce that, if a path contains a digit triple, each cell in the path contains the corresponding digit.

The idea is to take $T$ to be a large set of consecutive numbers starting from $100$ and find a feasible solution. The one above came from $T=\{(d_1,d_2,d_3)\in D^3: d_1 \not= 0 \land 100d_1+10d_2+d_3 \le 396\}$, after fixing some of the digits in the 394 solution from @DmitryKamenetsky.

396

$\begin{matrix}2&6&6&2&7&5\\8&1&3&7&5&3\\4&3&1&0&4&1\\2&9&5&6&2&4\\0&8&9&2&3&8\\3&0&1&7&8&1\\\end{matrix}$

I used integer linear programming as follows. Let $C=\{1,\dots,6\}^2$ be the set of cells, and let $D=\{0,\dots,9\}$ be the set of digits. Let $P=\{(i_1,j_1,i_2,j_2,i_3,j_3)\}$ be the set of paths of length three ($|P|=1460$), and let $T \subseteq \{(d_1,d_2,d_3)\in D^3: d_1 \not= 0\}$ be the set of digit triples to be covered. (The one- and two-digit numbers will take care of themselves if we cover $100=(1,0,0)$ through $199=(1,9,9)$.) For $(i,j)\in C$ and $d\in D$, let binary decision variable $x_{i,j,d}$ indicate whether cell $(i,j)$ contains digit $d$. For $p \in P$ and $t\in T$, let binary decision variable $y_{p,t}$ indicate whether path $p$ contains digit triple $t$. The constraints are: \begin{align} \sum_d x_{i,j,d} &= 1 &&\text{for $(i,j)\in C$} \tag1 \\ \sum_p y_{p,t} &\ge 1 &&\text{for all $t$} \tag2 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_1,j_1,d_1} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag3 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_2,j_2,d_2} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag4 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_3,j_3,d_3} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag5 \end{align} Constraint $(1)$ forces each cell to contain exactly one digit. Constraint $(2)$ forces each digit triple to appear at least once. Constraints $(3)$ through $(5)$ enforce that, if a path contains a digit triple, each cell in the path contains the corresponding digit.

The idea is to take $T$ to be a large set of consecutive numbers starting from $100$ and find a feasible solution. The one above came from $T=\{(d_1,d_2,d_3)\in D^3: d_1 \not= 0 \land 100d_1+10d_2+d_3 \le 395\}$.

397

$\begin{matrix}2&8&8&2&7&5\\6&1&3&7&5&3\\4&3&1&0&4&1\\2&9&5&8&2&4\\0&6&9&2&3&6\\3&0&1&7&6&1\\\end{matrix}$

I used integer linear programming as follows. Let $C=\{1,\dots,6\}^2$ be the set of cells, and let $D=\{0,\dots,9\}$ be the set of digits. Let $P=\{(i_1,j_1,i_2,j_2,i_3,j_3)\}$ be the set of paths of length three ($|P|=1460$), and let $T \subseteq \{(d_1,d_2,d_3)\in D^3: d_1 \not= 0\}$ be the set of digit triples to be covered. (The one- and two-digit numbers will take care of themselves if we cover $100=(1,0,0)$ through $199=(1,9,9)$.) For $(i,j)\in C$ and $d\in D$, let binary decision variable $x_{i,j,d}$ indicate whether cell $(i,j)$ contains digit $d$. For $p \in P$ and $t\in T$, let binary decision variable $y_{p,t}$ indicate whether path $p$ contains digit triple $t$. The constraints are: \begin{align} \sum_d x_{i,j,d} &= 1 &&\text{for $(i,j)\in C$} \tag1 \\ \sum_p y_{p,t} &\ge 1 &&\text{for all $t$} \tag2 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_1,j_1,d_1} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag3 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_2,j_2,d_2} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag4 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_3,j_3,d_3} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag5 \end{align} Constraint $(1)$ forces each cell to contain exactly one digit. Constraint $(2)$ forces each digit triple to appear at least once. Constraints $(3)$ through $(5)$ enforce that, if a path contains a digit triple, each cell in the path contains the corresponding digit.

The idea is to take $T$ to be a large set of consecutive numbers starting from $100$ and find a feasible solution. The one above came from $T=\{(d_1,d_2,d_3)\in D^3: d_1 \not= 0 \land 100d_1+10d_2+d_3 \le 396\}$.

395

$\begin{matrix}2&6&6&2&5&0\\8&1&3&5&0&3\\4&3&1&7&4&1\\2&9&0&6&2&4\\7&8&9&2&3&8\\3&7&1&5&8&1\\\end{matrix}$

I used integer linear programming as follows. Let $C=\{1,\dots,6\}^2$ be the set of cells, and let $D=\{0,\dots,9\}$ be the set of digits. Let $P=\{(i_1,j_1,i_2,j_2,i_3,j_3)\}$ be the set of paths of length three ($|P|=1460$), and let $T \subseteq \{(d_1,d_2,d_3)\in D^3: d_1 \not= 0\}$ be the set of digit triples to be covered. (The one- and two-digit numbers will take care of themselves if we cover $100=(1,0,0)$ through $199=(1,9,9)$.) For $(i,j)\in C$ and $d\in D$, let binary decision variable $x_{i,j,d}$ indicate whether cell $(i,j)$ contains digit $d$. For $p \in P$ and $t\in T$, let binary decision variable $y_{p,t}$ indicate whether path $p$ contains digit triple $t$. The constraints are: \begin{align} \sum_d x_{i,j,d} &= 1 &&\text{for $(i,j)\in C$} \tag1 \\ \sum_p y_{p,t} &\ge 1 &&\text{for all $t$} \tag2 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_1,j_1,d_1} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag3 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_2,j_2,d_2} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag4 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_3,j_3,d_3} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag5 \end{align} Constraint $(1)$ forces each cell to contain exactly one digit. Constraint $(2)$ forces each digit triple to appear at least once. Constraints $(3)$ through $(5)$ enforce that, if a path contains a digit triple, each cell in the path contains the corresponding digit.

The idea is to take $T$ to be a large set of consecutive numbers starting from $100$ and find a feasible solution. The one above came from $T=\{(d_1,d_2,d_3)\in D^3: d_1 \not= 0 \land 100d_1+10d_2+d_3 \le 394\}$.

396

$\begin{matrix}2&6&6&2&7&5\\8&1&3&7&5&3\\4&3&1&0&4&1\\2&9&5&6&2&4\\0&8&9&2&3&8\\3&0&1&7&8&1\\\end{matrix}$

I used integer linear programming as follows. Let $C=\{1,\dots,6\}^2$ be the set of cells, and let $D=\{0,\dots,9\}$ be the set of digits. Let $P=\{(i_1,j_1,i_2,j_2,i_3,j_3)\}$ be the set of paths of length three ($|P|=1460$), and let $T \subseteq \{(d_1,d_2,d_3)\in D^3: d_1 \not= 0\}$ be the set of digit triples to be covered. (The one- and two-digit numbers will take care of themselves if we cover $100=(1,0,0)$ through $199=(1,9,9)$.) For $(i,j)\in C$ and $d\in D$, let binary decision variable $x_{i,j,d}$ indicate whether cell $(i,j)$ contains digit $d$. For $p \in P$ and $t\in T$, let binary decision variable $y_{p,t}$ indicate whether path $p$ contains digit triple $t$. The constraints are: \begin{align} \sum_d x_{i,j,d} &= 1 &&\text{for $(i,j)\in C$} \tag1 \\ \sum_p y_{p,t} &\ge 1 &&\text{for all $t$} \tag2 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_1,j_1,d_1} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag3 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_2,j_2,d_2} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag4 \\ y_{(i_1,j_1,i_2,j_2,i_3,j_3,d_1,d_2,d_3)} &\le x_{i_3,j_3,d_3} &&\text{for $(i_1,j_1,i_2,j_2,i_3,j_3)\in P$, $(d_1,d_2,d_3)\in T$} \tag5 \end{align} Constraint $(1)$ forces each cell to contain exactly one digit. Constraint $(2)$ forces each digit triple to appear at least once. Constraints $(3)$ through $(5)$ enforce that, if a path contains a digit triple, each cell in the path contains the corresponding digit.

The idea is to take $T$ to be a large set of consecutive numbers starting from $100$ and find a feasible solution. The one above came from $T=\{(d_1,d_2,d_3)\in D^3: d_1 \not= 0 \land 100d_1+10d_2+d_3 \le 395\}$.