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$
  • 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 at 22:12
  • $\begingroup$ Yes good point! I will remove that condition. $\endgroup$ – Dmitry Kamenetsky Jul 16 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 at 22:57
  • $\begingroup$ You can use computers if you wish - the problem is still difficult. $\endgroup$ – Dmitry Kamenetsky Jul 17 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 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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Great answer! Can you elaborate on your approach? $\endgroup$ – Dmitry Kamenetsky Jul 16 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 at 4:14
  • 2
    $\begingroup$ Thanks. I thought this was the case as ILP is your favorite tool. $\endgroup$ – Dmitry Kamenetsky Jul 17 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 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 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}$

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

As of now I have:

168

enter image description here

I may be able to squeeze a few more

| improve this answer | |
$\endgroup$
  • $\begingroup$ @daw start from one of the central 1s, go to an adjacent central 0, go diagonally to the other adjacent central 0. $\endgroup$ – Steven Stadnicki Jul 16 at 20:29
5
$\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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I was able to improve this by 1 just now. $\endgroup$ – RobPratt Jul 27 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$ – Dmitry Kamenetsky Jul 27 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 at 4:43
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}$

| improve this answer | |
$\endgroup$
  • $\begingroup$ Great start to the problem $\endgroup$ – Dmitry Kamenetsky Jul 16 at 12:33
  • $\begingroup$ Nice. I have checked that your score is correct. $\endgroup$ – Dmitry Kamenetsky Jul 16 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.