# Making longest line in 10 by 10 grid

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.

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

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

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

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

• OCD doesn't like your yellow dots not being all in order. – Daniel Mathias Mar 23 at 22:36
• @DanielMathias It was bothering me too that I started it like that. I have updated it to have a cleaner solution. – eyl327 Mar 23 at 22:46