8
$\begingroup$

How many blocks can you pass through at most in a 10 × 10 grid.

The rules are:

  1. You cannot go over a line
  2. You cannot lift the pencil
  3. You cannot allow the blocks you have passed through to make a 2×2 block of adjacent boxes

I think it would be 71.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ It can be 75 in a sense that 100-(5*5) $\endgroup$ – Haroon Arfan Mar 23 at 21:09
  • 2
    $\begingroup$ Excuse my humor - but you violated your own rules (no lifting the pencil - I see it happen at least 2 times ) g $\endgroup$ – eagle275 Mar 24 at 13:16
9
$\begingroup$

I solved the problem via integer linear programming, and

71 is indeed optimal. Here's another optimal solution:

enter image description here

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. :)

| improve this answer | |
$\endgroup$
  • $\begingroup$ actually he lifted the pencil 2 times^^ 1 further lift in row 3 column 6 $\endgroup$ – eagle275 Mar 24 at 13:18
  • 1
    $\begingroup$ @eagle275, that one was a little ambiguous, so I didn't want to falsely accuse. :) $\endgroup$ – RobPratt Mar 24 at 14:47
8
$\begingroup$

If diagonals are allowed, here is a solution with 75.
grid

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ OCD doesn't like your yellow dots not being all in order. $\endgroup$ – Daniel Mathias Mar 23 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$ – eyl327 Mar 23 at 22:46

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.