How many blocks can you pass through at most in a 10 × 10 grid.
The rules are:
- You cannot go over a line
- You cannot lift the pencil
- You cannot allow the blocks you have passed through to make a 2×2 block of adjacent boxes
I think it would be 71.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ It can be 75 in a sense that 100-(5*5) $\endgroup$– Haroon ArfanCommented Mar 23, 2020 at 21:09
-
3$\begingroup$ Excuse my humor - but you violated your own rules (no lifting the pencil - I see it happen at least 2 times ) g $\endgroup$– eagle275Commented Mar 24, 2020 at 13:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
I solved the problem via integer linear programming, and
71 is indeed optimal. Here's another optimal solution:
Here are optimal values for $n\times n$ grids with $n \le 10$: \begin{matrix} n &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 \\ \hline \text{maximum} &1 &3 &8 &12 &19 &25 &37 &45 &59 &71 \\ \end{matrix}
By the way, you lifted your pencil in row 1, column 4. :)
$\begingroup$
$\endgroup$
3
If diagonals are allowed, here is a solution with 75.
-
3$\begingroup$ OCD doesn't like your yellow dots not being all in order. $\endgroup$ Commented Mar 23, 2020 at 22:36
-
3$\begingroup$ @DanielMathias It was bothering me too that I started it like that. I have updated it to have a cleaner solution. $\endgroup$ Commented Mar 23, 2020 at 22:46
-
1$\begingroup$ Your solution offers up a maximum bound: since 1 out of every 4 squares has to be omitted, that means that the upper bound cannot be higher than 75%, which would be 75 out of the 100 boxes. $\endgroup$ Commented Mar 20, 2023 at 20:12