CEMC Banner

Problem of the Week
Problem A and Solution
Mixed Up Letters

Problem

The letters A, B, C, D, E, F, G, H, and I each appear in one of the nine squares of the grid below.

     
     
     

What is the correct arrangement of these letters in the grid that satisfies all the clues above?

Solution

We will first give the final grid. There are a number of different ways to get to this answer. On the next page, we will give one possible solution.

A F C
H D E
B I G

Since D is in the middle square, then F must be in the square in the top middle of the grid. Since C is to the right of F, then C must be in the top right corner of the grid. We add these to the grid.

     F C
  D  
     

Since A is in a top corner, and C is in the top right corner, then A must be the top left corner. Now we know where A is, we know that H appears below A and B appears below H in the first column. We add these to the grid.

A F C
H D  
B    

Since I is between B and G, and B is to the left of I, now we know these letters appear in the bottom row. We add these to the grid.

A F C
H D
B I G

Since we know that G is directly below E, this means that E is directly above G. This will finish the third column and the grid.

A F C
H D E
B I G

Teacher’s Notes

Solving a problem like this one is good practice in computational thinking, which is an essential skill in mathematics and computer science. We might ask ourselves, can a computer solve this type of problem, and if so what is the procedure it would use?

One way a computer could solve this problem is through brute force. This means that the computer would try every possible arrangement of letters in the grid until it finds one arrangement that satisfies the rules. It could start by putting the letters in order

Row 1: A, B, C
Row 2: D, E, F
Row 3: G, H, I

but you find out that this arrangement does not work for several reasons.

Then you can try

Row 1: B, A, C
Row 2: D, E, F
Row 3: G, H, I

and again you find out this arrangement violates one or more of the rules.

It turns out that there are 362 880 possible arrangements of these 9 letters to consider. Even though this is a relatively small problem, a brute force solution becomes a pretty big task. In general brute force solutions are considered unusable for problems of any reasonable size, so computer scientists look for alternative techniques or look for ways to reduce the number of arrangements that need to be checked in this kind of search. Reducing the search space is called pruning. Techniques that a computer would use to solve a problem like this one are used in artificial intelligence and machine learning.