Thursday, January 22, 2009

Dots and boxes puzzle

In the Dots Game, we start by drawing a grid of dots. Two players take turns drawing lines between adjacent dots. Whenever a player completes the forth side of a box, they get a point and an extra turn. You can play the Dots Game here.

I have a puzzle (of my own creation) which is inspired by the Dots game.

To explain the puzzle, let me define some new terms. A box is complete if all four of its sides have been drawn. A box is open if exactly three of its sides have been drawn. A grid of dots is saturated if it contains no open boxes or complete boxes, and if it is impossible to add any new lines without creating an open box. In other words, a grid is saturated if it is impossible to make a move without giving your opponent an opportunity to score.

The goal of this puzzle is to find the least number of lines necessary to saturate a 5 by 5 grid of dots. And if you're up for the challenge, try a 6 by 6 grid, and then a 7 by 7 grid.

Example: for a 4 by 4 grid of dots, only 8 lines are necessary:


Solutions have been posted.

7 comments:

miller said...

It is possible to do better than 16 lines in a 5 by 5 grid.

Eduard said...

Is this a joke? Are you asking for proof that 15 is impossible?

miller said...

No, I said it's possible to do it with 15, not impossible. And I do not expect any proofs.

Eduard said...

Okay. Her is a solution (use Courier font):

| |
- - - -
|
- -
|
- -
| | |

Eduard said...

Ascii Art is seriousely hampered by the suppression of leading and multiple blanks. So we have a new but easier puzzle.

miller said...

Well, I can see the solution regardless, by looking at the page source. Good job!

miller said...

You can add the extra spaces by using "&nbsp" with a semicolon at the end.

    |    |

However, this won't help much, since I don't think there's any way for you to use a monospaced font.

If anyone around here were html savvy enough, I'd love to give commenters the ability to use monospaced font tags and spoiler tags, but I have no idea how.