From: To: Subject: [eternity] Digest Number 13 Date: Monday, July 05, 1999 11:41 PM --------------------------- ONElist Sponsor ---------------------------- Attention ONElist list owners! http://www.onelist.com/info/news.html Check out the new "DEFAULT MODERATED STATUS" option. ------------------------------------------------------------------------ There are 25 messages in this issue. Topics in today's digest: 1. Re: Question From: "Christophe Weibel" 2. Re: Complexity From: "Christophe Weibel" 3. Re: Complexity From: "Christophe Weibel" 4. Re: Parity From: "Christophe Weibel" 5. Re: possible multiple solutions From: "Christophe Weibel" 6. Programming Eternity From: Dsaund2773@aol.com 7. Re: Welcome to eternity@onelist.com From: Morgan Gary 8. Re: possible multiple solutions From: "Ronald Stewart" 9. Am I too late? From: Morgan Gary 10. Re: possible multiple solutions From: "Bob Harris" 11. Re: Am I too late? From: "=?iso-8859-1?Q?Pierre-Fran=E7ois_Culand?=" 12. Who are You ? From: Angus Walker 13. Re: Am I too late? From: Jason Armitage 14. s.o.s. From: BERIL SONMEZ 15. Re: Am I too late? From: "Ronald Stewart" 16. Re: Who are You ? From: Douglas Hogan 17. Re: Complexity From: redbaron@cix.compulink.co.uk (Richard Marsden) 18. Re: Complexity From: redbaron@cix.compulink.co.uk (Richard Marsden) 19. Re: Welcome to eternity@onelist.com From: "Martin Humphry" 20. Estimating the run time of brute force algorithms From: "Thomas Voigt" 21. Re: Who are You ? From: "Thomas Voigt" 22. Re: Complexity From: steve.waddicor@virgin.net (Steve Waddicor) 23. size of the box From: =?iso-8859-1?Q?Manuel_Carrillo_Jim=E9nez?= 24. size of the box From: =?iso-8859-1?Q?Manuel_Carrillo_Jim=E9nez?= 25. Re: Opinion please From: path@multipro.com.au _______________________________________________________________________________ _______________________________________________________________________________ Message: 1 Date: Mon, 5 Jul 1999 13:43:41 +0200 From: "Christophe Weibel" Subject: Re: Question On Jul 2, 2:35pm, Ing. Marco Polazzo wrote: > Subject: [eternity] Question > WHAT DOES IT MEAN AGAINST THE GRAIN ? (What is a Grain?) > > If someone could explain me..... I thanks him very much. Well. I suppose you've already seen the pages on www.mathpuzzle.com trying to explain. I didn't understand them, either. Here is the grid (sort of): ---------------- /\ /\ /\ /\ / \/ \/ \/ \ ---------------- Each one of the Etenity pieces contain triangles: ---- /\ / / \/ ---- A piece is placed AGAINST THE GRAIN if the triangles of the piece are NOT ALIGNED with the triangles of the grid. That is if you place the piece above on the grid, you obtain this. ---------------- /\ /\/\/\/ /\ / \/ /\/\/\/ \ ---------------- Now, if you place a piece "with the grain", you can move it in six different directions by a "half triangle side". Left or right, up-left or down-right, and up-right or down-left each give a different kind of against the grain. So, there are four ways a piece can be placed: the three against the grain, and one with the grain. _______________________________________________________________________________ _______________________________________________________________________________ Message: 2 Date: Mon, 5 Jul 1999 14:04:16 +0200 From: "Christophe Weibel" Subject: Re: Complexity On Jul 3, 3:43pm, Richard Marsden wrote: > 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. A rigorous proof would be to find a NP-Complete problem, and a transformation of this problem into a Eternity-type problem. Good luck... I think someone will solve Eternity before! :) _______________________________________________________________________________ _______________________________________________________________________________ Message: 3 Date: Mon, 5 Jul 1999 14:08:47 +0200 From: "Christophe Weibel" Subject: Re: Complexity On Jul 3, 10:28pm, 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 :-) Somewhere, someone (Monckton or a insurance company) is willing to bet one million pounds that NO program will solve it... Do you also have the feeling you have a "stupid guy" label stuck on your back? :) _______________________________________________________________________________ _______________________________________________________________________________ Message: 4 Date: Mon, 5 Jul 1999 14:36:43 +0200 From: "Christophe Weibel" Subject: Re: Parity On Jul 2, 5:01pm, Angus Walker wrote: > 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? Well. I found a good explanation somewhere (don't remember where): If you have a chess board, you can cover it with tiles of two squares: ------- | | | ------- But if you remove two black squares on opposite corners of the chess board, you won't be able to cover the rest. Why? There are 32 white squares left, and only 30 black squares left. And each two-squares tile covers a black square and a white square. So the best you can do is cover the 30 black squares and 30 of the 32 white squares, and there's still two white squares, which can't be adjacent, and which can't possibly be covered with a single tile. There are 12 different orientations for a drafter (half-equilateral-triangle) on the eternity board. On http://www.mathpuzzle.com/eternity.html there is an image titled "The three parities of ETERNITY" which shows three different ways of coloring the orientations, which each function like the chess board coloring. Now, it's more complicated than the chess board, because the eternity pieces aren't always "balanced", that is, they won't cover exactly as many black drafters and white drafters. They can be of parity 2, 4, or 6, meaning they will cover 2, 4, or 6 more drafters of one color than of the other. So it's possible that you find you have colored 60 more black drafters than white drafters, but the sum of parities of the remaining pieces is 20. So with the pieces you've still got, you'll only be able to color 20 more white drafters than black drafters. So it won't possible. So it would be a good idea that your program stops placing pieces and starts deleting a few ones :) _______________________________________________________________________________ _______________________________________________________________________________ Message: 5 Date: Mon, 5 Jul 1999 14:46:43 +0200 From: "Christophe Weibel" Subject: Re: possible multiple solutions On Jul 5, 11:06am, Martin Watson wrote: > 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? I think they probably don't have multiple solutions, except for the few symmetries. I think this sentence in the rules doesn't mean anything. Of course you can get a solution without USING the starter position, but maybe the solution you'll obtain will contain the starter position. Or a symmetry. _______________________________________________________________________________ _______________________________________________________________________________ Message: 6 Date: 5 Jul 1999 12:49:32 -0000 From: Dsaund2773@aol.com Subject: Programming Eternity I think C.M. has a misconception about using programming to solve Eternity. The computer doesnt solve the puzzle. It is the logic thought built into the program that uses the computer as a tool to do the mundane very quickly. I believe there is a way to program this problem. I believe there is a logical approach. I like to think it is the study of parity. Dick Saunders _______________________________________________________________________________ _______________________________________________________________________________ Message: 7 Date: Mon, 5 Jul 1999 14:05:00 +0100 From: Morgan Gary Subject: Re: Welcome to eternity@onelist.com QUESTIONS -------------- What's your..... name :Gary Morgan age : 22 occupation : Programmer city : London country : UK email : MorganGa@Logica.com homepage : ------- How did you hear about this list (website / friends) ? ------- www.mathpuzzle.com ------- Are you an active problem-solver, or just here out of general interest ? ------- Active problem solver ------- Do you hope that by listening to this list, you'll get the vital hint that'll make you win the prize ? ------- Yes. For a start I'd like the positions of the 5 other pieces. Normally available when you complete the smaller puzzles. ------- Do you own an Eternity puzzle ? ------- Yes ------- What's your best attempt by hand ? ------- Haven't tried by hand yet. Pieces are still sealed in their 4 bags. ------- What's your best attempt by computer ? ------- Haven't got my search engine up & running yet. I've just created a piece editor & entered the pieces into the computer. I only started 3 days ago. ------- What language / system / pc are you using ? ------- c++ (gcc) / 2 x PII400s 128Meg ram / Redhat linux 5.1 - Qt GUI toolkit ------- What algorithms / heuristics do you use for Eternity (brute force, backtracking, genetic algothims, simulated annealing, SECRET) ? ------- brute force, backtracking, genetic algothims & SECRET (design's in my head, haven't written it yet) ------- Did you type in all 209 pieces yourself ? ------- Yes ------- Did you try any simpler variations of Eternity ? ------- No ------- Do you know some other interesting web-sites ? ------- ------- Other hobbies ? ------- ------- Other physical puzzles ? ------- ------- Other programming projects ? ------- Loadz ------- Are you willing to show the group your source code (after removing your secret functions) ? ------- Yes. ------- Any other stuff you like to add ? ------- ------- Do you know any other interesting problems ? ------- Yes. ------- What's the meaning of life ? ------- ------- How are you going to spend your 1000.000 ? ------- Since the 1000,000 is taxed, I'll only have a fraction of it to spend. _______________________________________________________________________________ _______________________________________________________________________________ Message: 8 Date: Mon, 5 Jul 1999 14:55:26 +0100 From: "Ronald Stewart" Subject: Re: possible multiple solutions >From: Martin Watson > >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 By rotation and reflection, there are (I believe) 24 possible solutions which are in effect the same as Monckton's, although 23 will have the starter piece in a different position. This also covers any other possible solutions, which haven't been found (if they *could* have been found by now, then the puzzle wouldn't be hard, would it). Or perhaps as you suggest, there are trivial differences - such as a group of pieces making up the same shape which can be swopped. - Ron _______________________________________________________________________________ _______________________________________________________________________________ Message: 9 Date: Mon, 5 Jul 1999 15:01:00 +0100 From: Morgan Gary Subject: Am I too late? Since I've started this race a month later than everyone else in the world, the most important question to me is: Has anyone solved it yet? _______________________________________________________________________________ _______________________________________________________________________________ Message: 10 Date: Mon, 05 Jul 1999 10:09:16 -0500 From: "Bob Harris" Subject: Re: possible multiple solutions >> According to the rules that come with the Eternity puzzle: >> "It is possible to solve the puzzle without using the starter position." > > Re William's reply, 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? His solution could be rotated and reflected, so that gives a couple other solutions. While we probably wouldn't think of them as being 'different', the statement "it is possible to solve the puzzle without using the starter position" is certainly true. _______________________________________________________________________________ _______________________________________________________________________________ Message: 11 Date: Mon, 5 Jul 1999 16:31:57 +0100 From: "=?iso-8859-1?Q?Pierre-Fran=E7ois_Culand?=" Subject: Re: Am I too late? >From: Morgan Gary > > >Since I've started this race a month later than everyone else in the world, >the most important question to me is: Has anyone solved it yet? If I had already solve it and had sent my answer, I would answer YES because there would be no raison to hide this... If I hadn't solve it yet, I would answer YES to eliminate a new competitor candidate. So... YES I solved it ! That was easier than I thought... ;-) P.F. Culand Swiss Knife Software http://www.SwissKnifeSoftware.com P.S: This is finally and interessant question, what would Ertl do if an eventual winner would publish its solution after having regulary entered it...(Why wouldn't he do that ? Nothing in the rules forbid to do this) There would probably be a lot of consequent mails sent after this to Ertl with a copy of the published solution... And moreover, no more Eternity boxes sold !!! (They probably wouldn't like that...) The winner could even try to make profit out of this by asking more than the promised £1'000'000 reward, in exchange he would keep its solution secret until september 2000. Did they forgot this possibility ? It seems they are terribly sure nobody would solve it ! _______________________________________________________________________________ _______________________________________________________________________________ Message: 12 Date: Mon, 5 Jul 1999 15:23:44 +0100 From: Angus Walker Subject: Who are You ? QUESTIONS -------------- What's your..... name : Angus Walker age : 37 occupation : would-be lawyer city : London country : UK email : eternity@angus.demon.co.uk homepage : http://www.angus.demon.co.uk ------- How did you hear about this list (website / friends) ? ------- >From mathpuzzle.com ------- Are you an active problem-solver, or just here out of general interest ? ------- I am actively trying to solve Eternity, if that is what you mean ------- Do you hope that by listening to this list, you'll get the vital hint that'll make you win the prize ? ------- Listening - and participating ------- Do you own an Eternity puzzle ? ------- Yes, but I'm only opening it to place the pieces once I've solved the puzzle ------- What's your best attempt by hand ? ------- N/A ------- What's your best attempt by computer ? ------- Still perfecting my program :-) ------- What language / system / PC are you using ? ------- VBA using Access, 266MHz PC ------- What algorithms / heuristics do you use for Eternity (brute force, backtracking, genetic algorithms, simulated annealing, SECRET) ? ------- Educated brute force ------- Did you type in all 209 pieces yourself ? ------- Yes - I hope I got them right ------- Did you try any simpler variations of Eternity ? ------- If you mean the three mini-puzzles, they haven't arrived yet. If you mean test versions similar to Eternity, no. ------- Do you know some other interesting web-sites ? ------- Not related to this business ------- Other hobbies ? ------- crosswords, bridge - that sort of thing ------- Other physical puzzles ? ------- ------- Other programming projects ? ------- Nope - my programming is *very * rusty. ------- Are you willing to show the group your source code (after removing your secret functions) ? ------- Probably, except it'll be embarrassingly poor quality compared to people who know what things like 'simulated annealing' mean. I thought that was something to do with preventing rust. ------- Any other stuff you like to add ? ------- i) I hope that if someone solves it that they let us know rather than having to wait until September next year to find out ii) Has anyone solved the mini puzzles and received placements of a piece or pieces? what is the sending in/receiving the answer time lag? There seems to be some coyness on the list about this iii) Do we want to agree on terminology and nomenclature? Pieces: I have named the pieces (somewhat perversely) in hex - '00' - 'D0'. Board triangles: I have numbered the board triangles 1-1278 in rows, starting with a half-triangle row. Thus the piece we are given to start with is at 208/234/260/287/288 in whole triangles, the bottom half of 261 and the upper left half of 316, and is piece 34 (or '21' according to me!). Half-triangles: We need a standard way of referring to half-triangles - I have numbered them from 1-12, I know others use 1-6 twice depending on whether it is a left-pointing or right-pointing triangle. Pieces on the board: I have called putting a piece on the board a 'placement'. A piece can be placed (with the grain - I am in denial about an against the grain solution at the moment) in any of twelve ways. I have labelled these by numbering the twelve possible orientations 1-12, and deciding arbitrarily that one particular (whole) triangle belonging to each piece is its 'base triangle'. For example take piece 1 (or '00'). If you label the middle of the five whole triangles the base triangle, and call the orientation where you flip the piece over and rotate it by 30 degrees from its position in the diagram supplied with the puzzle (or 60 degrees from its position on the mathpuzzle website) orientation 4, then that piece can be fitted in the top left hand corner of the board at position 21/4 i.e. board triangle 21, orientation 4. Are you with me? Or am I talking complete nonsense? iv) Which are the consistently 'difficult to place' pieces? Are they the few with six half-triangles, or those with more than their fair share of concavities? It seems that the higher-numbered ones are more tricky than those at the beginning. ------- Do you know any other interesting problems ? ------- The paradox of the unexpected hanging - is that the sort of thing you mean? ------- What's the meaning of life ? ------- It has no meaning ------- How are you going to spend your 1000.000 ? ------- I'll cross that bridge when I come to it -- Angus Walker _______________________________________________________________________________ _______________________________________________________________________________ Message: 13 Date: Mon, 05 Jul 1999 15:43:23 +0100 From: Jason Armitage Subject: Re: Am I too late? It this time I can't think what possible defence Ertl would have against such disclosure. Possibly, they could get a court injunction, based on loss of revenue, but that would only have applicable in the UK. If some one was to find a solution they would be able to make quite a lot of money by selling the solution and their story to the media. Possibly the analysts looked at the sales for the rubic cube, don't think they went down once the solution was widely known, they might have risen. Jason. Pierre-Francois_Culand wrote: > From: "=?iso-8859-1?Q?Pierre-Fran=E7ois_Culand?=" > > >From: Morgan Gary > > > > > >Since I've started this race a month later than everyone else in the world, > >the most important question to me is: Has anyone solved it yet? > > If I had already solve it and had sent my answer, I would answer YES because > there would be no raison to hide this... > > If I hadn't solve it yet, I would answer YES to eliminate a new competitor > candidate. > > So... YES I solved it ! That was easier than I thought... > ;-) > > P.F. Culand > Swiss Knife Software > http://www.SwissKnifeSoftware.com > > P.S: This is finally and interessant question, what would Ertl do if an > eventual winner would publish its solution after having regulary entered > it...(Why wouldn't he do that ? Nothing in the rules forbid to do this) > There would probably be a lot of consequent mails sent after this to Ertl > with a copy of the published solution... And moreover, no more Eternity > boxes sold !!! (They probably wouldn't like that...) > > The winner could even try to make profit out of this by asking more than the > promised #1'000'000 reward, in exchange he would keep its solution secret > until september 2000. > > Did they forgot this possibility ? > > It seems they are terribly sure nobody would solve it ! > > --------------------------- ONElist Sponsor ---------------------------- > > Looking to expand your world? > http://www.onelist.com > ONElist has 180,000 e-mail communities from which to choose! > > ------------------------------------------------------------------------ _______________________________________________________________________________ _______________________________________________________________________________ Message: 14 Date: Mon, 5 Jul 1999 18:01:11 +0300 From: BERIL SONMEZ Subject: s.o.s. ýs there anyone to help me?(ý really pleasure) _______________________________________________________________________________ _______________________________________________________________________________ Message: 15 Date: Mon, 5 Jul 1999 16:02:24 +0100 From: "Ronald Stewart" Subject: Re: Am I too late? >Possibly the analysts looked at the sales for the rubic cube, don't think they >went down once the solution was widely known, they might have risen. Agreed... the knowledge that there is a findable solution may increase sales - at the moment, it is being marketed as a truly impossible puzzle. Anyone up for this type of challenge will buy, but Joe Public would not bother (well, if he sees the prize fund he might consider!). - Ron _______________________________________________________________________________ _______________________________________________________________________________ Message: 16 Date: Mon, 5 Jul 1999 16:13:39 +0100 From: Douglas Hogan Subject: Re: Who are You ? Here my 10 pence worth..... I wrote a program to solve eternity before it came out. I started it after seeing the puzzle presented on Sky News. Amazingly, as a computer programmer and someone who likes these types of tasks, I had to look hard to find information on the puzzle - I don't think they did a great job marketing it - if I hadn't seen the 5 minute clip on Sky News I don't think I would ever have heard about it. I've programmed the puzzle in C++ and think the code is fairly tight apart from the improvements below. I am a little disillusioned with the puzzle now and get the impression that implementing the improvements will cut the solution time from 10^100 years to 10^99 years!! 2 possible improvements to the algortihm. 1. Only test the region surrounding the last placed piece for an illegal board position. 2. Parity checks. 3. The idea about placing difficult pieces first. I do use a brute force method with some optimizations. One of the most effective of these was backtracking variable numbers of pieces if the max depth repeatedly hit the same upper bound. This dealt with dead end pieces. I did code a random piece choice extension to my algorithm to minimize finding similar dead-ends. I got an e-mail from Ed Pegg declaring that a program had to handle the 'against the grain' issue or it wouldn't solve the puzzle. This probably added 2 weeks programming time and created a work area of 4 times resolution. I now realize that that statement is a load of blarney! My code is a lot simpler and runs much faster now. Nice one Ed, but I still don't think I'll find a solution. My best result is ~165 pieces after a 2 hour run. It doesn't seem to get any better than this no matter how long the program is run. I am not taking into account parity issues. I do analyse the board before placing a piece to make sure it doesn't create illegal spaces. I solved the Delta & Meteor puzzles in about 10 minutes by hand. The Heart puzzle has turned out to be a much tougher nut to crack. I started to write a program to solve it using sort of linked lists, etc. I don't suppose anyone wants to reveal the Eternity placements for the heart puzzle? In any case, I have found no improvement by using the 4 starter positions I've got. There was a time lag of 2-3 weeks before the starter pieces were sent from ERTL. On the point of ERTL getting annoyed if someone posted a solution, I can't think of anyone in their right mind buying a puzzle like this unless there was a carrot for solving it. The puzzles themselves are of very low build quiality. I solved the Meteor puzzle but the pieces wouldn't fit together (maybe I found the wrong solution). The grid for Eternity doesn't fit unless you leave a 1/2 mm gap between the pieces. Monckton himself apparently said he solved the puzzle by hand after he created it and it took about 3 years. I think the chances of solving the puzzle by hand are infinitessimal, especially with the cheap board provided. Another marketing ploy... I think some mathematician somewhere will come up with a solution algoritm (divide and conquer like quicksort, or something like that). Must go now (my dream of celebrity is over) ......... -----Original Message----- From: Angus Walker [mailto:angus@angus.demon.co.uk] Sent: Monday, July 05, 1999 7:24 AM To: eternity@onelist.com Subject: [eternity] Who are You ? From: Angus Walker QUESTIONS -------------- What's your..... name : Angus Walker age : 37 occupation : would-be lawyer city : London country : UK email : eternity@angus.demon.co.uk homepage : http://www.angus.demon.co.uk ------- How did you hear about this list (website / friends) ? ------- >From mathpuzzle.com ------- Are you an active problem-solver, or just here out of general interest ? ------- I am actively trying to solve Eternity, if that is what you mean ------- Do you hope that by listening to this list, you'll get the vital hint that'll make you win the prize ? ------- Listening - and participating ------- Do you own an Eternity puzzle ? ------- Yes, but I'm only opening it to place the pieces once I've solved the puzzle ------- What's your best attempt by hand ? ------- N/A ------- What's your best attempt by computer ? ------- Still perfecting my program :-) ------- What language / system / PC are you using ? ------- VBA using Access, 266MHz PC ------- What algorithms / heuristics do you use for Eternity (brute force, backtracking, genetic algorithms, simulated annealing, SECRET) ? ------- Educated brute force ------- Did you type in all 209 pieces yourself ? ------- Yes - I hope I got them right ------- Did you try any simpler variations of Eternity ? ------- If you mean the three mini-puzzles, they haven't arrived yet. If you mean test versions similar to Eternity, no. ------- Do you know some other interesting web-sites ? ------- Not related to this business ------- Other hobbies ? ------- crosswords, bridge - that sort of thing ------- Other physical puzzles ? ------- ------- Other programming projects ? ------- Nope - my programming is *very * rusty. ------- Are you willing to show the group your source code (after removing your secret functions) ? ------- Probably, except it'll be embarrassingly poor quality compared to people who know what things like 'simulated annealing' mean. I thought that was something to do with preventing rust. ------- Any other stuff you like to add ? ------- i) I hope that if someone solves it that they let us know rather than having to wait until September next year to find out ii) Has anyone solved the mini puzzles and received placements of a piece or pieces? what is the sending in/receiving the answer time lag? There seems to be some coyness on the list about this iii) Do we want to agree on terminology and nomenclature? Pieces: I have named the pieces (somewhat perversely) in hex - '00' - 'D0'. Board triangles: I have numbered the board triangles 1-1278 in rows, starting with a half-triangle row. Thus the piece we are given to start with is at 208/234/260/287/288 in whole triangles, the bottom half of 261 and the upper left half of 316, and is piece 34 (or '21' according to me!). Half-triangles: We need a standard way of referring to half-triangles - I have numbered them from 1-12, I know others use 1-6 twice depending on whether it is a left-pointing or right-pointing triangle. Pieces on the board: I have called putting a piece on the board a 'placement'. A piece can be placed (with the grain - I am in denial about an against the grain solution at the moment) in any of twelve ways. I have labelled these by numbering the twelve possible orientations 1-12, and deciding arbitrarily that one particular (whole) triangle belonging to each piece is its 'base triangle'. For example take piece 1 (or '00'). If you label the middle of the five whole triangles the base triangle, and call the orientation where you flip the piece over and rotate it by 30 degrees from its position in the diagram supplied with the puzzle (or 60 degrees from its position on the mathpuzzle website) orientation 4, then that piece can be fitted in the top left hand corner of the board at position 21/4 i.e. board triangle 21, orientation 4. Are you with me? Or am I talking complete nonsense? iv) Which are the consistently 'difficult to place' pieces? Are they the few with six half-triangles, or those with more than their fair share of concavities? It seems that the higher-numbered ones are more tricky than those at the beginning. ------- Do you know any other interesting problems ? ------- The paradox of the unexpected hanging - is that the sort of thing you mean? ------- What's the meaning of life ? ------- It has no meaning ------- How are you going to spend your 1000.000 ? ------- I'll cross that bridge when I come to it -- Angus Walker --------------------------- ONElist Sponsor ---------------------------- Check out this week's ONElist of the week. http://www.onelist.com How is ONElist changing YOUR life? Visit our homepage and let us know! ------------------------------------------------------------------------ _______________________________________________________________________________ _______________________________________________________________________________ Message: 17 Date: Mon, 5 Jul 99 16:38 BST From: redbaron@cix.compulink.co.uk (Richard Marsden) Subject: Re: Complexity In-Reply-To: <9907051404.ZM992@masg20.epfl.ch> In article <9907051404.ZM992@masg20.epfl.ch>, weibel@masg32.epfl.ch (Christophe Weibel) wrote: > A rigorous proof would be to find a NP-Complete problem, and a > transformation > of this problem into a Eternity-type problem. Good luck... I think > someone will > solve Eternity before! :) Well, I have gone the other way! :-) Richard _______________________________________________________________________________ _______________________________________________________________________________ Message: 18 Date: Mon, 5 Jul 99 16:38 BST From: redbaron@cix.compulink.co.uk (Richard Marsden) Subject: Re: Complexity In-Reply-To: <37805D41.8E9FEEDC@oce.nl> > 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 It isn't too hard to convert the linear equations into simple summations (with equalities). The problem is that these equations then work on discrete values. Therefore linear algebra (Gaussian Elimination, Simplex,etc) doesn't work, and a search of solution space has to be performed. Richard _______________________________________________________________________________ _______________________________________________________________________________ Message: 19 Date: Mon, 5 Jul 1999 17:17:41 GMT0BST From: "Martin Humphry" Subject: Re: Welcome to eternity@onelist.com > QUESTIONS > -------------- > What's your..... > > name : Martin Humphry > age : 23 > occupation : Research student > city : Nottingham > country : UK > email : ppxmjh@nottingham.ac.uk > homepage : > > ------- > How did you hear about this list (website / friends) ? > ------- > www.mathpuzzle.com > ------- > Are you an active problem-solver, or just here out of general interest ? > ------- > Problem solver - when I get the time! > ------- > Do you hope that by listening to this list, you'll get the vital hint that'll make you win the > prize ? > ------- >Just interested in how other people are approaching the problem > ------- > Do you own an Eternity puzzle ? > ------- > Yes > ------- > What's your best attempt by hand ? > ------- >Haven't counted - probably ~ 1/2 > ------- > What's your best attempt by computer ? > ------- >None yet, haven't got the code quite right yet. > ------- > What language / system / pc are you using ? > ------- > PC PII 333, Turbo C > ------- > What algorithms / heuristics do you use for Eternity > (brute force, backtracking, genetic algothims, simulated annealing, SECRET) ? > ------- >Genetic algorithms + modifications > ------- > Did you type in all 209 pieces yourself ? > ------- >No > ------- > Did you try any simpler variations of Eternity ? > ------- >Yes - manually completed some of the other commercial puzzles, and tried a simpler version on PC before starting coding full puzzle. > ------- > Do you know some other interesting web-sites ? > ------- >Not related to Eternity...... > ------- > Other hobbies ? > ------- >Aikido (sport) > ------- > Other physical puzzles ? > ------- > Um... I used to do the rubik's cube. > ------- > Other programming projects ? > ------- >I do a lot of programming for my research, including DSP programming, and windows. > ------- > Are you willing to show the group your source code (after removing your secret functions) ? > ------- >Maybe > ------- > Any other stuff you like to add ? > ------- >Not really > ------- > Do you know any other interesting problems ? > ------- > I can't think of any at the mo.. > ------- > What's the meaning of life ? > ------- >To figure out the answer to that question > ------- > How are you going to spend your 1000.000 ? > ------- >Carefully > > > > > _______________________________________________________________________________ _______________________________________________________________________________ Message: 20 Date: Tue, 6 Jul 1999 00:30:08 +0100 From: "Thomas Voigt" Subject: Estimating the run time of brute force algorithms > From: Douglas Hogan > I've programmed the puzzle in C++ and think the code is fairly tight apart > from the improvements below. I am a little disillusioned with the puzzle now > and get the impression that implementing the improvements will cut the > solution time from 10^100 years to 10^99 years!! (...) > My best result is ~165 pieces after a 2 hour run. It doesn't seem to get any > better than this no matter how long the program is run. I am not taking into > account parity issues. I do analyse the board before placing a piece to make > sure it doesn't create illegal spaces. Did you try to estimate the size of the search tree ? I found this always very useful if I had a problem of this size. (It may help you to figure out if your algorithm runs 2 weeks or 10^99 years :-) For those of you interested, Donald E. Knuth developed a simple algorithm for such estimates (check Mathmatics of Computation 29, 1975). To put it short: If you have your search tree then you do a random descent. We want to know the estimated number of nodes at each level (e[n]) and the total search time (t). Start with the root node (set e to 1, t to 0). In each step you figure out the number of sucessors (k) and the time (or operations) required to calculate them (t0). Set e[k] := e*n and add e*t0 to t. Select one sucessor at random and continue the procedure until there are no more sucessors. Summing up all e[k] gives an estimate for the total number of nodes in the search tree. Since e will depend highly on the chosen branches you'll want to repeat this procedure a few times and calculate the average values. This method relies somewhat on a bell-shaped tree but this should be the case here. tv (I wish my eternity solver would be close enough to completion to try this estimate, but since I have few time it will take a few weeks more :-) -- 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: 21 Date: Tue, 6 Jul 1999 00:30:07 +0100 From: "Thomas Voigt" Subject: Re: Who are You ? > QUESTIONS > -------------- > What's your..... > name : Thomas Voigt age : 26 occupation : student/programmer city : Berlin country : Germany email : spock@berlin.snafu.de homepage : - > > ------- > How did you hear about this list (website / friends) > ? > ------- friends > > ------- > Are you an active problem-solver, or just here out of > general interest ? > ------- active > ------- > Do you hope that by listening to this list, you'll > get the vital hint that'll make you win the > prize ? > ------- If somebody had an algorithm then he would be crazy to tell us ... :-) > ------- > Do you own an Eternity puzzle ? > ------- No. > ------- > What's your best attempt by hand ? > ------- - > ------- > What's your best attempt by computer ? > ------- 149 (10 minutes Screen saver :-) > ------- > What language / system / pc are you using ? > ------- Depends on the problem (currently Delphi/CBuilder/g++) / Windows & Linux / P200 > ------- > What algorithms / heuristics do you use for Eternity > (brute force, backtracking, genetic algothims, > simulated annealing, SECRET) ? > ------- Dunno yet. I have several ideas, I'll see if any of them work ... > ------- > Did you type in all 209 pieces yourself ? > ------- No. > ------- > Did you try any simpler variations of Eternity ? > ------- No. > ------- > Do you know some other interesting web-sites ? > ------- Not yet :-) > ------- > Other hobbies ? > ------- Football, board games, music. > ------- > Other physical puzzles ? > ------- Actually I hate conventional puzzles :-) > ------- > Other programming projects ? > ------- Several small ones. > ------- > Are you willing to show the group your source code > (after removing your secret functions) ? > ------- Sure, why not ? > ------- > Any other stuff you like to add ? > ------- It's unlikely that I'll solve the problem, but I find it very interesting :-) > ------- > Do you know any other interesting problems ? > ------- Is NP=P ? :-) But seriously, if you are interested in enumeration problems then you don't have to look far. Number of facets that a n-dimensional 0/1 polytope can have, grid triangulations, magic squares, knight's tours etc. All these problems can be described in 2 sentences, but we know only crude estimates for the number of solutions. > ------- > What's the meaning of life ? > ------- I could earn more than 1.000.000 if I could answer that question :-) > ------- > How are you going to spend your 1000.000 ? > ------- No idea. 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: 22 Date: Mon, 05 Jul 1999 23:05:26 GMT From: steve.waddicor@virgin.net (Steve Waddicor) Subject: Re: Complexity On Mon, 5 Jul 1999 14:08:47 +0200, "Christophe Weibel" wrote: >Somewhere, someone (Monckton or a insurance company) is willing to bet one >million pounds that NO program will solve it... Not at all. Suppose they have allocated 10 pounds out of the 30 pounds selling price to go into the prize fund. Then all they're betting is that they'll sell 100,000 of the things before Sept 2000. They're getting a lot of publicity, so it doesn't look like too dificult a target. In fact come to think of it, they're probably saving quite a bit on payed for publicity. Regards, Steve. _______________________________________________________________________________ _______________________________________________________________________________ Message: 23 Date: Tue, 6 Jul 1999 01:23:10 +0200 From: =?iso-8859-1?Q?Manuel_Carrillo_Jim=E9nez?= Subject: size of the box I would like to know the size of the eternity original box, and the weight. Could anybody that had the game help me? _______________________________________________________________________________ _______________________________________________________________________________ Message: 24 Date: Tue, 6 Jul 1999 01:23:10 +0200 From: =?iso-8859-1?Q?Manuel_Carrillo_Jim=E9nez?= Subject: size of the box I would like to know the size of the eternity original box, and the weight. Could anybody that had the game help me? _______________________________________________________________________________ _______________________________________________________________________________ Message: 25 Date: Tue, 6 Jul 1999 00:40:21 -0500 From: path@multipro.com.au Subject: Re: Opinion please Patrick M Hamlyn@MULTIPROGRAMMING 07/06/99 01:40 PM >From: Jeanette Hauser >Is a computer essential? Excuse the delay, my email was 'in flux' for a while there, and this got bounced. Well right now, the computer's not doing me any good, so I'd say you have *more* chance doing it manually than my program has. I hope to change that though. There are a few things you could do to give yourself a 'leg-up': Try fitting 'difficult' pieces together into 'easier' shapes. A difficult piece is basically one with more edges, eg #166 which has 12. If you make up 'combination pieces' with 'smoother' outlines, then you may be able to tile faster. You can make the combination pieces by manually fitting together groups of difficult and easy pieces until you get a 'nice' shape, then cut out a piece of paper that shape, and write on it the numbers of the pieces that went to make it up (and their outlines, you don't want to have to solve another puzzle later). Repeat this a few hundred times until you have a 'compound shape' for every difficult piece. If you can get lots of difficult pieces into a shape, so much the better. Also, try to use *different* sets of pieces for each compound shape as far as possible. You have to keep track of which pieces are used by each one when you use it, so less pieces in common allows more options. Now you can tile using the pieces of paper (use Blue-tack/Prestick/whatever your local name is for that sticky stuff to hold the paper shapes in place). Whenever you tile, always look for 'useful' compound shapes you make along the way, and make up a bit of paper to add to your library whenever you make a good one. With a big enough library of these shapes, you should be able to tile much faster, re-doing less work along the way - as long as you make shapes that can fit together reasonably well. There may be something you can do to limit the external shapes of your compound pieces to make them fit together better - eg a rule that says, all half-drafters must be paired so the compound shape is a polyiamond (ie made up exclusively of equilateral triangles). This may not be possible, but there is sure to be some other simple rule out there that you can use instead. One possibility is to make 'rectilenear' shapes, ie all vertices are right angles.These have a much reduced set of external angles, and can also be placed 'off-grid' giving greater usefulness of each compound shape. _______________________________________________________________________________ _______________________________________________________________________________