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.