21
$\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
    Jul 16 '20 at 22:12
  • $\begingroup$ Yes good point! I will remove that condition. $\endgroup$ Jul 16 '20 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
    Jul 16 '20 at 22:57
  • $\begingroup$ You can use computers if you wish - the problem is still difficult. $\endgroup$ Jul 17 '20 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
    Jul 20 '20 at 7:47
15
+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$ Jul 16 '20 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
    Jul 17 '20 at 4:14
  • 2
    $\begingroup$ Thanks. I thought this was the case as ILP is your favorite tool. $\endgroup$ Jul 17 '20 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
    Jul 17 '20 at 5:06
  • 1
    $\begingroup$ I don't know whether this solution is optimal. I will describe the full ILP formulation later. $\endgroup$
    – RobPratt
    Jul 17 '20 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$ Jul 20 '20 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
    Jul 20 '20 at 20:04
  • $\begingroup$ @Stiv agree this a great battle of wits. Why don't you join them? ;) $\endgroup$ Jul 21 '20 at 1:50
  • 2
    $\begingroup$ Are you using the same approach as RobPratt? If not, what is yours? $\endgroup$ Jul 22 '20 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
    Jul 27 '20 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$ Jul 27 '20 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
    Jul 27 '20 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$ Jul 16 '20 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$ Jul 16 '20 at 12:33
  • $\begingroup$ Nice. I have checked that your score is correct. $\endgroup$ Jul 16 '20 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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