Crazy Sheep Puzzle

All Solutions

by Neal R. Wagner

The Puzzle: At a Mensa conference they passed out a Crazy Sheep Puzzle: 16 squares to arrange in a 4-by-4 array so that adjoining squares represented the front and rear of a sheep using the same color. Evidently nobody at the conference was able to solve the puzzle (much harder than the standard 3-by-3 versions of this kind of puzzle), but someone gave the puzzle to my wife who worked on it and showed it to me. I was proud to have out-Mensaed them by solving it on a computer.

Below are pictures of the 16 pieces, scanned from my puzzle. In the pictures, there are 4 colors: white, black, brown, and gray. I numbered the pieces from 0 to 15. Note that 2 and 4 are the same, as are 10 and 11. The order in which the pieces are numbered was my own arbitrary choice. The pieces are arranged as shown in the rectangle below, with the white part pointing down, since white is the only color which occurs exactly once in each piece.

       +----+----+----+----+
Row 3: | 12 | 13 | 14 | 15 |
       +----+----+----+----+
Row 2: |  8 |  9 | 10 | 11 |
       +----+----+----+----+
Row 1: |  4 |  5 |  6 |  7 |
       +----+----+----+----+
Row 0: |  0 |  1 |  2 |  3 |
       +----+----+----+----+

For larger pictures, see Big Sheep.

Here is a formal definition of the pieces, where the sides are listed in counter-clockwise order:

Piece number  0:      white rear,  black front, brown front, gray  rear
Piece number  1:      white rear,  brown front, gray  front, black rear
Piece number  2 = 4:  white rear,  brown rear,  black front, gray  front
Piece number  3:      white rear,  brown rear,  gray  front, black front
Piece number  4 = 2:  white rear,  brown rear,  black front, gray  front
Piece number  5:      white rear,  gray  rear,  black front, gray  front
Piece number  6:      white rear,  black rear,  gray  front, brown front
Piece number  7:      white rear,  gray  rear,  black front, brown front
Piece number  8:      white front, gray  rear,  brown rear,  black front
Piece number  9:      white front, brown rear,  black rear,  gray  front
Piece number 10 = 11: white front, brown front, black rear,  gray  rear
Piece number 11 = 10: white front, brown front, black rear,  gray  rear
Piece number 12:      white front, gray  front, black rear,  brown rear
Piece number 13:      white front, gray  front, brown rear,  black rear
Piece number 14:      white front, black front, black rear,  gray  rear
Piece number 15:      white front, brown front, black rear,  brown rear

All 55 Solutions: Below is a table giving all 55 distinct solutions of the puzzle. In the table , the first four numbers are the pieces in the corners, with the lowest numbered one first, and the rest given in counter-clockwise order. These corner pieces were printed first to help eliminate duplicates in the list of solutions. The next number, in parentheses, gives the orientation of the first piece listed, which is in the lower left corner (position 0). Codes for the orientation are: 0 = white down, 1 = white left, 2 = white up, 3 = white right. Codes for the location of each piece are given in the table above, before the pictures:

The sixteen final numbers for each row give each number of the pieces in positions 0, 1, 2, 3, through 15, in the arrangement above. (Piece numbers 4 and 11 are not used in the table, but replaced by 2 and 10, respectively.) For each solution listed below, there are three other solutions that are rotations of the given solution by 90, 180, and 270. To get the solution, lay out the first piece in position 0 and in the proper orientation. Then each subsequent piece can be inserted, using its number, and choosing the orientation that makes it fit with earlier choices.

  +------------+----+-------------+-------------+-------------+-------------+
# |   Corners  |orie|     Row 0   |     Row 1   |     Row 2   |     Row 3   |
  +------------+----+-------------+-------------+-------------+-------------+
  | 0  3 15 12 |    |  0  1  2  3 |  4  5  6  7 |  8  9 10 11 | 12 13 14 15 |
  +------------+----+-------------+-------------+-------------+-------------+
