From: Rozberk Omniist To: Ed Pegg ; Herald Subject: Fw: [eternity] Digest Number 11 Date: Monday, July 05, 1999 8:47 AM ----- Original Message ----- From: To: Sent: Sunday, July 04, 1999 5:37 AM Subject: [eternity] Digest Number 11 > > --------------------------- ONElist Sponsor ---------------------------- > > Where do some of the Internet's largest email lists reside? > http://www.onelist.com > At ONElist - the most scalable and reliable service on the Internet. > > ------------------------------------------------------------------------ > > There are 6 messages in this issue. > > Topics in today's digest: > > 1. Re: Complexity > From: redbaron@cix.compulink.co.uk (Richard Marsden) > 2. question > From: paul@white33.freeserve.co.uk > 3. Re: question > From: "Ronald Stewart" > 4. Re: Complexity > From: "Thomas Voigt" > 5. Re: question > From: "William Waite" > 6. Re: Complexity > From: redbaron@cix.compulink.co.uk (Richard Marsden) > > > ____________________________________________________________________________ ___ > ____________________________________________________________________________ ___ > > Message: 1 > Date: Sat, 3 Jul 99 15:43 BST > From: redbaron@cix.compulink.co.uk (Richard Marsden) > Subject: Re: Complexity > > In-Reply-To: <199907030900.LAA27406@mail.cs.tu-berlin.de> > In article <199907030900.LAA27406@mail.cs.tu-berlin.de>, > voigtgob@cs.tu-berlin.de (Thomas Voigt) wrote: > > > From: "Thomas Voigt" > > > > Howdy, > > > > everybody says that Eternity is NP-Complete. > > Where can I find the proof ? (Or is it obvious ? :-) > > > > tv > > 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. > > > > Richard > > > > ____________________________________________________________________________ ___ > ____________________________________________________________________________ ___ > > Message: 2 > Date: 3 Jul 1999 16:15:09 -0000 > From: paul@white33.freeserve.co.uk > Subject: 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? > > 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. Should we enter this into our programs to ensure that it stays in that position? > > What do we think? > > > ____________________________________________________________________________ ___ > ____________________________________________________________________________ ___ > > Message: 3 > Date: Sat, 3 Jul 1999 20:33:28 +0100 > From: "Ronald Stewart" > Subject: Re: question > > >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. Should we > enter this into our programs to ensure that it stays in that position? > > > >What do we think? > > > We think that if you fill the board, then they cannot disallow your solution > as it is equally as correct as Monckton's original. > > For reasons I have already argued, I feel it would be more advisable to > place the pieces given as there is a guaranteed solution on that path. But > you are entitled to your own opinion. > > Having said that, I do not feel that it is worthwhile to pay for the > sub-puzzles to get the extra positions. Hehee. > > WHSmiths refused to sell me their display copy this afternoon. And it was > tattered. I guess I'm waiting until August... > > - Ron > > > > ____________________________________________________________________________ ___ > ____________________________________________________________________________ ___ > > Message: 4 > Date: Sat, 3 Jul 1999 22:28:39 +0100 > From: "Thomas Voigt" > Subject: Re: Complexity > > > 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 ... > But I would agree that eternity is either NP or high-order P. > If I had a house I would bet it on the fact that simple > brute force (like the screen saver) won't solve the problem :-) > > tv > > -- > Thomas Voigt | spock@berlin.snafu.de, tvoigt@comitatus.de > ================================================================== > I have a message to deliver to the cute people of the world...if > you're cute, or maybe you're beautiful...there's MORE OF US UGLY > MOTHERF#^&^#$ OUT THERE THAN YOU ARE!! (Frank Zappa) > > > ____________________________________________________________________________ ___ > ____________________________________________________________________________ ___ > > Message: 5 > 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." > > > > ____________________________________________________________________________ ___ > ____________________________________________________________________________ ___ > > Message: 6 > Date: Sun, 4 Jul 99 00:07 BST > From: redbaron@cix.compulink.co.uk (Richard Marsden) > Subject: Re: Complexity > > In-Reply-To: <199907032027.WAA09985@mail.cs.tu-berlin.de> > In article <199907032027.WAA09985@mail.cs.tu-berlin.de>, > voigtgob@cs.tu-berlin.de (Thomas Voigt) wrote: > > > Interesting. I also thought about transforming eternity into an IP, but > > it would probably have a lot of equations ... > > But I would agree that eternity is either NP or high-order P. > > If I had a house I would bet it on the fact that simple > > brute force (like the screen saver) won't solve the problem :-) > > > > tv > > I now have it in the form of a sparse matrix. Takes a few minutes to > create. Also, takes about 40Meg. My code probably isn't optimum, but it > is cunning enough to join and split neighbouring nodes, so as to minimise > the C++ object overhead. > > > > > Richard > > > > ____________________________________________________________________________ ___ > ____________________________________________________________________________ ___ > >