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." > > > _______________________________________________________________________________ _______________________________________________________________________________