From:
To:
Subject: [eternity] Digest Number 12
Date: Monday, July 05, 1999 4:37 AM
--------------------------- ONElist Sponsor ----------------------------
Campaign 2000 is here!
http://www.onelist.com
Discuss your thoughts; get informed at ONElist. See our homepage.
------------------------------------------------------------------------
There are 6 messages in this issue.
Topics in today's digest:
1. Parity
From: Angus Walker
2. Re: Parity
From: "C West"
3. Re: Complexity
From: Andreas Gammel
4. Re: Complexity
From: Andreas Gammel
5. Re: Complexity
From: BERIL SONMEZ
6. Re: possible multiple solutions
From: Martin Watson
_______________________________________________________________________________
_______________________________________________________________________________
Message: 1
Date: Fri, 2 Jul 1999 17:01:40 +0100
From: Angus Walker
Subject: Parity
Hi - I'm new to this list so please excuse my ignorance.
I don't understand the concept of 'parity' - could someone please
explain it to me?
Thanks
--
Angus Walker
_______________________________________________________________________________
_______________________________________________________________________________
Message: 2
Date: Sun, 4 Jul 1999 22:11:07 +0100
From: "C West"
Subject: Re: Parity
Me too seen up/down parity left/right etc. Read some stuff at maths.com
still don't really follow the concept though. Anybody know how many 6 unit
area shapes that can be produced without 30 degree pieces to which the
eternity 209 is a subset ?
_______________________________________________________________________________
_______________________________________________________________________________
Message: 3
Date: Mon, 05 Jul 1999 09:22:41 +0200
From: Andreas Gammel
Subject: Re: Complexity
Thomas Voigt wrote:
> From: "Thomas Voigt"
>
> > I wouldn't call it a rigorous proof, but I've managed to convert the
> > problem (theoretically) into a set of discrete linear equations. Linear
> > equations can be solved in polynomial time (hence my interest!), but
> > discrete ones aren't - they're generically NP-complete, unless something
> > can be found to simplify the problem.
>
> Interesting. I also thought about transforming eternity into an IP, but
> it would probably have a lot of equations ...
I've writing these equations down, too. The problem is (I think) that a lot of
properties of the puzzle (e.g. piece A and piece B cannot overlap) result in
an INequality (like x=/ y). The trouble is that each inequality introduces 2
search ereas (x > y OR x < y). In an N-variable space this creates 2^N search
areas, so where back to point zero. The problem is to find a set of
expressions that do not contain inequalities. I believe this cannot be done.
Andreas
_______________________________________________________________________________
_______________________________________________________________________________
Message: 4
Date: Mon, 05 Jul 1999 09:36:37 +0200
From: Andreas Gammel
Subject: Re: Complexity
Thomas Voigt wrote:
> everybody says that Eternity is NP-Complete.
> Where can I find the proof ? (Or is it obvious ? :-)
I think there is am essential difference in the order of your search space
OS() of a problem and the order of the algorithm OA() for that problem.
Eg. if I want to find the first 100 digits of SQRT(2) then OS(sqrt) =
10^100. Yet we mostly use a linear algorithm that has OA(sqrt) = 100. This
is caused by the fact that we now so much about the intermediate results (in
this case x^2 should be around 2) that we can half the search space at each
step.
The trouble with Eternity is, that the intermediate results cannot be
checked when doing a binary search, which makes this algorithm unusable.
This does however NOT prove, that there isnt some other approach which does
allow for intermediate results to be checked. This might be found by
studying the properties of possible solutions. Maybe by splacing pieces in a
different way (not connecting like the screensaver does) or by placing
groups of pieces in one step, or whatever, blah blah
so, this really helps, doesnt it ....
Andreas
_______________________________________________________________________________
_______________________________________________________________________________
Message: 5
Date: Mon, 5 Jul 1999 10:42:18 +0300
From: BERIL SONMEZ
Subject: Re: Complexity
Mr. Gammel,
ý want some information about this game because ý am the new in this game
> -----Original Message-----
> From: Andreas Gammel [SMTP:qaga@oce.nl]
> Sent: 05 Temmuz 1999 Pazartesi 10:37
> To: eternity@onelist.com
> Subject: Re: [eternity] Complexity
>
> From: Andreas Gammel
>
> Thomas Voigt wrote:
>
> > everybody says that Eternity is NP-Complete.
> > Where can I find the proof ? (Or is it obvious ? :-)
>
> I think there is am essential difference in the order of your search space
> OS() of a problem and the order of the algorithm OA() for that problem.
> Eg. if I want to find the first 100 digits of SQRT(2) then OS(sqrt) =
> 10^100. Yet we mostly use a linear algorithm that has OA(sqrt) = 100. This
> is caused by the fact that we now so much about the intermediate results
> (in
> this case x^2 should be around 2) that we can half the search space at
> each
> step.
>
> The trouble with Eternity is, that the intermediate results cannot be
> checked when doing a binary search, which makes this algorithm unusable.
> This does however NOT prove, that there isnt some other approach which
> does
> allow for intermediate results to be checked. This might be found by
> studying the properties of possible solutions. Maybe by splacing pieces in
> a
> different way (not connecting like the screensaver does) or by placing
> groups of pieces in one step, or whatever, blah blah
>
> so, this really helps, doesnt it ....
>
> Andreas
>
>
>
> --------------------------- ONElist Sponsor ----------------------------
>
> ONElist members are using Shared Files in great ways!
> http://www.onelist.com
> Are you? If not, see our homepage for details.
>
> ------------------------------------------------------------------------
_______________________________________________________________________________
_______________________________________________________________________________
Message: 6
Date: Mon, 5 Jul 1999 11:06:19 +0100
From: Martin Watson
Subject: Re: possible multiple solutions
Re William's reply below, unless Monckton has one or more solutions which
are only trivially different to his 'sealed' solution, how does anyone think
these multiple solutions were achieved?
Martin
> Date: Sat, 3 Jul 1999 20:36:00 +0200
> From: "William Waite"
> Subject: Re: question
>
> >I have a question - If there are in fact many solutions to the eternity
> puzzle, do we have to get the exact solution that Monckton got, or will
> any of the solutions get us the cash?
>
> Any solution will do.
>
>
> >If we have to get the same as Monckton, it seems that a lot of our
> programs are going to be incorrect, as mine for one does not include the
> correct position for the number 34 piece, as shown on the eternity board.
>
> According to the rules that come with the Eternity puzzle:
> "It is possible to solve the puzzle without using the starter position."
>
>
>
_______________________________________________________________________________
_______________________________________________________________________________