English Sixteen puzzle

The "English Sixteen" puzzle is peg jumping puzzle that is essentially a two-dimensional analogue of the Leaping Frogs puzzle. The board has two 3×3 grids of holes which share one corner hole. Initially the shared hole is empty, and the rest is filled with eight pegs of one colour in one half of the board and eight pegs of a second colour in the other half. You are allowed to shift a peg to an adjacent hole, or you can jump a peg over another if the hole is immediately behind that. The aim is to swap the colours, moving every peg to the other half of the board in as few moves as possible.

This puzzle is described in Professor Hoffman's "Puzzles Old and New" from 1893.

In some versions of the puzzle you are restricted in your movements by one or both of the following rules:

A peg is only allowed to shift/jump forwards, not backwards.
A peg may only jump a peg of the other colour, not one of the same colour.

These restrictions are essentially the same as draughts/checkers, so sometimes this version of the puzzle is played on a checkered board with pieces on the black squares.

		A1
	B1		B2
C1		C2		C3
	D1		D2
		E1
	F1		F2
G1		G2		G3
	H1		H2
		I1

Swap Squares is a version of the puzzle which starts with only 7 pieces in each half - the centre hole of each 3×3 grid is initially left empty. The same restrictions may be applied if you wish. Note that in this game it is possible to shift/jump one piece several times in succession. You may wish to count multiple consecutive shifts/jumps with one piece as a single move, or only count consecutive jumps as a single move.

If your browser supports JavaScript, then you can play the English Sixteen / Swap Squares puzzle by clicking the link below:

JavaScript English Sixteen / Swap Squares Puzzle

The number of positions, 16-peg game:

If there are no restrictions on the moves, then it is easy to calculate the number of positions. There are 17 holes, and 8 pegs of each colour, giving a total of 17!/8!² = 218,790 positions. If only forwards moves are allowed, then many of these positions are unreachable. It is difficult to calculate the number directly, but a full enumeration by computer showed there are 133,864 reachable positions.

Any direction

Forward only
Jump any colour

Forward only
Jump opposite colour

Depth	#positions
0	1
1	8
2	12
3	14
4	32
5	58
6	121
7	178
8	284
9	494
10	794
11	1,143
12	1,700
13	2,386
14	3,223
15	4,242
16	5,677
17	7,330
18	8,722
19	10,084
20	11,501
21	12,879
22	13,997
23	14,804

Depth	#positions
24	15,433
25	14,981
26	14,015
27	12,849
28	11,666
29	10,439
30	9,334
31	7,858
32	6,075
33	4,651
34	3,459
35	2,682
36	1,990
37	1,401
38	914
39	557
40	348
41	202
42	137
43	66
44	32
45	4
46	11
47	2
Total	218,790

Depth	#positions
0	1
1	8
2	12
3	14
4	24
5	44
6	65
7	88
8	132
9	190
10	328
11	472
12	664
13	1,002
14	1,426
15	1,948
16	2,633
17	3,484
18	4,420
19	5,360
20	6,516
21	7,684
22	8,589
23	9,447

Depth	#positions
24	10,080
25	10,267
26	9,956
27	9,314
28	8,231
29	7,002
30	6,078
31	5,110
32	3,875
33	2,948
34	2,138
35	1,518
36	1,061
37	757
38	430
39	255
40	144
41	76
42	40
43	24
44	4
45	4
46	1
Total	133,864

Depth	#positions
0	1
1	4
2	10
3	14
4	22
5	36
6	53
7	76
8	118
9	168
10	246
11	364
12	538
13	794
14	1,160
15	1,602
16	2,079
17	2,694
18	3,354
19	4,256
20	5,330
21	6,424
22	7,494
23	8,460

Depth	#positions
24	9,108
25	9,514
26	10,054
27	9,899
28	9,302
29	8,705
30	7,454
31	6,409
32	4,990
33	4,132
34	2,992
35	2,140
36	1,498
37	965
38	625
39	374
40	216
41	105
42	48
43	24
44	8
45	4
46	1
Total	133,864

The number of positions, 14-peg game:

In the 14 peg game, 7 pegs of each colour and 3 empty holes, giving 17!/(7!²3!) = 2,333,760 positions if there are no restrictions on the moves. If we restrict to forward moves only, then there are 2,071,392 reachable positions.

Every jump and shift counts as a move

Any direction

Forward only
Jump any colour

