Peg Solitaire, Solo Noble, Solo Goli, Marble Solitaire or simply Solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known as solitaire in Britain and as peg solitaire in the US where 'solitaire' is now the common name for patience.
The first evidence of the game can be traced back to the court of Louis XIV, and the specific date of 1697, with an engraving made ten years later by Claude Auguste Berey of Anne de Rohan-Chabot, Princess of Soubise, with the puzzle by her side. The August 1697 edition of the French literary magazine Mercure galant contains a description of the board, rules and sample problems. This is the first known reference to the game in print.
The standard game fills the entire board with pegs except for the central hole. The objective is, making valid moves, to empty the entire board except for a solitary peg in the central hole.
Board
English solitaire board
European peg solitaire board
There are two traditional boards ('.' as an initial peg, 'o' as an initial hole):
Playing Peg solitaireMan playing triangular peg solitaire
A valid move is to jump a peg orthogonally over an adjacent peg into a hole two positions away and then to remove the jumped peg.
In the diagrams which follow, · indicates a peg in a hole, * emboldened indicates the peg to be moved, and o indicates an empty hole. A blue ¤ is the hole the current peg moved from; a red * is the final position of that peg, a red o is the hole of the peg that was jumped and removed.
Thus valid moves in each of the four orthogonal directions are:
* · o → ¤o*Jump to right
o · * → *o¤Jump to left
*¤
· → oJump down
o *
o *
· → oJump up*¤
On an English board, the first three moves might be:
There are many different solutions to the standard problem, and one notation used to describe them assigns letters to the holes (although numbers may also be used):
English European
a b c a b c
d e f y d e f z
g h i j k l m g h i j k l m
n o p x P O N n o p x P O N
M L K J I H G M L K J I H G
F E D Z F E D Y
C B A C B A
This mirror image notation is used, amongst other reasons, since on the European board, one set of alternative games is to start with a hole at some position and to end with a single peg in its mirrored position. On the English board the equivalent alternative games are to start with a hole and end with a peg at the same position.
There is no solution to the European board with the initial hole centrally located, if only orthogonal moves are permitted. This is easily seen as follows, by an argument from Hans Zantema. Divide the positions of the board into A, B and C positions as follows:
A B C
A B C A B
A B C A B C A
B C A B C A B
C A B C A B C
B C A B C
A B C
Initially with only the central position free, the number of covered A positions is 12, the number of covered B positions is 12, and also the number of covered C positions is 12. After every move the number of covered A positions increases or decreases by one, and the same for the number of covered B positions and the number of covered C positions. Hence after an even number of moves all these three numbers are even, and after an odd number of moves all these three numbers are odd. Hence a final position with only one peg cannot be reached, since that would require that one of these numbers is one (the position of the peg, one is odd), while the other two numbers are zero, hence even.
There are, however, several other configurations where a single initial hole can be reduced to a single peg.
A tactic that can be used is to divide the board into packages of three and to purge (remove) them entirely using one extra peg, the catalyst, that jumps out and then jumps back again. In the example below, the * is the catalyst.:
* · o ¤o* o * · *o¤
· → · → o → o
· · ¤ o
This technique can be used with a line of 3, a block of 2·3 and a 6-peg L shape with a base of length 3 and upright of length 4.
Other alternate games include starting with two empty holes and finishing with two pegs in those holes. Also starting with one hole here and ending with one peg there. On an English board, the hole can be anywhere and the final peg can only end up where multiples of three permit. Thus a hole at a can only leave a single peg at a, p, O or C.
Studies on peg solitaire
A thorough analysis of the game is known.[1] This analysis introduced a notion called pagoda function which is a strong tool to show the infeasibility of a given generalized peg solitaire problem.
A solution for finding a pagoda function, which demonstrates the infeasibility of a given problem, is formulated as a linear programming problem and solvable in polynomial time.[2]
A paper in 1990 dealt with the generalized Hi-Q problems which are equivalent to the peg solitaire problems and showed their NP-completeness.[3]
A 1996 paper formulated a peg solitaire problem as a combinatorial optimization problem and discussed the properties of the feasible region called 'a solitaire cone'.[4]
In 1999 peg solitaire was completely solved on a computer using an exhaustive search through all possible variants. It was achieved making use of the symmetries, efficient storage of board constellations and hashing.[5]
In 2001 an efficient method for solving peg solitaire problems was developed.[2]
An unpublished study from 1989 on a generalized version of the game on the English board showed that each possible problem in the generalized game has 29 possible distinct solutions, excluding symmetries, as the English board contains 9 distinct 3×3 sub-squares. One consequence of this analysis is to put a lower bound on the size of possible "inverted position" problems, in which the cells initially occupied are left empty and vice versa. Any solution to such a problem must contain a minimum of 11 moves, irrespective of the exact details of the problem.
It can be proved using abstract algebra that there are only 5 fixed board positions where the game can successfully end with one peg.[6]
Solutions to the English game
Interactive solution guide for English Peg Solitaire.
The shortest solution to the standard English game involves 18 moves, counting multiple jumps as single moves:
P-f D-P G-I J-H
· · o · · o · · o · · o
· o * · o · · o · · o ·
· · · · o o · · · · · o o · · · · · o o · · · · · o o ·
· · · · ¤ · · · · · · * · · · · · · · · · · · · · · · ·
· · · · · · · · · · · o · · · · · · *o¤ · · · ¤o* o
· · · · · ¤ · · o · · o
· · · · · · · · · · · ·
m-G-I i-k g-i L-J-H-l-j-h
· · o · · o · · o · · o
· o · · o · · o · · o ·
· · · · o o ¤ · · ¤o* o o ¤o* o · o o o *oooo o
· · · · · · o · · · · · · o · · · · · · o · · · · · o o
· · · o *oo · · · o · o o · · · o · o o · ¤oooo o
· · o · · o · · o · · o
· · · · · · · · · · · ·
C-K p-F A-C-K M-g-i
· · o · · o · · o · · o
· o · · o · · o · · o ·
o · o o o o o o · o o o o o o · o o o o o oo* o o o o
· · · · · o o · · ¤ · · o o · · o · · o o o · o · · o o
· o * o o o o · o o o o o o · o * o o o o ¤ o · o o o o
o · o * · o o · o o · o
¤ · · o · · oo¤ o o o
a-c-k-I d-p-F-D-P-p o-x
¤oo o o o o o o
· o o¤ o o o o o
o o · o o o o o o o o o o o o o o o o o o
o · o · o o o o · *oo o o o ¤o* o o o
o o · o * o o o o o o o o o o o o o o o o
o · o ooo o o o
o o o o o o o o o
The order of some of the moves can be exchanged. Note that if you instead think of * as a hole and o as
a peg, you can solve the puzzle by following the solution in reverse, starting from the last picture, going
towards the first. However, this requires more than 18 moves.
This solution was found in 1912 by Ernest Bergholt and proven to be the shortest possible by John Beasley in 1964.[7]
An easily remembered solution of first clearing edges by focusing on the holes circled in white – in figure 1, pegs are labelled in the order they are removed
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 (Possible Board Positions) of possible board positions after n jumps, and the possibility of the same peg moved to make a further jump (No Further Jumps). 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.
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
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
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
n
PBP
NFJ
31
2
2
Since there can only be 31 jumps, modern computers can easily examine all game positions in a reasonable time.[8]
The above sequence "PBP" has been entered as A112737 in 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).
n
PBP
1
1
2
4
3
12
4
60
5
296
6
1,338
7
5,648
8
21,842
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
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
n
PBP
25
800,152
26
255,544
27
68,236
28
14,727
29
2,529
30
334
31
32
32
5
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.
n
Real
1
1
2
4
3
12
4
60
5
292
6
1,292
7
5,012
8
16,628
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
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
n
Real
25
16,628
26
5,012
27
1,292
28
292
29
60
30
12
31
4
32
1
Solutions to the European game
There are 3 initial non-congruent positions that have solutions.[9] These are:
Peg solitaire has been played on other size boards, although the two given above are the most popular. It has also been played on a triangular board, with jumps allowed in all 3 directions. As long as the variant has the proper "parity" and is large enough, it will probably be solvable.
Peg solitaire game board shapes: (1) French (European) style, 37 holes, 17th century; (2) J. C. Wiegleb, 1779, Germany, 45 holes; (3) Asymmetrical 3-3-2-2 as described by George Bell, 20th century;[10] (4) English style (standard), 33 holes; (5) Diamond, 41 holes; (6) Triangular, 15 holes. Grey = the hole for the survivor.
A common triangular variant has five pegs on a side. A solution where the final peg arrives at the initial empty hole is not possible for a hole in one of the three central positions. An empty corner-hole setup can be solved in ten moves, and an empty midside-hole setup in nine (Bell 2008):
Shortest solution to triangular variant
* = peg to move next;
¤ = hole created by move;
o = jumped peg removed;
* = hole filled by jumping;
· · · *¤
· · · · · · · *o¤
· · · · · · * · · ¤ · · *o ·
· · · · · · · · · · · · · o · · ** · ** · o · · ¤o** · o *o¤ · o · * o · o · · o ·
o o o o o
****¤¤ o o o o
o o o o ** o oo o o * o o ¤¤ · · ¤ o oo o o o ** o o · o o o o o
o ** o · o ¤¤ o · o o o o * o o o o ¤ o o * o o
Video game
On June 26, 1992, a video game based on peg solitaire was released for the Game Boy. Titled simply Solitaire, the game was developed by Hect. In North America, DTMC released the game as Lazlos' Leap.
In popular culture
The PC game Shivers, a horror-themed point and click puzzle game, features many puzzles/games for the player to complete. The puzzle dubbed "Chinese Checkers" is actually peg solitaire.
Cracker Barrel features the game at every table at their locations. The board featured is triangular with 15 total holes.
In Cowboy Bebop: The Movie, the main antagonist, Vincent Volaju, spends most of his free time playing peg solitaire. The vector
for his planned Bioterrorism attack, a type of nanobot, is stored in peg solitaire marbles.
^ abKiyomi, M.; Matsui, T. (2001), "Integer Programming Based Algorithms for Peg Solitaire Problems", Proc. 2nd Int. Conf. Computers and Games (CG 2000): Integer programming based algorithms for peg solitaire problems, Lecture Notes in Computer Science, vol. 2063, pp. 229–240, CiteSeerX10.1.1.65.6244, doi:10.1007/3-540-45579-5_15, ISBN978-3-540-43080-3
^Uehara, R.; Iwata, S. (1990). "Generalized Hi-Q is NP-complete". Trans. IEICE. 73: 270–273.
^Avis, D.; Deza, A. (2001), "On the solitaire cone and its relationship to multi-commodity flows", Mathematical Programming, 90 (1): 27–57, doi:10.1007/PL00011419, S2CID7852133
^Eichler; Jäger; Ludwig (1999), c't 07/1999 Spielverderber, Solitaire mit dem Computer lösen (in German), vol. 7, p. 218
Sir Richard DollRichard Doll in 2002Lahir(1912-10-28)28 Oktober 1912Hampton, Middlesex, InggrisMeninggal24 Juli 2005(2005-07-24) (umur 92)Oxford, InggrisKebangsaanInggrisAlmamaterKolese King's LondonDikenal atasEpidemiologi merokok, model Armitage–DollPenghargaanPenghargaan Internasional Yayasan Gairdner (1970)Medali Buchanan (1972)Penghargaan Charles S. Mott (1979)Medali Royal (1986)Penghargaan Pangeran Mahidol (1992)Penghargaan Shaw(2004)Penghargaan Internasional Raja Faisal(2005)Ka...
Concept in Turkish ethnic nationalism Erdoğan and Abbas with actors representing the 16 Great Turkic Empires (2015)[1] Flags of the 16 Great Turkish Empires displayed in the Istanbul Military Museum The 16 Great Turkic Empires (Turkish: 16 Büyük Türk Devleti, which translates as 16 Great Turkic States) is a concept in Turkish ethnic nationalism, introduced in 1969 by Akib Özbek, map officer[2] and widely invoked by Turkish authorities during the 1980s, under the governmen...
Al Capone, seorang gangster. Gangster adalah kriminal yang merupakan anggota organisasi kejahatan pembuat kekacauan, seperti geng. Istilah gangster digunakan untuk merujukan anggota organisasi kriminal yang berhubungan dengan Mafia, seperti Chicago Outfit dan Five Families, dan individu seperti Al Capone dan Bugsy Siegel. Artikel bertopik sosiologi ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.lbs
For related races, see 1896 United States gubernatorial elections. 1896 West Virginia gubernatorial election ← 1892 November 3, 1896 1900 → Nominee George W. Atkinson Cornelius Clarkson Watts Party Republican Democratic Popular vote 105,588 93,558 Percentage 52.41% 46.44 Governor before election William A. MacCorkle Democratic Elected Governor George W. Atkinson Republican Elections in West Virginia Federal government Presidential elections 1864 1868 1872 18...
لمعانٍ أخرى، طالع قائمة نهائيات كأس السوبر الأفريقي. كأس السوبر الإفريقي مارس 2019الحدثكأس السوبر الأفريقي الترجي التونسي الرجاء البيضاوي 1 2 التاريخ29 مارس 2019 (2019-03-29)الملعباستاد ثاني بن جاسم، الدوحةالحكمباملاك تيسيما وييسا (إثيوبيا) → 2018 2020 (فبراير) ← كأس الس�...
Untuk doktrin serupa dalam denominasi Kristen lainnya, lihat Meterai Pengakuan. Bagian dari seri Gereja Katolik tentangTobat dan Rekonsiliasi Sakramen Tobat dan Rekonsiliasi Penyesalan Meterai Pengakuan Misericordia Dei Reconciliatio et paenitentia Penyangkalan dan Pemulihan Petrus Penitensiaria Apostolik Lamentabili sane exitu Portal Katoliklbs Bagian dari seri tentangHukum KanonikGereja Katolik Hukum Mutakhir Kitab Hukum Kanonik 1983 Omnium in mentem Kitab Hukum Kanon Gereja-Gerej...
Idillio villereccioOpera teatrale in tre atti Fotografia di George Bernard Shaw (1934) AutoreGeorge Bernard Shaw Titolo originaleVillage Wooing Lingua originaleInglese GenereCommedia Composto nel1933 Prima assolutaDallas, 16 aprile 1934Little Theatre Personaggi A Z Manuale Idillio villereccio (Village Wooing) è una commedia a due voci in tre atti di George Bernard Shaw, scritta nel 1933, rappresentata per la prima volta nel 1934 Indice 1 Trama 2 Rappresentazioni 3 Edizioni 4 Note...
Negeri Kesultanan Serdang Darul Arifﻛﺴﻠﺘﺎﻧﻦ سردڠ1723–Sekarang Bendera Lambang Wilayah Kesultanan Serdang dan beberapa kerajaan Melayu di Sumatra Timur pada 1930Ibu kotaRantau PanjangPerbaunganBahasa yang umum digunakanMelayuAgama Islam (Resmi)PemerintahanMonarki KesultananSultan • 1723–1782 Tuanku Umar Johan Pahlawan Alam Shah• 1881–1946 Sultan Sulaiman Syariful Alam Shah• 2002–2011 Sultan Luckman Sinar Bashar Shah II• 2011–Sek...
Pour les articles homonymes, voir Koga. KogaLe logo de l'équipe en 2014.InformationsStatut Équipe continentaleCode UCI AXA (1999-2005) UBB (2006-2007) KOG (2011-2014)Discipline Cyclisme sur routePays Pays-BasCréation 1999Disparition 2014Saisons 16EncadrementDirecteur général Ton WellingDirecteur sportif Willy VinkPeter SchepDénominations1999-2000 Axa2001-2002 Axa-VVZ Professional2003-2005 Axa2006-2008 Ubbink-Syntec2009 Koga-CreditForce2010 Koga-CreditForce-Ubbink Track2011 Ubbink...
Public university in Basel, Switzerland University of BaselUniversität BaselLatin: Universitas BasiliensisTypePublicEstablished4 April 1460; 564 years ago (1460-04-04)BudgetCHF 768 million (2020)[1]PresidentAndrea Schenker-Wicki[2]Academic staff4,700[1]Students13,139[1]LocationBasel, Basel-City, Switzerland47°33′31″N 07°35′00″E / 47.55861°N 7.58333°E / 47.55861; 7.58333ColoursMint, Red, Anthracite[3 ...
Questa voce sull'argomento artisti marziali italiani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Matteo Marconcini Nazionalità Italia Altezza 185 cm Peso 81 kg Judo Termine carriera 21 aprile 2021 Carriera Squadre di club Judo Ok Arezzo2008-2021 Carabinieri Nazionale 2007-2020 Italia Carriera da allenatore Carabinieri Palmarès Competizione Ori Argenti Bronzi Mondiali 0 1 0 Mondiali Militari 0 0 1 World Tour 1 3 4 Campionati ital...
Cleavage of C=C, C≡C, or N=N bonds with ozone Ozonolysis Reaction type Organic redox reaction Identifiers Organic Chemistry Portal ozonolysis-criegee-mechanism In organic chemistry, ozonolysis is an organic reaction where the unsaturated bonds are cleaved with ozone (O3). Multiple carbon–carbon bond are replaced by carbonyl (C=O) groups, such as aldehydes, ketones, and carboxylic acids. The reaction is predominantly applied to alkenes, but alkynes and azo compounds are also susceptible to...
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: The One video – news · newspapers · books · scholar · JSTOR (February 2024) (Learn how and when to remove this message) 2004 video by Michael JacksonThe OneVideo by Michael JacksonReleasedMarch 9, 2004GenrePopLength39 minutes LabelEpic Music VideoP...
Imagen de la Virgen de los Treinta y Tres, patrona del Uruguay. La Iglesia católica se encuentra presente en Uruguay; a ella se adscriben aproximadamente el 45% de la población.[1] Generalidades Hay 8 diócesis y la arquidiócesis de Montevideo. El actual arzobispo es Daniel Sturla, nombrado por el papa Francisco el 11 de febrero de 2014.[2] También están presentes algunas iglesias católicas orientales: la Iglesia católica armenia y la Iglesia Maronita. Historia El proceso...
Risk management of underwater diving activities Diving safety is the aspect of underwater diving operations and activities concerned with the safety of the participants. The safety of underwater diving depends on four factors: the environment, the equipment, behaviour of the individual diver and performance of the dive team. The underwater environment can impose severe physical and psychological stress on a diver, and is mostly beyond the diver's control. Equipment is used to operate underwat...
لمعانٍ أخرى، طالع أوفيد (توضيح). أوفيد (باللاتينية: Publius Ovidius Naso) معلومات شخصية الميلاد 20 مارس 43 ق م [1][2][3] سولمونا[4] الوفاة سنة 17 [5][6] كونستانتسا[7][6][4] الإقامة كونستانتسا (8–) مواطنة روما القديمة الحياة ال...
Findlater Castle. class=notpageimage| Findlater Castle shown within the United Kingdom(grid reference NJ541672) Findlater Castle is the old seat of the Earls of Findlater and Seafield, sitting on a 50-foot (15 m)-high cliff overlooking the Moray Firth on the coast of Banff and Buchan, Aberdeenshire, Scotland. Location and etymology It lies about 15 km (9.3 mi) west of Banff, near the village of Sandend, between Cullen and Portsoy. The cliffs here contain quartz; the name Findl...
Public college in Castine, Maine, United States Maine Maritime AcademyMottoDirigo (Latin)Motto in EnglishI directTypePublic universityEstablishedMarch 21, 1941; 83 years ago (1941-03-21)Academic affiliationsSpace-grantEndowment$18.1 millionPresidentRDML Craig Johnson, USMS, Interim [1]Undergraduates979 studentsLocationCastine, Maine, United States44°23.3′N 68°48.2′W / 44.3883°N 68.8033°W / 44.3883; -68.8033Campus35 acres (14 ...
