Enigmatic Code

Programming Enigma Puzzles

Puzzle #15: Lines through the chessboard

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]

5 responses to “Puzzle #15: Lines through the chessboard

  1. Jim Randell 3 August 2019 at 11:44 am

    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×n grid. 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.

    • Jim Randell 13 August 2019 at 1:56 pm

      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.

  2. Robert Brown 4 August 2019 at 7:17 am

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

    • Robert Brown 4 August 2019 at 7:46 am

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

      • Jim Randell 4 August 2019 at 10:04 am

        @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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: