21-110: Working systematically

Introduction

We often want to make a complete list of all of the different types of some object, or search for a solution to a puzzle by trial and error. A very helpful technique to follow in cases such as these is to work systematically. Unless the problem is especially simple, it will often save you a lot of frustration if you have a systematic way to record what you have done and to determine what to try next.

How I listed the 35 free hexominoes

I wanted to make a list of all 35 of the free hexominoes. How did I do it?

At first I just drew hexominoes more or less randomly. By the time I had about 20 of them, however, it was becoming rather difficult to make sure I wasn’t listing duplicates, and when I got stuck and couldn’t think of any more, I had no idea what kind of shapes I should be looking for.

Idea 1: Classifying hexominoes according to their longest line of squares

I realized that I needed a more systematic way of listing the hexominoes. So I started over, this time more carefully. I began with the hexomino consisting of six squares in a straight line:

Then I listed all the hexominoes having five squares in a straight line. This was pretty easy, because I only had to think of all the ways to add one square to a line of five. I got three more:

Next I listed all the hexominoes having four squares in a straight line. I did this by thinking of all the ways I could add two squares to a line of four. I found 12 more hexominoes like this:

Now, I could have moved on to listing all hexominoes having three squares in a straight line, but I thought, “If I do this, I am going to have to think of all the ways to add three squares to a line of three, and it seems that I have lost the advantage I had previously, where I had to add only a few squares to a basic ‘skeleton.’ But I think I have listed a lot of the hexominoes—it shouldn’t be very hard to figure out all the rest.” So I started listing hexominoes randomly again:

But it didn’t take long before I was stuck again, and as before I had no idea what I was missing. I needed a better idea.

Idea 2: Extending pentominoes

I reviewed my first idea, and I saw that the reason it was easy to list the hexominoes with five squares in a line was that I was adding only one square to a starting shape. So I tried to use this idea by thinking about adding one square to each of the 12 free pentominoes.

First I had to list the pentominoes. There are only 12 of these, so I was able to list them in a few minutes without requiring a systematic approach. The 12 free pentominoes are shown below, in the order I found them.

Then I examined each pentomino individually and considered all the ways to add a single square somewhere around its perimeter. Rather than restarting my list from scratch, I just added onto the list I found using my first idea. The first thing I discovered was that I had missed one of the hexominoes with four squares in a line!

It took me a while to work through all of the pentominoes, adding squares all the way around their perimeters, but I had a system to follow, and so I was never at a loss for what to do next. (It was still difficult to avoid duplicates, and a few of them slipped by before I caught them later.) My completed list of all 35 free polyominoes is shown below.

Idea 3: Classifying hexominoes by layers

A few days later I wanted a list of the free hexominoes again, but I was at school and had left my list at home. So I started with Idea 1 again, this time being more systematic about the polyominoes with three squares in a line. But when I got to 34 hexominoes, I couldn’t figure out what I was missing, so I tried a different idea.

I imagined each hexomino as made up of several layers, and then examined the various ways a hexomino could be formed in these ways. I decided that I would rotate each of the hexominoes so that the “long” dimension (when this made sense) would be horizontal. I made the following table.

Layers	Squares in each layer	Hexominoes
One	6
Two	1 + 5
	2 + 4
	3 + 3
Three	1 + 1 + 4
	1 + 2 + 3
	1 + 3 + 2
	1 + 4 + 1
	2 + 1 + 3
	2 + 2 + 2

After a bit of thought, I saw that it was impossible for a hexomino to have four layers along its “short” dimension, because six squares simply aren’t enough to make a polyomino measuring 4 × 4.

Note that I organized the table in a systematic way: first by the number of layers, then by the number of squares in each of the layers, from top to bottom. I didn’t have to include possibilities such as 3 + 2 + 1, because that’s the same as 1 + 2 + 3 (since these are free hexominoes). There is also a systematic way the hexominoes in each row are ordered (can you see it?), so that I could be sure I wasn’t missing any or listing any twice. I did not include the 2 × 3 rectangle () in the 2 + 2 + 2 row, because I had made the rule that all of my hexominoes should be oriented with their “long” dimension horizontal. The reason I created and followed all of these rules was that I wanted to avoid including duplicates, so I tried to make rules that would ensure that each free hexomino would be classified in only one row of the table. Then I could focus on avoiding duplicates within each row separately rather than in my entire list.

After I finished my table, I counted and found that I had listed 40 hexominoes! So apparently I had duplicates after all. Crossing out these duplicates gave me my final list. Can you find them? Do you see why these hexominoes appeared more than once in my table, despite my careful efforts to avoid duplicates? Can you think of an additional rule I could have followed to avoid this duplication?

Listing other polyominoes

The following table gives the number of polyominoes of the first few sizes. Can you use a systematic approach to list all of the free heptominoes? (This will take some work!)

Backtracking

Backtracking is a very useful approach to solving certain problems. It is essentially a systematic form of trial and error. The advantage of backtracking over random guessing is that backtracking gives you a way to keep track of the things you’ve tried so far and a guide for what you should try next.

The eight queens puzzle

Can you place eight queens on an 8 × 8 chessboard in such a way that no queen is attacking any other queen? (A queen on a chessboard can attack any piece on a square it can reach by moving in a straight line vertically, horizontally, or diagonally.)

A good way to solve this puzzle is by backtracking. Since we know that no two queens can occupy the same column, there must be one queen in each column. So we can start by placing a queen in the first square of the first column.

Next we want to place a queen somewhere in the second column. The position of the first queen makes some of the squares in the second column off limits, but there are six squares available for the second queen; we place the second queen in the first available square.

We can continue in this way, placing each queen in the first available square in the appropriate column (keeping in mind that the squares in each column are restricted by the positions of all previously placed queens). If we do this, we can fill up the first five columns:

But now we are stuck. There is no available square in the sixth column—every square in the sixth column is under attack by at least one of the five queens already on the board. So we backtrack. We undo the last thing we did, which was to place the fifth queen in the fourth row, and we try the next available option: placing it in the eighth row.

However, we have a problem again: there is still no place to put the sixth queen. Since we have exhausted all of the possibilities for the fifth queen (with the first four queens in their current positions), we backtrack, undoing the placement of the fourth queen, and trying the next possibility.

Now we can go as far as placing the seventh queen before we get stuck with no place to put the eighth:

Since we are stuck, we backtrack again, undoing the placement of the seventh queen, trying the next possibility, and continuing.

Can you continue this process to find a solution to the eight queens puzzle?

More applications of backtracking

Backtracking is often used to search for solutions to problems that require the arrangement or selection of objects according to certain rules. Here are a few types of puzzles that can be approached using a backtracking technique.

• Form a 6 × 10 rectangle from the 12 free pentominoes.
• Use tetrominoes (as many copies of each piece as you need) to tile a rectangular grid with some squares removed. There is a very cool “Tetris Tiler” at http://www.gfredericks.com/main/sandbox/tetris that does exactly this. Play around with it—when it gets stuck, you can see it backtracking.
• Find your way through the following maze (from http://www.xefer.com/maze-generator).

  

  (This maze generator will also solve the mazes it produces, using a backtracking technique. Try it!)
• Write the number 21110 as the sum of three squares (in other words, find three integers a, b, and c so that 21110 = a² + b² + c²).
• Fit words from a word list into a crossword grid (see Problem 6 on Homework 2).
• Solve the “knapsack problem” (see Problem 7 on Homework 2).
• Analyze the game of Tic-Tac-Toe. What is the best first move to make? What is the best second move?
• How many ways are there to tile a 2 × 3 checkerboard with fixed polyominoes, of any size? (There are 12 ways to tile a 2 × 2 checkerboard with fixed polyominoes.)

Back to the 21-110 page