### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,314)
- misc (3)
- project euler (2)
- puzzle (78)
- puzzle# (21)
- site news (54)
- tantalizer (80)
- teaser (7)

### Site Stats

- 217,165 hits

Programming Enigma Puzzles

3 August 2019

Posted by on **From New Scientist #3241, 3rd August 2019** [link] [link]

Linus is using a thin felt-tip pen and a ruler to draw straight lines on a conventional 8×8 chessboard. With eight lines, he can easily ensure that a line passes through every square on the board. For instance, he can just draw a line through the middle of each row of squares, which means each line would go through eight squares. But a line can pass through more than eight squares – for example, the one in the illustration goes through nine – so Linus wants to find a way to cut through all 64 squares with fewer than eight lines.

Can you help?

[puzzle#15]

%d bloggers like this:

If we consider a 3×3 grid, we can use two lines to pass through each square:

And we can extend this idea to larger grids. The line passing through the blue squares in the 3×3 grid, passes through the 3 squares in the middle row, but would also pass through blocks of three squares that were shifted horizontally by two squares and vertically by one square.

Here is a 5×5 grid using the same idea, that uses 4 lines to pass through each square:

And we see that the pattern can be extended to an

n×ngrid. We need(n – 2)lines to pass through each group of stepped 3×1 blocks, and then an extra line to to pass through the 4 red blocks in the corners of the grid, for a total of(n – 1)lines.So:

Solution:Here is a set of 7 straight lines that pass through each square of the 8×8 grid:The program I used to generate the diagrams is available here [ @repl.it ].

Note that while this method works for

n ≥ 3, it is not possible to touch each square of a 2×2 grid with 1 line, or a 1×1 grid with 0 lines.For a sneaky solution we could place the grid on a large cylinder, and then draw a single “straight” line (with respect to the cylinder), that spirals around and passes through each row. Thereby cutting each of the squares on the grid with a single line.

Interestingly, the published solution [link] claims: “In fact, it is always possible to draw lines through an N×N grid with no more than N−1 lines”. So either they have some clever solution when N=1 or 2, or they are assuming N ≥ 3.

Interesting that 6 blocks have 2 lines passing through them (could be coloured red?)

Oops – that should say 10 blocks! So 74 cuts altogether.

@Robert: The lines have a bit of wiggle room, so we can shift the line through the reds slightly so that it doesn’t pass through the centre point of the grid, and we get another square that is cut twice, to give us 11 in total, and 75 cuts altogether.