A stronger model for peg solitaire II

Claude - Auguste Berey

Description

Niveau: Supérieur, Doctorat, Bac+8
A stronger model for peg solitaire, II ?† O. Ramaré, CNRS, Laboratoire Painlevé, Université Lille 1 59 655 Villeneuve d'As q, Fran e January 4, 2008 Abstra t The main problem addressed here is to de ide whether it is or not possible to go from a given position on a peg-solitaire board to another one. No non-trivial su ient onditions are known, but tests have been devised to show it is not possible. We expose the way these tests work in a unied formalism and provide a new one whi h is stri tly stronger than all previous ones. 1 Introdu tion Peg solitaire (also alled Hi-Q) is a very simple board game that appeared in Europe most probably at the end of the 17th entury. Its prior origin is unknown. The rst eviden e is a painting by Claude-Auguste Berey of Anne Chabot de Rohan (1663-1709) playing it. It seems to have then be ome popular in some royal ourts. The mathemati al study of the game starts in 1710 when Leibniz writes a memoir on the subje t [1?. We refer the reader to the ex ellent histori al a ount presented in Beasley's book [2?. Let us introdu e rapidly how this game is being played.

• single peg via legal moves


• negative integer


• conway's group theory


• lassi al


• ex ellent histori


• peg solitaire


• full linear

Sujets

• Europe
• Integer
• Peg solitaire

Informations

• Publié par: mijec
• Nombre de lectures: 37
• Langue: English

Extrait

∗†
2S
I
J
∗
†
I
I
p
The
h
and
for
ted
O.
w
Ramar?,
),
CNRS,
sub
Lab
game
oratoire
Z
P
(see
ainlev
en
?,
solitaire,
Univ
1710
ersit?
to
Lille
us
1
rst
59
e
655
h
Villeneuv
tro
e
oard

it
F
mo
rance
that
Jan

uary
the
4,
a
2008
e

historical
The
o
main
rapidly
problem
pla
addressed
b
here
ximation
is
as
to
oard

b
whether
a
it
J.C.
is
square
or
most
not
as
p
go
ossible
p
to
one
go
of
from
w
a
da
giv
91A46,
en
study
p
starts
osition
Leibniz
on
on
a
℄
p
the
eg-solitaire

b
t
oard
Beasley's
to
℄
another
tro
one.
w
No
b
non-trivial
ed.
sucien
is
t
stronger

rst
are
y
kno
t
wn,
subset
but
english
tests
the
ha
dra
v
w,
e
presen
b
one
een
b
devised
in
to

sho
this
w
hold
it
p
is
pr
not
e
p
is
ossible.
a
W
of
e
(sa
exp
to
ose
y
the
a
w
gal
solitaire,
e
eyw
a
y
P
these
P
eg
tests
w
05A99,
ork
90C08.
in
mathematical
a
of
unied
game
formalism
in
and
when
pro
writes
vide
memoir
a
the
new

one
W
whic
refer
h
reader
is
the

t
stronger

than
presen
all
in
previous
b
ones.
ok
1
Let
In
in
tro


ho
P
this
eg
is
solitaire
eing
(also
y

The
Hi-Q)
data
is
a
a
oard
v
whic
ery
in
simple
appro
b
ma
oard
b
game
though
del
of
.
a

of
are
that
app
The
eared
ones
in
the
Europ
b
e
and
most

probably
one
at
wn
the
elo
end
and
of
e
the
t
17th
third

in
tury

.
y
Its
Wiegleb
prior
1779
origin
℄
is
h
unkno
of
wn.
b
The

rst
at

one
is
eg,
a
a
pain
oblem
ting
w
b
dene
y
here
Claude-Auguste
to
Berey
from
of
giv
Anne
distribution
Chab
these
ot
egs
de
y
Rohan
)
(1663-1709)
another
pla
(sa
A
ying
it.
via
It

seems
le
to
moves
ha
w
v
no
e
dene.
then
k
b
ords:
ecome
eg
p
Hi-Q,
opular
ago
in
function.
some
AMS
ro
primary
y

al
52B12,

1P Q R
P Q
R
P Q R
P Q R
Q
|I|−|J|
|I|−|J|
577 116 156 815 309 849 672
40 861 647 040 079 968
n×n k×n
k
7× 7
remo
ving
tral
Wiegleb
h
the
an
t
binatorial
w
.
o
are
p
this
egs
e
in
eg
3:
b
and
a
Figure
problem
and
y
putting
it
one
b
on
reac
the
gets
empt

y
oard
square
the
oard
v
.
on
W
nal
e
umerous

to
sa
y
y
to
that
in
the
es

the
p
not,
eg
mo
in
fur-
b
This
jumps
ecause
o

v
one
er

the

middle
english
one

in
h
h
tral
and
whic
lands
a
in
en
renc
eing
,
℄
while
sho
destro
or
ying
a
the
ose
p
b
eg
is
in
that.
F
b
.
e
As
mo
a
rep
trivial
un

n
the
(
n
do
um
)
b
es
er
or
of
mo
p
p
egs

on
k
the
the
b
F
oard
Harang

there
when
the
the
a
game
b
pro
(sa

w
further.
on
F
oard
or
p
most
the
authors,
on
a
e
problem
the

empt
in
whic

diagonal),
the
(but
initial
w
distribution
Giv
of
to
p
eg
egs,
the
what
See
w

e
tend

that
thereafter
NP-complete.
the
sen
initial
v
p
w
osition

,
w
to
extending
a
to
single
and
p

eg
hiev
via

legal
three
mo
is
v
while
es.
us
They
not
qualify
v
the
and
p
eat
osition
action
as
til
solvable
required
if
um
this
er
is
a
p
es
ossible.
)
W
(
e
of
shall
v
sa
is
y
hed
that
no
the
ther
problem
v
in
is
our
ossible.
sense
pro
is
usually
fe
stuc
asible
b
if
of
one


explosion.
go
or
from
E.
the
℄
initial
that
p
are
osition
third
to
while
the
p
nal
tain
one
)
b
and
y
y
using
e
legal
o
mo
t
v
paths
es.
the
Note
b
that
from
the
initial
n
osition
um
of
b
full
er
oard
of
whic

w
h
lea
mo
e
v

es
square
is
y
kno
Of
wn
h
and
of
equals
a
the
not
dierence

b
or
et
ro
w
in
een
and
the
lead
n
the
um
p
b
b
er
on
of

p
square.
egs
also
in
In
the
n
initial
setting
p
to
osition
w
and
the
the
is
n
F
um
this

tence
move
ha
oard
e
gal
sense,
is
e
wn
to
b
ho
linear
a
℄
a

of
ma
the
w
oard
whether
innit
english
,
oard
there
a
no
of
fashion
le
ac
in
e
oard
The
tractable
of
not
,
the
squares
er
oard
still
studied
at
℄
not
the
will
b
er
b
of
with
p
xed
egs
sho
in
to
the
e
nal
in
one
Of
(that
one
is:
y
2:
onder
Figure
the
oard
b
b
as
English
subset
1:
a

h

b
n
is
b
or
of
and
b
answ
enormous,
is
e
no,
ok
least
tests
without
Figure
uge
).
The
Giv
um
en
er
a
paths
problem,
eing
w
w
e
lo

for
try
that
all
ensure
p
that
ossible
is
legal
2S F(S, )
F(S, ) F(S, )2
I ⊂S
ˇP ∈S PI
ˇ ˇ ˇP f =P+Q−R −fI
attributed
to
Reiss
has
in
use
in
in
1857
whic
in
Beasley
℄
oard.
though
game.
Beasley
of
traces
ev
it
due

or
k
of
to
een
A.
are
Suremain
w
de
none
Missery
b
,
an
a
a
former
GTK

in
of

the
t
F
for
renc
en
h
In
artillery
del
,
w
around
though
1842.
oard
W
The
e
this
again
tee
refer
p
the
set
reader
its
to
function
℄
th
for
an
more
e
historical
a
details.
Let
It
y
is

also
in
describ
it
ed
our
in
w

(to
b
wledge
o
on
ok
not
℄
time,
whic
orking
h
via


tains
tally
also
It
more

material
of
and
b
in
Z
the
et

functions

dene
hapter
y