Editing Peg solitaire (section)

=== Studies on peg solitaire ===
A thorough analysis of the game is known.<ref name="conway">{{citation|last1=Berlekamp |first1=E. R. |author1-link=Elwyn R. Berlekamp |last2=Conway |first2=J. H. |author2-link=John H. Conway |last3=Guy |first3=R. K. |author3-link=Richard K. Guy  |title=Winning Ways for your Mathematical Plays |date=2001 |orig-year=1981 |publisher=A K Peters/CRC Press |isbn=978-1568811307 |edition=2nd |oclc=316054929|language=en |title-link=Winning Ways for your Mathematical Plays }}</ref>  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.<ref name="kiyomi">{{citation |last1=Kiyomi |first1=M. |last2=Matsui |first2=T. |title=Proc. 2nd Int. Conf. Computers and Games (CG 2000): Integer programming based algorithms for peg solitaire problems |series=Lecture Notes in Computer Science |volume=2063 |year=2001 |pages=229–240 |doi=10.1007/3-540-45579-5_15 |chapter=Integer Programming Based Algorithms for Peg Solitaire Problems |isbn=978-3-540-43080-3 |citeseerx=10.1.1.65.6244 }}</ref>

A paper in 1990 dealt with the generalized Hi-Q problems which are equivalent to the peg solitaire problems and showed their [[NP-completeness]].<ref name="uehara">{{cite journal|last1=Uehara|first1=R.|last2=Iwata|first2=S.|title=Generalized Hi-Q is NP-complete|journal=Trans. IEICE|volume=73|year=1990|pages=270–273}}</ref>

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'.<ref name="avis">{{citation |last1=Avis |first1=D. |author1-link=David Avis |last2=Deza |first2=A. |title=On the solitaire cone and its relationship to multi-commodity flows |journal=Mathematical Programming |volume=90 |issue=1 |year=2001 |pages=27–57 |doi=10.1007/PL00011419|s2cid=7852133 }}</ref>

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.<ref name="spielverderber">{{citation |last1=Eichler |last2=Jäger |last3=Ludwig |title=c't 07/1999 Spielverderber, Solitaire mit dem Computer lösen |language=de |volume=7 |year=1999 |pages=218<!--page of the reference or pages in the book?-->}}</ref>

In 2001 an efficient method for solving peg solitaire problems was developed.<ref name="kiyomi"/>

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 2<sup>9</sup> 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.<ref>{{citation| title=Mathematics and brainvita | website=Notes on Mathematics | date=28 August 2012 | url=https://notesonmathematics.wordpress.com/2012/08/28/the-mathematics-of-brainvita/ | access-date=6 September 2018}}</ref>