23
$\begingroup$

You are probably familiar with the word game Boggle, where you need to construct words by concatenating letters from a grid. Here we will play a numerical version of the game. The rules are as follows:

  • Create a 6x6 grid of digits. Each cell must contain a single digit from 0 to 9.
  • Starting in one cell you collect digits as you move to neighboring cells (in all 8 directions). As the digits are collected they are concatenated left to right, to form a single number. Note that the starting digit is collected too and you can revisit cells.

Your task is to create a 6x6 grid of digits, such that the smallest positive number that cannot be constructed is as large as possible.

$\endgroup$
7
  • 1
    $\begingroup$ Actually the "Numbers cannot start with a 0" condition is redundant, because it would be never necessary to do so (the leading 0s can be dropped). $\endgroup$
    – trolley813
    Commented Jul 16, 2020 at 22:12
  • $\begingroup$ Yes good point! I will remove that condition. $\endgroup$ Commented Jul 16, 2020 at 22:55
  • 1
    $\begingroup$ Great question. I was expecting the answers to quickly hit the 10,000's+, clearly I haven't given it enough thought yet. Is there an invisible no computer tag here? Or may I answer with an algorithmic approach(assuming I can even work one out)? $\endgroup$
    – TCooper
    Commented Jul 16, 2020 at 22:57
  • $\begingroup$ You can use computers if you wish - the problem is still difficult. $\endgroup$ Commented Jul 17, 2020 at 2:12
  • $\begingroup$ Do you collect digits one by one moving in 1 of the 8 directions? Or you somehow move in all 8 directions at the same time? $\endgroup$
    – klm123
    Commented Jul 20, 2020 at 7:47

5 Answers 5

16
+50
$\begingroup$

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.

$\endgroup$
17
  • 1
    $\begingroup$ Great answer! Can you elaborate on your approach? $\endgroup$ Commented Jul 16, 2020 at 23:59
  • 3
    $\begingroup$ I'm using integer linear programming, where the main decisions are represented by binary variables $x_{i,j,k}$ that indicate whether cell $(i,j)$ contains value $k$. $\endgroup$
    – RobPratt
    Commented Jul 17, 2020 at 4:14
  • 2
    $\begingroup$ Thanks. I thought this was the case as ILP is your favorite tool. $\endgroup$ Commented Jul 17, 2020 at 4:20
  • 2
    $\begingroup$ Haha, you always amaze me with your application of ILP in various places RobPratt. Have a +1. Can you describe more what you mean by using binary variables $x_{i,j,k}$ to make decision? Don't we need some sort of sequence in the mix? $\endgroup$
    – justhalf
    Commented Jul 17, 2020 at 5:06
  • 1
    $\begingroup$ I don't know whether this solution is optimal. I will describe the full ILP formulation later. $\endgroup$
    – RobPratt
    Commented Jul 17, 2020 at 14:55
9
$\begingroup$

Edit: Here is a new and improved answer of

337

As follows

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

$\endgroup$
4
  • $\begingroup$ ooh nice work! This is getting closer to my solution. $\endgroup$ Commented Jul 20, 2020 at 16:07
  • 1
    $\begingroup$ I'm enjoying watching this puzzling tennis match between you and @RobPratt - just waiting for one of you to smash down an ace to finish the rally! $\endgroup$
    – Stiv
    Commented Jul 20, 2020 at 20:04
  • $\begingroup$ @Stiv agree this a great battle of wits. Why don't you join them? ;) $\endgroup$ Commented Jul 21, 2020 at 1:50
  • 2
    $\begingroup$ Are you using the same approach as RobPratt? If not, what is yours? $\endgroup$ Commented Jul 22, 2020 at 3:52
7
$\begingroup$

I have found

394

with this grid

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

I used a hill climbing algorithm that changes one value at a time. It accepts a move if it increases (or equals) the score, otherwise it rejects it. After all possible changes have been tried, it adds some random mutations and restarts the process. I ran multiple processes of this method for about a week and it only found this grid once. Hence I am not convinced that this solution is optimal.

It was a fun problem and I thank everyone for participating. I got the idea from this competition and I encourage you to check it out.

UPDATE:

I have improved my algorithm and was able to get a higher score of

399

with this grid

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

Note if we can make 399, then we will also get 400 to 405 for free.

$\endgroup$
3
  • $\begingroup$ I was able to improve this by 1 just now. $\endgroup$
    – RobPratt
    Commented Jul 27, 2020 at 4:02
  • $\begingroup$ Wow cool! Your solution looks quite different though. I am guessing you initialized your variables with my solution first and then ran your optimization? $\endgroup$ Commented Jul 27, 2020 at 4:34
  • $\begingroup$ Yes, one of my improvement heuristics for a given solution is to fix all occurrences of a subset of digits and optimize the rest. $\endgroup$
    – RobPratt
    Commented Jul 27, 2020 at 4:43
5
$\begingroup$

As of now I have:

168

enter image description here

I may be able to squeeze a few more

$\endgroup$
1
  • $\begingroup$ @daw start from one of the central 1s, go to an adjacent central 0, go diagonally to the other adjacent central 0. $\endgroup$ Commented Jul 16, 2020 at 20:29
4
$\begingroup$

No guarantees of optimality, but I'll start us off with a score of

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

$\endgroup$
2
  • $\begingroup$ Great start to the problem $\endgroup$ Commented Jul 16, 2020 at 12:33
  • $\begingroup$ Nice. I have checked that your score is correct. $\endgroup$ Commented Jul 16, 2020 at 12:48

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.