1 | 0  9  2  6 |( 1)|  0  2 14  9 | 12  8  3 10 | 15  7 10  5 |  6 13  1  2 |
2 | 0  9  3  5 |( 3)|  0 12  7  9 |  1 10  2  8 | 13  2 15 14 |  5  6 10  3 |
3 | 0  9  3  5 |( 3)|  0 15  2  9 |  1 10  7  8 | 13  2 12 14 |  5  6 10  3 |
4 | 0  9  3  5 |( 3)|  0 15  7  9 |  1 10  2  8 | 13  2 10 14 |  5  6 12  3 |
5 | 0  9  3  6 |( 3)|  0 10  5  9 |  1 12  2  8 | 13  7 15 14 |  6  2 10  3 |
6 | 0  9  3  6 |( 3)|  0 12  5  9 |  1 10  2  8 | 13  2 15 14 |  6  7 10  3 |
7 | 0  9  3  6 |( 3)|  0 12  7  9 |  1 10  2  8 | 13  5 15 14 |  6  2 10  3 |
8 | 0  9  3  6 |( 3)|  0 15  2  9 |  1 10  7  8 | 13  5 12 14 |  6  2 10  3 |
9 | 0  9  3  6 |( 3)|  0 15  5  9 |  1 10  2  8 | 13  2 10 14 |  6  7 12  3 |
10| 0  9  3  6 |( 3)|  0 15  7  9 |  1 10  2  8 | 13  5 10 14 |  6  2 12  3 |
11| 0  9  3  7 |( 3)|  0 12  5  9 |  1 10  2  8 | 13  2 15 14 |  7  6 10  3 |
12| 0  9  3  7 |( 3)|  0 15  5  9 |  1 10  2  8 | 13  2 10 14 |  7  6 12  3 |
13| 0  9 12  3 |( 2)|  0  5  1  9 | 10 13  2 14 |  8  7 10  6 |  3 15  2 12 |
14| 0  9 13 10 |( 0)|  0 12  2  9 | 15  5 14  1 |  2 10  6  7 | 10  3  8 13 |
15| 0  9 13 10 |( 0)|  0 15  2  9 | 12  2 14  1 |  5 10  6  7 | 10  3  8 13 |
16| 0  9 13 15 |( 0)|  0 10  2  9 | 12  2 14  1 |  7 10  6  5 | 15  3  8 13 |
17| 0  9 15  3 |( 2)|  0  5  1  9 | 10 13  2 14 |  8  7 10  6 |  3 12  2 15 |
18| 1 12  2  9 |( 0)|  1 13  2 12 |  7 10  5 14 |  3  8 10  6 |  9  0 15  2 |
19| 1 14  5  9 |( 0)|  1 13  2 14 | 10  7 10  6 |  3  8 15  2 |  9  0 12  5 |
20| 2  3  9  7 |( 1)|  2  1 13  3 | 10  5 10  6 |  8 14  2 15 |  7 12  0  9 |
21| 2  5 12  6 |( 2)|  2  0 13  5 | 14 15  1 10 |  8  3  7  2 |  6  9 10 12 |
22| 2  5 12  9 |( 2)|  2  0 13  5 | 14 15  1 10 |  8  3  7  2 |  9  6 10 12 |
23| 2  6  2 10 |( 0)|  2 10  9  6 | 12  7  3  8 |  5  1 15 14 | 10 13  0  2 |
24| 2  6 14  8 |( 1)|  2  1 13  6 |  7 10  5 15 | 12  2 10  3 |  8  0  9 14 |
25| 2  8  5  9 |( 0)|  2 10  1  8 | 12  7 13 14 |  2 15  6  3 |  9  0 10  5 |
26| 2  9  2 10 |( 0)|  2 10  6  9 | 12  7  3  8 |  5  1 15 14 | 10 13  0  2 |
27| 2  9  6 10 |( 1)|  2 12  2  9 | 14  5 10  1 | 13  7 15  0 | 10  3  8  6 |
28| 2  9  7 12 |( 0)|  2 15  0  9 | 10  5  1  8 |  2 10 13 14 | 12  6  3  7 |
29| 2  9 12 13 |( 3)|  2 15  0  9 |  6 10  8  3 | 14  5 10  7 | 13  1  2 12 |
30| 2 10  6  5 |( 1)|  2 15  7 10 | 10  3  8 12 |  9 14  2  0 |  5  1 13  6 |
31| 2 10 12 15 |( 0)|  2  7  9 10 | 10  1 14  3 |  5 13  2  8 | 15  6  0 12 |
32| 2 10 15 12 |( 3)|  2 10  7 10 |  6 13  1  5 |  0  2 14  9 | 12  8  3 15 |
33| 2 13  6  9 |( 2)|  2  0  1 13 | 14 12  5 10 |  8  7 10  3 |  9  2 15  6 |
34| 2 13  6  9 |( 2)|  2  0  1 13 | 14 15  5 10 |  8  2 10  3 |  9  7 12  6 |
35| 2 13  6  9 |( 2)|  2  0  1 13 | 14 15  7 10 |  8  2 12  3 |  9  5 10  6 |
36| 2 15  6  5 |( 1)|  2 10  7 15 | 10  3  8 12 |  9 14  2  0 |  5  1 13  6 |
37| 2 15 10 12 |( 3)|  2 10  5 15 |  6 13  1  7 |  0  2 14  9 | 12  8  3 10 |
38| 3  5 10  9 |( 2)|  3  1 12  5 | 14 10  0 15 |  8  2  6  2 |  9  7 13 10 |
39| 3  5 10  9 |( 2)|  3  6  2  5 | 14 13 10 15 |  8  1  7  2 |  9  0 12 10 |
40| 3  5 10  9 |( 2)|  3  6 12  5 | 14 13  7 15 |  8  1 10  2 |  9  0  2 10 |
41| 3  5 10  9 |( 2)|  3 10  1  5 | 14 12  0 15 |  8  7  6  2 |  9  2 13 10 |
42| 3  5 10  9 |( 2)|  3 10  1  5 | 14 15  0 12 |  8  2  6  2 |  9  7 13 10 |
43| 3  5 10  9 |( 2)|  3 12  1  5 | 14 10  0 15 |  8  2  6  2 |  9  7 13 10 |
44| 3  7 10  9 |( 2)|  3  1 12  7 | 14 10  0 15 |  8  2  6  2 |  9  5 13 10 |
45| 3  7 10  9 |( 2)|  3 10  1  7 | 14 15  0 12 |  8  2  6  2 |  9  5 13 10 |
46| 3  7 10  9 |( 2)|  3 12  1  7 | 14 10  0 15 |  8  2  6  2 |  9  5 13 10 |
47| 3 10  5  9 |( 2)|  3  1 12 10 | 14 10  0  2 |  8  2  6 15 |  9  7 13  5 |
48| 3 10  5  9 |( 2)|  3  6  2 10 | 14 13 10  2 |  8  1  7 15 |  9  0 12  5 |
49| 3 10  5  9 |( 2)|  3  6 12 10 | 14 13  7  2 |  8  1 10 15 |  9  0  2  5 |
50| 3 10  5  9 |( 2)|  3 10  1 10 | 14 12  0  2 |  8  7  6 15 |  9  2 13  5 |
51| 3 10  5  9 |( 2)|  3 10  1 10 | 14 15  0  2 |  8  2  6 12 |  9  7 13  5 |
52| 3 10  5  9 |( 2)|  3 12  1 10 | 14 10  0  2 |  8  2  6 15 |  9  7 13  5 |
53| 3 10  7  9 |( 2)|  3  1 12 10 | 14 10  0  2 |  8  2  6 15 |  9  5 13  7 |
54| 3 10  7  9 |( 2)|  3 10  1 10 | 14 15  0  2 |  8  2  6 12 |  9  5 13  7 |
55| 3 10  7  9 |( 2)|  3 12  1 10 | 14 10  0  2 |  8  2  6 15 |  9  5 13  7 |
  +------------+----+-------------+-------------+-------------+-------------+

