TransWikia.com

Numerical Boggle

Puzzling Asked on September 4, 2021

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 6×6 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 6×6 grid of digits, such that the smallest positive number that cannot be constructed is as large as possible.

5 Answers

I have found

with this grid

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

with this grid

Answered by Dmitry Kamenetsky on September 4, 2021

Edit: Here is a new and improved answer of

As follows

Answered by hexomino on September 4, 2021

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 $din D$, let binary decision variable $x_{i,j,d}$ indicate whether cell $(i,j)$ contains digit $d$. For $p in P$ and $tin 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.

Answered by RobPratt on September 4, 2021

As of now I have:

I may be able to squeeze a few more

Answered by TheGuy23 on September 4, 2021

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

Answered by AxiomaticSystem on September 4, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP