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:
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.
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP