Editing Peg solitaire (section)

===Brute force attack on standard English peg solitaire===

The only place it is possible to end up with a solitary peg is the centre, or the middle of one of the edges; on the last jump, there will always be an option of choosing whether to end in the centre or the edge.

Following is a table over the number ('''P'''ossible '''B'''oard '''P'''ositions) of possible board positions after '''n''' jumps, and the possibility of the same peg moved to make a further jump ('''N'''o '''F'''urther '''J'''umps). Interesting to note is that the shortest way to fail the game is in six moves, and the solution (besides its rotations and reflections) is unique. An example of this is as follows: 4 → 16; 23 → 9; 14 → 16; 17 → 15; 19 → 17; 31 → 23. (In this notation, the pegs are numbered from left to right, starting with 0, and moving down each row and to the far left once each row is marked.)

'''NOTE: If one board position can be rotated and/or flipped into another board position, the board positions are counted as identical.'''
{{col-begin|width=auto}}
{{col-break}}
{| class="wikitable"
|-
! n || PBP || NFJ
|-
| 1 || 1 || 0
|-
| 2 || 2 || 0
|-
| 3 || 8 || 0
|-
| 4 || 39 || 0
|-
| 5 || 171 || 0
|-
| 6 || 719 || 1
|-
| 7 || 2,757 || 0
|-
| 8 || 9,751 || 0
|-
| 9 || 31,312 || 0
|-
| 10 || 89,927 || 1
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || PBP || NFJ
|-
| 11 || 229,614 || 1
|-
| 12 || 517,854 || 0
|-
| 13 || 1,022,224 || 5
|-
| 14 || 1,753,737 || 10
|-
| 15 || 2,598,215 || 7
|-
| 16 || 3,312,423 || 27
|-
| 17 || 3,626,632 || 47
|-
| 18 || 3,413,313 || 121
|-
| 19 || 2,765,623 || 373
|-
| 20 || 1,930,324 || 925
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || PBP || NFJ
|-
| 21 || 1,160,977 || 1,972
|-
| 22 || 600,372 || 3,346
|-
| 23 || 265,865 || 4,356
|-
| 24 || 100,565 || 4,256
|-
| 25 || 32,250 || 3,054
|-
| 26 || 8,688 || 1,715
|-
| 27 || 1,917 || 665
|-
| 28 || 348 || 182
|-
| 29 || 50 || 39
|-
| 30 || 7 || 6
|} 
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || PBP || NFJ
|-
| 31 || 2 || 2
|}
{{col-end}}

Since there can only be 31 jumps, modern computers can easily examine all game positions in a reasonable time.<ref name="solboard">{{cite web|author=<!--Not stated-->|date=2020-08-31|title=solboard|url=https://github.com/vsaugey/solboard|access-date=2020-08-31|website=github|quote=Implementation of brute force calculation of the Peg solitaire game}}</ref>

The above sequence "PBP" has been entered as [[oeis:A112737|A112737]] in [[On-Line Encyclopedia of Integer Sequences|OEIS]].  Note that the total number of reachable board positions (sum of the sequence) is 23,475,688, while the total number of possible board positions is 8,589,934,590 (33bit-1) (2^33), so only about 2.2% of all possible board positions can be reached starting with the center vacant.

It is also possible to generate all board positions. The results below have been obtained using
the [[mCRL2]] toolset (see the peg_solitaire example in the distribution).
{{col-begin|width=auto}}
{{col-break}}
{| class="wikitable"
|-
! n || PBP
|-
| 1 || 1
|-
| 2 || 4
|-
| 3 || 12
|-
| 4 || 60
|-
| 5 || 296
|-
| 6 || 1,338
|-
| 7 || 5,648
|-
| 8 || 21,842
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || PBP
|-
| 9 || 77,559
|-
| 10 || 249,690
|-
| 11 || 717,788
|-
| 12 || 1,834,379
|-
| 13 || 4,138,302
|-
| 14 || 8,171,208
|-
| 15 || 14,020,166
|-
| 16 || 20,773,236
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || PBP
|-
| 17 || 26,482,824
|-
| 18 || 28,994,876
|-
| 19 || 27,286,330
|-
| 20 || 22,106,348
|-
| 21 || 15,425,572
|-
| 22 || 9,274,496
|-
| 23 || 4,792,664
|-
| 24 || 2,120,101
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || PBP
|-
| 25 || 800,152
|-
| 26 || 255,544
|-
| 27 || 68,236
|-
| 28 || 14,727
|-
| 29 || 2,529
|-
| 30 || 334
|-
| 31 || 32
|-
| 32 || 5
|}
{{col-end}}

In the results below, it has generated all the board positions it '''really''' reached starting with the center vacant and finishing in the central hole.
{{col-begin|width=auto}}
{{col-break}}
{| class="wikitable"
|-
! n || Real
|-
| 1 || 1
|-
| 2 || 4
|-
| 3 || 12
|-
| 4 || 60
|-
| 5 || 292
|-
| 6 || 1,292
|-
| 7 || 5,012
|-
| 8 || 16,628
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || Real
|-
| 9 || 49,236
|-
| 10 || 127,964
|-
| 11 || 285,740
|-
| 12 || 546,308
|-
| 13 || 902,056
|-
| 14 || 1,298,248
|-
| 15 || 1,639,652
|-
| 16 || 1,841,556
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || Real
|-
| 17 || 1,841,556
|-
| 18 || 1,639,652
|-
| 19 || 1,298,248
|-
| 20 || 902,056
|-
| 21 || 546,308
|-
| 22 || 285,740
|-
| 23 || 127,964
|-
| 24 || 49,236
|}
{{col-break|gap=2em}}
{| class="wikitable"
|-
! n || Real
|-
| 25 || 16,628
|-
| 26 || 5,012
|-
| 27 || 1,292
|-
| 28 || 292
|-
| 29 || 60
|-
| 30 || 12
|-
| 31 || 4
|-
| 32 || 1
|}
{{col-end}}