8
$\begingroup$

What is the minimum number of squares to be used to draw a 8x8 board which is divided into 64 unit squares.

  • The squares you are going to use can be of any size you want (see example below).
  • There will be no extra lines or draws outside the table when you are done!

Example for 3x3: First is drawn with 5 square, second is drawn with 4 squares.

Here is an example for 3x3

$\endgroup$
  • $\begingroup$ [logic-puzzle] is for a puzzle that uses ONLY logical deduction. [logic-grid] is for Einstein's Riddle-type puzzles with lists of clues like "the German man lives in the red house" and "None of the women have a pet fish". $\endgroup$ – Deusovi Feb 27 '16 at 22:10
7
$\begingroup$

The minimum number is 14 squares.

A solution with 14 squares it to place four 7x7 squares, four 6x6 squares, and four 5x5 squares touching the four corners of the boards, plus two 4x4 squares touching two opposite corners.

To show that 14 is optimal, consider the 28 segments that touch the outer edge of the board but don't lie on it. Any square covers a maximum of two of these segments: no square can reach two segments adjoining two opposite sides, if it touches two segments adjoining the same side, it can't reach any other segments. So, 14 squares are needed.

This also implies that in any 14-square solution, every square must touch the edge of the board, and the 8x8 square cannot be used.

$\endgroup$
5
$\begingroup$

Edit: I kept going back and forth between whether it should be 15 or 16 squares. I used color to convince myself that 15 does actually work. 1 is in the bottom left corner of a 8x8 square. All of the other numbers are the bottom left corners of a 4x4 square.

enter image description here

First consider that is is necessary for each of the number around the perimeter, 1,2,3,4,5,6,8,10,12 to have a square which has its lower left corner there. There are 18 lines in the image and each lower left corner can produce at most 2 of the lines. Additionally, only the number 1 spot can have an 8x8 square, all the rest must have smaller squares. This means that each square along the lower or left perimeter leaves partially complete lines and a second square must be added to complete the lines.

$\endgroup$
  • $\begingroup$ Couldn't you take out 16 and 1, and then add a square around the border? $\endgroup$ – Deusovi Feb 28 '16 at 1:07
  • $\begingroup$ @Deusovi, I flipped back and forth, between requiring 16 squares or 15 like you said. I thought there would be 2 segments missing with 15 squares, in the top middle and right middle, but now that I look at it again, I think it would all be covered. $\endgroup$ – Tony Ruth Feb 28 '16 at 3:52
  • $\begingroup$ the answer is less than 15. $\endgroup$ – Oray Feb 28 '16 at 10:20

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.