# Numerical Boggle

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.

• 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). – trolley813 Jul 16 at 22:12
• Yes good point! I will remove that condition. – Dmitry Kamenetsky Jul 16 at 22:55
• 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)? – TCooper Jul 16 at 22:57
• You can use computers if you wish - the problem is still difficult. – Dmitry Kamenetsky Jul 17 at 2:12
• 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? – klm123 Jul 20 at 7:47

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.

• Great answer! Can you elaborate on your approach? – Dmitry Kamenetsky Jul 16 at 23:59
• 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$. – RobPratt Jul 17 at 4:14
• Thanks. I thought this was the case as ILP is your favorite tool. – Dmitry Kamenetsky Jul 17 at 4:20
• 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? – justhalf Jul 17 at 5:06
• I don't know whether this solution is optimal. I will describe the full ILP formulation later. – RobPratt Jul 17 at 14:55

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}$$

• ooh nice work! This is getting closer to my solution. – Dmitry Kamenetsky Jul 20 at 16:07
• 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! – Stiv Jul 20 at 20:04
• @Stiv agree this a great battle of wits. Why don't you join them? ;) – Dmitry Kamenetsky Jul 21 at 1:50
• Are you using the same approach as RobPratt? If not, what is yours? – Andrew Savinykh Jul 22 at 3:52

As of now I have:

168

I may be able to squeeze a few more

• @daw start from one of the central 1s, go to an adjacent central 0, go diagonally to the other adjacent central 0. – Steven Stadnicki Jul 16 at 20:29

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.

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

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}$$

• Great start to the problem – Dmitry Kamenetsky Jul 16 at 12:33
• Nice. I have checked that your score is correct. – Dmitry Kamenetsky Jul 16 at 12:48