Forward only
Jump opposite colour

Depth	#positions
0	1
1	16
2	90
3	262
4	547
5	1,228
6	2,671
7	5,158
8	9,132
9	15,101
10	23,537
11	35,273
12	50,750
13	69,412
14	90,229
15	112,694
16	135,101
17	155,505
18	171,464
19	182,023

Depth	#positions
20	186,328
21	184,389
22	174,191
23	158,294
24	137,663
25	115,672
26	93,624
27	72,941
28	53,685
29	37,525
30	24,949
31	15,725
32	9,319
33	5,065
34	2,594
35	1,020
36	441
37	132
38	9
Total	2,333,760

Depth	#positions
0	1
1	12
2	48
3	96
4	159
5	348
6	815
7	1,672
8	3,304
9	6,195
10	10,967
11	18,650
12	30,436
13	46,728
14	67,445
15	91,498
16	116,713
17	140,337
18	159,307
19	171,645

Depth	#positions
20	177,471
21	176,398
22	167,361
23	151,684
24	131,266
25	109,025
26	87,616
27	67,647
28	49,642
29	34,505
30	22,571
31	13,979
32	8,184
33	4,307
34	2,104
35	846
36	319
37	88
38	3
Total	2,071,392

Depth	#positions
0	1
1	8
2	30
3	74
4	149
5	306
6	659
7	1,348
8	2,610
9	4,795
10	8,309
11	13,568
12	21,254
13	31,660
14	44,984
15	61,081
16	79,713
17	99,288
18	118,283
19	134,985
20	148,364
21	157,830

Depth	#positions
22	162,531
23	161,645
24	154,375
25	140,786
26	122,463
27	102,906
28	83,632
29	66,060
30	49,617
31	35,808
32	24,486
33	15,881
34	9,968
35	5,895
36	3,186
37	1,628
38	720
39	341
40	136
41	25
42	4
Total	2,071,392

Consecutive jumps with the same piece count as one move

Any direction

Forward only
Jump any colour

Forward only
Jump opposite colour

Depth	#positions
0	1
1	16
2	90
3	266
4	607
5	1,648
6	4,241
7	9,476
8	19,135
9	36,040
10	64,090
11	104,174
12	156,638

Depth	#positions
13	216,249
14	275,231
15	315,642
16	323,794
17	294,625
18	230,546
19	153,083
20	82,372
21	34,205
22	9,839
23	1,665
24	87
Total	2,333,760

Depth	#positions
0	1
1	12
2	48
3	100
4	183
5	468
6	1,197
7	2,860
8	6,856
9	15,437
10	33,209
11	64,740
12	113,747

Depth	#positions
13	179,156
14	250,086
15	306,156
16	325,380
17	297,053
18	224,970
19	142,555
20	71,708
21	27,203
22	7,231
23	946
24	86
25	4
Total	2,071,392

Depth	#positions
0	1
1	8
2	30
3	78
4	169
5	370
6	833
7	1,834
8	3,920
9	7,837
10	14,605
11	25,614
12	42,064
13	65,193
14	94,950
15	129,744

Depth	#positions
16	165,986
17	198,901
18	222,164
19	231,601
20	223,416
21	199,062
22	159,470
23	115,697
24	77,828
25	47,087
26	24,841
27	11,631
28	4,550
29	1,442
30	394
31	68
32	4
Total	2,071,392

Consecutive shifts and jumps with the same piece count as one move

Any direction

Forward only
Jump any colour

Forward only
Jump opposite colour

Depth	#positions
0	1
1	16
2	102
3	429
4	1,702
5	6,337
6	20,128
7	53,759
8	122,795

Depth	#positions
9	239,240
10	381,894
11	480,308
12	464,233
13	331,158
14	169,841
15	54,538
16	7,137
17	142
Total	2,333,760

Depth	#positions
0	1
1	12
2	52
3	166
4	579
5	2,024
6	7,011
7	22,343
8	62,174
9	144,427
10	275,035

Depth	#positions
11	413,490
12	472,113
13	384,971
14	205,664
15	66,412
16	12,236
17	2,110
18	459
19	96
20	17
Total	2,071,392

Depth	#positions
0	1
1	8
2	38
3	140
4	425
5	1,242
6	3,851
7	11,173
8	28,420
9	61,832
10	117,880