It took about six hours (during the course of two days) to write and debug the program that found all solutions, though I was a bit lucky. To an expert, this is a simple backtracking program, similar to "8 queens" and such. Even to me the biggest problem was deciding how to represent everything.

It required only a fraction of a second for the machine to find the first solution. The program used 314,152 position checks before reaching this first solution. All 55 solutions were found in a few minutes (twenty years ago), using 43,278,240 position checks.

Note that there are exactly two solutions with piece number 1 or 8 or 14 in a corner. All other pieces occur in a corner in more than two solutions.

A Picture of a Solution: One of two solutions with piece number 8 in a corner is below:

Solution # 24
For larger pictures, see Big Sheep.

C Program to Find the Solutions: C Program (.html), C Program + data (.pdf), C Program + data (.ps).

I wrote this a long time ago, and it is relatively straightforward as a backtracking program. The table of solutions shown above is not the direct result of running this program. Instead, the program's output was sorted and processed to eliminate duplicates. In fact, the raw output of the program is here: Output. This gives 880 solutions, but each solution is duplicated 16 times: 4 times for the four rotations, and 2 times for each of the two duplicate pieces. (Notice that solutions were generated by placing each of the 16 pieces in the first square, but solutions were displayed with the lowest numbered corner piece in the first square -- to make it easier to eliminate duplicates.)

More Pictures of Wins. For more wins see Winning Placements.