The following puzzles use a grid of on and off light bulbs. The illumination of each light bulb in the grid is determined by two other light bulbs: the bulb directly above it and the bulb directly to the right. The rules for obtaining the state of one light bulb given two others are as follows:

Each grid has a row of light bulbs along the top and a column of light bulbs along the right side. These light bulbs determine the illumination for the entire grid. Here's an example of how to combine the outer row and column to complete the grid.

For each puzzle, you are to determine the illumination of the outer row and column given the state of the light bulb grid. You are given the number of light bulbs that should be on and off along the outer edge. Unfortunately, someone has come along and removed most of the light bulbs in the grid, leaving only a few light bulbs to solve each puzzle. Can you still determine the illumination of the light bulbs in the outer row and column?

On = 1 bulb

Off = 5 bulbs

One way to solve this is to start with the outer row and column, make a guess as to the order of the on and off light bulbs, and then start filling in the grid to see if there is a contradiction.

Another way to solve the problem is to start by filling in the grid, making guesses as to what combinations of bulbs in the grid or on the outer edge would produce those already given in the grid. This is the technique used to produce the problem space tree below. (Not every possibility will be explored in each problem space tree, just the ones that are the most important.

Notice that by the time we get to the end, all but one of the possibilities are eliminated because they do not have the correct number of on and off light bulbs in the outer row and column. The single possibility left must be the solution.

For any bulb given in the grid, remember that there are always two possible combinations of bulbs that could produce it. For an off bulb, either two off bulbs or two on bulbs were combined. For an on bulb, one off and one on bulb are combined, but the on bulb might be on top, or it could be on the right.

Be sure to keep careful track of how many of each type of bulb is available for the outer edge. If you have a limited number of one type of bulb, use those sparingly.

Last Updated : March 23, 2008

"Knossos Games" — by

Copyright © 1993-2008 All Rights Reserved