Depth	#positions
11	197,718
12	288,088
13	358,744
14	368,721
15	302,180
16	193,300
17	94,948
18	33,684
19	7,735
20	1,209
21	55
Total	2,071,392

Solution, 16-peg game:

Without the restrictive rules, the optimal solution is 46 moves (20 shifts and 26 jumps). Unsurprisingly, there are no backwards moves, so the first restriction makes no difference. More surprising is that there are such optimal solutions where jumps are only performed over pieces of the opposite colour. The second restriction therefore also makes no difference to the length of the shortest solution (although there are more optimal solutions if you do not impose the second restrictive rule).

Here is one of many 46 move solutions:

D2-E1 F1xD2 G1-F1 E1xG1 D1-E1 F2xD1 G3-F2 E1xG3 C3xE1 B2-C3 D1xB2 F2xD1 E1-F2 C3xE1 D2-C3 F1xD2 G2-F1 F2-G2 H1xF2 G1-H1 I1xG1 G3xI1 E1xG3 C1xE1 B1-C1 D2xB1 F1xD2 G1-F1 E1xG1 C1xE1 A1xC1 B1-A1 D2xB1 F1xD2 H2xF1 G3-H2 E1xG3 C1xE1 D1-C1 C2-D1 D2-C2 F1xD2 E1-F1 F2-E1 D1xF2 E1-D1

Solution, 14-peg game:

Suppose we only apply the first restrictive rule, so moves are only forwards, and there is no restriction on the colours of pieces we jump over. In this case there are solutions which are optimal whichever way you count the moves. It has 38 shifts/jumps, 24 moves when only consecutive jumps with the same piece are combined to one move, and 18 moves if consecutive shifts/jumps of the same piece are also combined.
Here is one such solution:

B1-C2 F1-E1 H2-G2 D2xF1xH2 G1-F1xD2xB1 C3-D2xF1 E1-F2 I1xG1xE1xC3 C1xE1xG1xI1 A1xC1xE1xG1 G3xE1xC1xA1 D1-E1 F2xD1-C1 B2xD1xF2-G3 H1xF2xD1xB2 C2-D1xF2xH1 G2-F2xD1 E1-F2

Allowing backwards moves does not allow for shorter solutions, except if you combine consecutive shifts/jumps of one piece. In that case, a 17 move solution is possible, for example:

F2-E1 D1xF2-G2 H1xF2xD1x-C2 B2xD1xF2xH1 C3-B2xD1xF2 E1-D1xB2 G1xE1-F1 A1xC3xE1xG1 G3xE1xC3xA1 H2-G3xE1xC3 D2-E1xG3-H2 I1xG3xE1-D2 C1xE1xG3xI1 B1-C1xE1xG3 F1-E1xC1 G2-F1 C2-B1

On the other hand if both rules are in effect (forward moves only, jumps only over opposite colour), then the solutions are all slightly longer - 41 shifts and jumps, 31 if consecutive jumps are combined, and 21 if consecutive jumps and shifts are combined. The solution below is optimal in the first two metrics, and the solution below that in the third metric. There is probably no single solution that is optimal in all three.

B1-C2 D1-E1 F2xD1 E1-F2 D2-E1 F1xD2xB2 F2-G2 H2xF1xD2 G3-F2 G1-F1 E1xG1 C1xE1xG3 G3-H2 C3xE1xG3 A1xC1xE1 B2-C3 D1-C1 F2xD1xB2 B2-A1 H1xF2xD1xB2 I1-H1 G1xI1 H1xF2xD1 E1-F2 C3xE1xG1 D2-C3 C2-D2 D2-E1 F1xD2 G2-H1 E1-D1

B1-C2 F2-E1 D1xF2-G2 C1-D1xF2 A1-B1-C1-D1 E1xC1-B1-A1 F1-E1xC1-B1 G1-F1-E1xC1 D2-E1-F1-G1 C3-D2-E1-F2 B2-C3-D2 G3xE1xC3-B2 H2-G3xE1xC3 F2-G3-H2 D2-E1-F2-G3 H1xF2-E1-D2 I1-H1xF2-E1 G2-H1-I1 D1xF2-G2-H1 C2-D1xF2 E1-D1

Jaap's Puzzle Page

English Sixteen / Swap Squares

JavaScript English Sixteen / Swap Squares Puzzle

The number of positions, 16-peg game:

The number of positions, 14-peg game:

Solution, 16-peg game:

Solution, 14-peg game: