From: To: Subject: [eternity] Digest Number 1 Date: Friday, June 25, 1999 6:00 AM --------------------------- ONElist Sponsor ---------------------------- Books, music, videos, gifts, e-cards, auctions-find them at AMAZON.COM. Browse Earth's Biggest Selection! Enjoy everyday savings of up to 50%! Click Here ------------------------------------------------------------------------ There are 22 messages in this issue. Topics in today's digest: 1. up to 36 and counting.... From: Andreas Gammel 2. Re: up to 36 and counting.... From: Jason Armitage 3. parity issues From: "Ed Pegg Jr." 4. Re: parity issues From: James Kittock 5. Re: Known Pieces From: James Kittock 6. Re: up to 36 and counting.... From: James Kittock 7. Vicher's page?!? From: James Kittock 8. Re: Vicher's page?!? From: NickGard@aol.com 9. Re: Known Pieces From: Paul Why 10. Re: Known Pieces From: path@multipro.com.au 11. Re: Vicher's page?!? From: "Brendan Owen" 12. Re: parity issues From: "Brendan Owen" 13. Re: parity issues From: path@multipro.com.au 14. eternity From: "Miroslav Vicher" 15. Re: [Re: [eternity] parity issues] From: david sprenkle 16. Re: parity issues From: "Brendan Owen" 17. Re: parity issues From: path@multipro.com.au 18. Re: parity issues From: Andreas Gammel 19. Re: parity issues From: "Brendan Owen" 20. Re: up to 36 and counting... From: "Dunne, Mike" 21. Re: parity issues From: "Bob Harris" 22. Parity example and list From: "Miroslav Vicher" _______________________________________________________________________________ _______________________________________________________________________________ Message: 1 Date: Thu, 24 Jun 1999 17:02:27 +0200 From: Andreas Gammel Subject: up to 36 and counting.... Ok, a little status report After 1 day, the Eternity List has now 35 (no, oops.., just a new member coming in) 36 members from about 10 countries. Of the 42 personal invitations, 14 people subscribed. The other 21 members must have responded to my message in some puzzle newsgroups. I also see that several people are making attempts to crack the little bugger. I heard of a few results of around 100 pieces. The best effort up till now is 192 pieces. (or has it been improved yet...?) Although visually very nice (I hang a printout of the 150 piece attempt on my monitor) I think that mathematically this result is not very interesting. We are trying to place 209 pieces on a board. So we write an algorithm that puts them on the board one by one. What this means that we have to search a tree with 1 root and lets say 10^200 leaves. If one assumes there's only a single right solution, this means that there are (10^200 - 1) wrong solutions. By walking from the root to a leaf, which is 'putting pieces on the board', we pass the 150 pieces point. This means that at this point in the progress there are 10^150 possible semi-solutions. The 150 piece attempt only shows 1 of these 10^150 possibilties, which is probably at the extreme left site of the tree. Of course, al lot of attempts during the tree-traversal will fail. This means that any child-tree of this failed tree node can be skipped. The closer this failure occurs to the root of the tree, the larger the child-tree that can be skipped will be, thereby limitiing the total number of nodes to be searched. This would be my strategy to make an algorithm. This all sounds nice, but it is only useful if the number of childs per node is limited to 1. If the problem is limited to say 2^200, it still takes a few big bangs to solve it. But of course, this blah-blah is only valid if one assumes a strategy of actually putting pieces on the board. What could be interesting is to study a number of these 150-attempts and try to find similarities. Another idea I spend many happy hours thinking about is the concept of 'conversion'. With this I mean studying problems that are in some way similar to this problem, then converting it to that 'space', solving it, and converting it back to this one. Some classic problems were cracked in this way, like Fermat's Last Theorem and Ramanujan's Pi Fomula. The discussion about GA (Genetic Algorithms) and SA (Simmulated Annealing) I don't believe too much in myself. These methods assume that solutions that are 'almost' or 99% correct are acceptable. The problem is that 'almost' does not exist in this problem. well, that's all folks Andreas _______________________________________________________________________________ _______________________________________________________________________________ Message: 2 Date: Thu, 24 Jun 1999 18:17:38 +0100 From: Jason Armitage Subject: Re: up to 36 and counting.... An interesting observation on the difficulty of the puzzle, but there is one factor in our favour, there is more than solution. Even if there is only one combination, which I don't believe having currently got over 400 solutions for the delta puzzle, then there would be at least 22 different solutions, taking into account the puzzles symmetry. If the solution has any parts that are symmetrical than that would also generate different solutions. And if you look at it from a tree point of view the first piece in one solution might be the 90th of another, the last piece of yet another, and so on. This would mean that there could be thousands or tens of thousands of possible solutions, or more, but even millions is a drop in the ocean compared to the number of combinations. Jason. Andreas Gammel wrote: > From: Andreas Gammel > > Ok, a little status report > > After 1 day, the Eternity List has now 35 (no, oops.., just a new member > coming in) 36 members from about 10 countries. > Of the 42 personal invitations, 14 people subscribed. The other 21 > members must have responded to my message in some puzzle newsgroups. > > I also see that several people are making attempts to crack the little > bugger. I heard of a few results of around 100 pieces. The best effort > up till now is 192 pieces. (or has it been improved yet...?) > > Although visually very nice (I hang a printout of the 150 piece attempt > on my monitor) I think that mathematically this result is not very > interesting. We are trying to place 209 pieces on a board. So we write > an algorithm that puts them on the board one by one. What this means > that we have to search a tree with 1 root and lets say 10^200 leaves. If > one assumes there's only a single right solution, this means that there > are (10^200 - 1) wrong solutions. By walking from the root to a leaf, > which is 'putting pieces on the board', we pass the 150 pieces point. > This means that at this point in the progress there are 10^150 possible > semi-solutions. The 150 piece attempt only shows 1 of these 10^150 > possibilties, which is probably at the extreme left site of the tree. > > Of course, al lot of attempts during the tree-traversal will fail. This > means that any child-tree of this failed tree node can be skipped. The > closer this failure occurs to the root of the tree, the larger the > child-tree that can be skipped will be, thereby limitiing the total > number of nodes to be searched. This would be my strategy to make an > algorithm. > > This all sounds nice, but it is only useful if the number of childs per > node is limited to 1. If the problem is limited to say 2^200, it still > takes a few big bangs to solve it. But of course, this blah-blah is only > valid if one assumes a strategy of actually putting pieces on the board. > > What could be interesting is to study a number of these 150-attempts and > try to find similarities. > > Another idea I spend many happy hours thinking about is the concept of > 'conversion'. With this I mean studying problems that are in some way > similar to this problem, then converting it to that 'space', solving it, > and converting it back to this one. Some classic problems were cracked > in this way, like Fermat's Last Theorem and Ramanujan's Pi Fomula. > > The discussion about GA (Genetic Algorithms) and SA (Simmulated > Annealing) I don't believe too much in myself. These methods assume that > solutions that are 'almost' or 99% correct are acceptable. The problem > is that 'almost' does not exist in this problem. > > well, that's all folks > Andreas > > --------------------------- 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. > > ------------------------------------------------------------------------ _______________________________________________________________________________ _______________________________________________________________________________ Message: 3 Date: Thu, 24 Jun 1999 10:15:56 -0600 From: "Ed Pegg Jr." Subject: parity issues The 59 hexadudes problem has been solved by Patrick Hamlyn. See www.mathpuzzle.com for a diagram, and for a full explanation of parity. I think I see groupings of pieces by parity in the 59 piece solution. Can anyone modify an existing Eternity solver to color in three side by side partial Eternity solutions in the same fashion? For those using brute force algorithms, parity might help. Many of these programs start with the pieces arranged randomly. Do that. Then have the computer look at parity, and shuffle some pieces around so that the diagram will stay mostly balanced as the pieces are placed. This should speed up the programs by some insignificant factor. --Ed Pegg Jr. _______________________________________________________________________________ _______________________________________________________________________________ Message: 4 Date: Thu, 24 Jun 1999 11:09:52 -0700 From: James Kittock Subject: Re: parity issues > For those using brute force algorithms, parity might help. > Many of these > programs start with the pieces arranged randomly. Do that. > Then have the > computer look at parity, and shuffle some pieces around so > that the diagram > will stay mostly balanced as the pieces are placed. This > should speed up > the programs by some insignificant factor. Actually, I noticed the parity issue early on and specifically chose to ignore it, in the sense that my encoding forces the pieces to go "with the grain". I figure if I can convince myself that there isn't a "with the grain" solution, then I'll worry about looking for an against the grain solution. :-) --james _______________________________________________________________________________ _______________________________________________________________________________ Message: 5 Date: Thu, 24 Jun 1999 11:29:47 -0700 From: James Kittock Subject: Re: Known Pieces Hi Patrick, > Well I've tried about a dozen or two dozen different tacks so far, all > hitting a brick wall. They included making twelve identical > sections, 6 > identical sections, 3 identical sections, non-identical sections, > jagged-edged sections, direct attack with pruning and > directed searching > techniques, etc. All have come to nothing as yet. I can now place 150 > pieces in around 2 minutes, 170 in an hour or two, but no more. Based on my experiments with a 36 piece pseudo-eternity puzzle, this does not surprise me. I found that placing about 5/6 of the pieces is doable in a reasonable amount of time. In the case of the 36 piece puzzle, that's about 30 pieces, in the case of the 209 piece puzzle it would be about 170. So your result seems to corroborate that empirical finding. > If you remove any 160 pieces which tile something (anything), > the remainder don't tile anything. I call this the E-property. This sounds very interesting, but I'm not 100% sure I follow you. Are you saying that if I start with the pieces numbered 1 through 209 (or 0 through 208 like good programmers :-), and 1 through 160 happen to tile about 3/4 of the board, then you start over with just pieces 161 through 209, those 49 pieces won't tile? If so, that is very interesting, and feels somehow related to the above finding about it being easy to tile 5/6 of the grid. It is almost as if some critical angle or edge length gets "used up" too easily. > How does your GA work? > How good is a 'pretty good' solution - how many > pieces placed? How many pieces could it place on the whole > Eternity grid in a reasonable time? I haven't coded up the full puzzle, mainly because I've been lazy about encoding the 209 pieces. If I get some time, I could try it, but I am not super optimistic about the GA. Anyhow, the present GA works like this. The "genome" is a sequence of triplets, where x and y are locations on the grid and r is the orientation of the piece. I create a population of lots of random genomes, and then apply a fitness measure. The next generation is determined by random selection of "mating pairs", weighted by fitness. I do a simple cross-over of the parent genomes to produce an offspring genome. Then there is some probability of a mutation (re-randomization of one or more of x, y, or r). I have experimented with x and y being both absolute and relative, i.e. having x2 and y2 be offsets relative to x1 and y1. I thought the relative approach might work better with the cross-over, since it would tend to preserve clumps of pieces that fit together well. In the end, it didn't seem to make a lot of difference. The trickiest thing was coming up with a fitness measure. In the end, I did something very simple--I think it was total area covered. I experimented with special fitness penalties for things like unfillable holes, but it didn't seem to help much. The biggest problem I had was a typical one with GA's--the pool would pretty rapidly converge on a few extremely fit partial solutions that were nowhere near the real solution (the benefit of working with a puzzle I know the solution to is that I can tell how good or bad the solver is doing!). After that, any mutations would be very unlikely to improve anything, so the population would reach stasis. So that's it for the GA for now. The one additional experiment I'd like to do is to run, say, 1000 fixed-length "sessions" of the GA, starting from a different random population each time, and seeing if any pieces end up in the same place in the "best" genome in each session more times than would be expected by chance. On the 36-piece grid, there is on the order of 3000 placements for each piece in my encoding, so if a piece appeared in the same place even a few times, that would be very interesting. > If you tell me which 36 pieces you used and the shape you > tried to make I'll see if my 'directed solver' makes any > headway. It got the 59 hexadudes shape in around one hour. Wow, that's cool. I'm sure it's better than mine. Mine still can't solve the 36 piece puzzle, although it is admittedly pretty dumb still. What would be the best way to get you the pieces? I doubt my particular encoding would be much use to you, and I don't have the pieces in any electronic form. I just did a screen dump of the java applet and worked from there. > I am starting to believe that any successful approach will have to > circumvent the E-property by 'working backwards' in some way. > I've tried several 'backward' approaches, but to no avail. They all > required order N*N operations on lists of many billions of partial > tilings. I think there is more analysis that needs to be done to the puzzle to better understand your and my empirical findings about tiling and the "E-property". Unfortunately, I'm more of a programmer than I am a mathematician. I get the feeling that if the right N pieces are placed in the right locations, the solution will pretty much "crystallize" out. But as you pointed out, finding those hard pieces is pretty much impossible. In fact, it is probably equivalent to solving the puzzle. :-) Even if we could guess heuristically that, say 5 pieces were the most critical and we placed those first, there are still many, many possible placements of those 5 pieces to use as starting points for deeper exploration. --james PS I was just checking on my solver and it found a 34-piece solution to the 36-piece puzzle, which appears to be mostly correct. The first place I can see it went wrong was with the 8th piece placed. That wrong placement meant that the last 2 pieces didn't fit, although it otherwised tiled the board very nicely. An interesting question would be if there is a way to help the program figure out to preserve the 9th through 34th placements and back up to the 8th piece to see if it could plug the remaining holes simply by moving that piece... _______________________________________________________________________________ _______________________________________________________________________________ Message: 6 Date: Thu, 24 Jun 1999 11:46:19 -0700 From: James Kittock Subject: Re: up to 36 and counting.... > An interesting observation on the difficulty of the puzzle, > but there is one factor in our favour, there is more than > solution. I'd actually be interested in starting a side betting pool on whether more than one solution exists (not counting reflections and rotations on the board, obviously). Assuming there are any takers for the "unique" side (I'm not sure which I believe at the moment). >> Although visually very nice (I hang a printout of the 150 >> piece attempt on my monitor) I think that mathematically >> this result is not very interesting. I said the same thing to Ed Pegg in a private e-mail. My experimentation leads me to believe this is pretty easy, actually. And what you are left with, as Patrick Hamlyn has shown, is a bunch of non-fitting pieces. Hmm, I wonder if it would be worth using as a heuristic the "tileability" of the remaining pieces? This might be particularly effective with a solution that tries to place pieces along an outside perimeter. > > This all sounds nice, but it is only useful if the number > > of childs per node is limited to 1. If the problem is limited > > to say 2^200, it still takes a few big bangs to solve it. Depressing, isn't it? I am beginning to believe that a depth-first search (DFS) just won't work for this puzzle. And, of course, breadth-first (BFS) is clearly impossible. I'm planning to modify my program to do a form of beam search, which is a hybrid of DFS and BFS. It basically keeps an "open" list of finite size. I plan to invent some heuristics that let me pick the nodes that I expand, at the expense of bypassing possible solutions. If I can exhaustively search even a small part of the tree, I can progressively relax my heuristics. If my heuristics are good guesses, then I solve the problem in finite time. >> Another idea I spend many happy hours thinking about is the >> concept of 'conversion'. With this I mean studying problems >> that are in some way similar to this problem, then converting >> it to that 'space', solving it, and converting it back to this >> one. Some classic problems were cracked in this way, like >> Fermat's Last Theorem and Ramanujan's Pi Fomula. The computer scientist in me says that this is a nice thought, but that it won't help. This problem is clearly NP-complete and will be no matter how you transform it. While you can make the representation faster to compute, you can't dodge the fundamental complexity of the problem. I did spend a bit of time thinking about a representation that would be quick to compute on. I came up with something that eliminates the parity issue (by assuming everything goes with the grain) and is very fast for the computer to compute whether a piece fits or not. I'm sure there are other good representations. >> The discussion about GA (Genetic Algorithms) and SA (Simmulated >> Annealing) I don't believe too much in myself. These methods >> assume that solutions that are 'almost' or 99% correct are >> acceptable. The problem is that 'almost' does not exist in this >> problem. The problem is less that these things tend to find "almost" solutions and more that there are many, many "almost" solutions that are nowhere near the 100% correct solution. If the fitness landscape was better-behaved, the GA or SA might have a chance. --james _______________________________________________________________________________ _______________________________________________________________________________ Message: 7 Date: Thu, 24 Jun 1999 12:03:43 -0700 From: James Kittock Subject: Vicher's page?!? What's up with the picture at http://alpha.ujep.cz/~vicher/puzzle/ Is he trying to give me a heart-attack? What is that picture of, anyhow?!?! --james James Kittock - Interval Research Corporation email: kittock@interval.com phone: 650.856.7257 _______________________________________________________________________________ _______________________________________________________________________________ Message: 8 Date: Thu, 24 Jun 1999 16:01:07 EDT From: NickGard@aol.com Subject: Re: Vicher's page?!? kittock@interval.com writes: > What's up with the picture at http://alpha.ujep.cz/~vicher/puzzle/ > > Is he trying to give me a heart-attack? What an impressive picture! At first sight all the pieces look familiar. But do not worry, for I have spotted the following: A piece on the top centre edge, coloured medium orange; and A piece on the right hand edge, coloured dark reddish, are identical, and correspond to piece number 25 of the puzzle. And, while writing this, I've just spotted two number 120 pieces. There may well be other flaws. Glad I didn't stop my computer program. :) Nick. _______________________________________________________________________________ _______________________________________________________________________________ Message: 9 Date: Fri, 25 Jun 1999 00:46:23 +0100 From: Paul Why Subject: Re: Known Pieces In message <4825679A.00306958.00@mantaray.multipro.com.au>, path@multipro.com.au writes: >If you tell me which 36 pieces you used and the shape you tried to make, >I'll see if my 'directed solver' makes any headway. It got the 59 hexadudes >shape in around one hour. Well done! The Cray fund grows just that little bit larger. :-) Incidentally, which version of your program managed to crack it? The reason I ask is that Ed Pegg's challenge had been running for some time. For your program to solve it in around an hour implies that either you'd only recently started to attack it (which I don't believe), or you'd managed to tweak the algorithm in such a way as to eliminate blind alleys much more quickly. As an aside, do people generally write solvers in such a way that they can be restarted from a particular point? I'm imagining the scenario where a program has been running for days, then for some reason the machine requires a reboot, or there's a power failure. It could avoid frustration if the program didn't have to start from scratch again. As it stands, my (not yet working) program uses recursion, and saving its entire state would be difficult. It could be written so that e.g. the stack and function arguments are implemented explicitly (and can thus be written to disk periodically), but I'm not sure if it's worth the effort. Paul -- Paul Why paul@clastech.demon.co.uk _______________________________________________________________________________ _______________________________________________________________________________ Message: 10 Date: Fri, 25 Jun 1999 08:29:57 +0800 From: path@multipro.com.au Subject: Re: Known Pieces Patrick M Hamlyn@MULTIPROGRAMMING 06/25/99 08:29 AM From: Paul Why >Incidentally, which version of your program managed to crack it? The >reason I ask is that Ed Pegg's challenge had been running for some time. >For your program to solve it in around an hour implies that either you'd >only recently started to attack it (which I don't believe), or you'd >managed to tweak the algorithm in such a way as to eliminate blind >alleys much more quickly. I used a direct attack, with 1-step lookahead and three different 'position evaluation' criteria. The only reason I hadn't cracked it before is I hadn't correctly counted all the parities. In fact I had identified but not yet even given a name to the East-West parity, let alone counted it. Once I got all the parity counts right (with help from Ed Pegg), I was able to make a shape in a few minutes and solve it in an hour. Prior to that I had spent a few hours on untilable shapes, largely because I wanted to develop and tune my solver on something more manageable than the E-puzzle. >As an aside, do people generally write solvers in such a way that they >can be restarted from a particular point? I'm imagining the scenario >where a program has been running for days, then for some reason the >machine requires a reboot, or there's a power failure. It could avoid >frustration if the program didn't have to start from scratch again. >As it stands, my (not yet working) program uses recursion, and saving >its entire state would be difficult. It could be written so that e.g. >the stack and function arguments are implemented explicitly (and can >thus be written to disk periodically), but I'm not sure if it's worth >the effort. Yes the re-start capability is essential, especially if you live in an area that gets power failures, (ie planet Earth), or you run some form of Windows, or you need to move your computer, do something else with it etc etc. My program uses recursion too, all I do is save the current value of the loop counter at each level, then insert those as start points at each level of the recursion on a restart. All the other calculations that occur are deterministic, so this works fine. If I added a random element for example, then I would have to seed the random number generator the same way every time in order to ensure that it was still restartable. Whenever I change the algorithm tuning parameters or similar, I have to start over. It is possible though, to keep an audit trail of tuning parameters in your saved status file so that you keep using the same tuning parameters until you start placing new stuff. My solver attempts to save its status peridically in case of power failures or crashes too. Making it check to see whether it's time to save without slowing it down is a real trick. You have to find some part of you algorithm where code is executed regularly but not too often and put the check there. Aside to James Kittock: I think you may be confusing the parity issue with grid alignment. Read Ed Pegg's article at mathpuzzle.com, there's a nice diagram which shows all three parities. What you need to do is keep track of the overall parity balance of the untiled section of the grid, and match it with the parity balance of the remaining pieces as far as possible. IE don't place the first 100 pieces in such a way that you are left with +50 up-drafters, and the possible orientations of the remaining pieces is thus restricted since they must correct this imbalance. I don't do this yet, I'm banking on the hope that the area left will have roughly balanced parity since it is geographically contiguous, and that any random group of pieces will probably be fairly close to balanced too. _______________________________________________________________________________ _______________________________________________________________________________ Message: 11 Date: Fri, 25 Jun 1999 11:08:46 +1000 From: "Brendan Owen" Subject: Re: Vicher's page?!? Hi All, > > From: James Kittock > > What's up with the picture at http://alpha.ujep.cz/~vicher/puzzle/ > I just analized Vicher's "solution" there are 35 peices not used 142 peices used once 29 peices used twice 3 peices used three times Regards Brendan _______________________________________________________________________________ _______________________________________________________________________________ Message: 12 Date: Fri, 25 Jun 1999 16:26:58 +1000 From: "Brendan Owen" Subject: Re: parity issues Hi All, > From: "Ed Pegg Jr." > > The 59 hexadudes problem has been solved by Patrick Hamlyn. See > www.mathpuzzle.com for a diagram, and for a full explanation of parity. I > think I see groupings of pieces by parity in the 59 piece solution. Can > anyone modify an existing Eternity solver to color in three side by side > partial Eternity solutions in the same fashion? I could modify my image shape recognition program. I just need to work out the different 3 parities for all the pieces. Also I think that it would be useful to work out the sign of the parity after the piece has been placed and colour code that as well. Regards Brendan _______________________________________________________________________________ _______________________________________________________________________________ Message: 13 Date: Fri, 25 Jun 1999 14:50:51 +0800 From: path@multipro.com.au Subject: Re: parity issues Patrick M Hamlyn@MULTIPROGRAMMING 06/25/99 02:50 PM Brendan Owen wrote: >I could modify my image shape recognition program. I just need to work out >the different 3 parities for all the pieces. This sounds like a nifty little program. I for one would not complain if you made it available! It might be nice if you made it 'extensible' to different sets of pieces as well - polyominoes, polyhexes etc. I think Bob Harris is planning to write the opposite, a program that will allow people to interchange electronic piece descriptions in a common language and which will then draw them from the piece descriptions. Also ideally you would be able to plug in a converter to and from your own personal data format for pieces. Adding your recogniser would make a fine set of utilities for swapping around info like this. >..Also I think that it would be >useful to work out the sign of the parity after the piece has been placed >and colour code that as well. Another thing you could do with Eternity pieces: List all the orientations of the 'unpaired drafters' for each piece (12 possible orientations. I have a spreadsheet with these, generated by Bob Harris' program). Now at any point during the solving process, you can do a computation to see whether the pieces can be oriented in such a way that all the unpaired drafters can be placed correctly into the remaining empty grid. Obviously it's a huge computation except towards the end of solving, but perhaps you can keep things 'close to balanced' as with the parity. Colour-coding these would be nice too. Now all you need is a colour-coded grid, and pieces which display the correct colouring automatically as you rotate them wrt the grid. It could all be done with fairly simple technology too! You might as well put a few buttons along the edge to change which sorts of parity are displayed while you're at it. Also. it might be nice if you could touch a stylus (or your finger?) to a cell, and have all the pieces that fit into that cell light up, and those that will fit but make it impossible to fill another cell should light up a different colour. Sounds like a job for a program maybe rather than a mechanical device. ===== I've been racking my brain to come up with a better way of using these orientation counts, can anyone help out? _______________________________________________________________________________ _______________________________________________________________________________ Message: 14 Date: Fri, 25 Jun 1999 09:05:22 +0200 From: "Miroslav Vicher" Subject: eternity I apologize to everyone who took my joke seriously. My web server is down. I moved my pages to http://mbox.troja.mff.cuni.cz/~vicher/puzzle/. Congratulation to Patrik Hamlyn for solution of haxadudes M. Vicher _______________________________________________________________________________ _______________________________________________________________________________ Message: 15 Date: 25 Jun 99 00:30:41 PDT From: david sprenkle Subject: Re: [Re: [eternity] parity issues] Parity Shmarity With all this parity talk going around I wrote a program that would randomly choose a set of piece with a random side and rotation and then randomly turn the pieces until the parity is correct for the puzzle. Then it trys to make a puzzle out of them. I have written all my programs in perl just to see if they work and I am now converting them to C. It seemed to work in perl but it was sloooow. Work as in could find parity quickly and sometimes find non solutions quickly(couple hours). I just figure it would be a good program to have constantly running on some unused machine. People do win the Lotterys you know. ____________________________________________________________________ Get your own FREE, personal Netscape WebMail account today at http://webmail.netscape.com. _______________________________________________________________________________ _______________________________________________________________________________ Message: 16 Date: Fri, 25 Jun 1999 17:54:18 +1000 From: "Brendan Owen" Subject: Re: parity issues Hi All, > Patrick M Hamlyn@MULTIPROGRAMMING > 06/25/99 02:50 PM > > Brendan Owen wrote: > > >I could modify my image shape recognition program. I just need > to work out > >the different 3 parities for all the pieces. > > This sounds like a nifty little program. I for one would not complain if > you made it available! I wouldn't complain if you made your code available. :) At the moment I'm just getting it to index each pixel with its shape number. This works out nicely because 209 (pieces) < 256 (grey shades). That way it is possible to give each index a different colour depending on your requirements. I'll put the program in the upload directory when I get it working. The image format I use is PGM and PPM. > It might be nice if you made it 'extensible' to > different sets of pieces as well - polyominoes, polyhexes etc. This shouldn't be too hard to make it more general because it was ported from my research code which is automatic fish recognition. Although at the moment my research seems to be the eternity puzzle :) > I think Bob > Harris is planning to write the opposite, a program that will allow people > to interchange electronic piece descriptions in a common language > and which > will then draw them from the piece descriptions. Also ideally you would be > able to plug in a converter to and from your own personal data format for > pieces. Adding your recogniser would make a fine set of utilities for > swapping around info like this. When we have a standard position and orientation format. I can get the program to output the positions, orientations and shape numbers. My position format involves an x and y position on a 30 degree squed grid. Where each grid "square" is made up of two equilateral triangles. My orientation is an index between 0 and 11. 0-5 are the 60 degree rotations anticlockwise. 6-11 are first flipped around the y-axis and then rotated. My shape numbers are not quiet the same as CMs order. The shapes are first normalised and then sorted. I'll have to number then in CMs order at some stage. ____________ / / / / /___/___/___/ / / / / /___/___/___/ Brendan _______________________________________________________________________________ _______________________________________________________________________________ Message: 17 Date: Fri, 25 Jun 1999 15:54:43 +0800 From: path@multipro.com.au Subject: Re: parity issues Patrick M Hamlyn@MULTIPROGRAMMING 06/25/99 03:54 PM > I wouldn't complain if you made your code available. :) My answer is the same as yours - as soon as it works :>> _______________________________________________________________________________ _______________________________________________________________________________ Message: 18 Date: Fri, 25 Jun 1999 10:22:34 +0200 From: Andreas Gammel Subject: Re: parity issues Can anyone explain to me what PARITY means, starting with a simple example and then applied to Eternity ? Andreas PS 46 members now.. _______________________________________________________________________________ _______________________________________________________________________________ Message: 19 Date: Fri, 25 Jun 1999 18:33:11 +1000 From: "Brendan Owen" Subject: Re: parity issues > Can anyone explain to me what PARITY means, starting with a simple example > and then applied to Eternity ? Have you looked at the at www.mathpuzzle.com site? This has a good explaination. If not I can have a shot of explaining it. > > Andreas > > PS 46 members now.. > Brendan _______________________________________________________________________________ _______________________________________________________________________________ Message: 20 Date: Fri, 25 Jun 1999 10:18:29 +0100 From: "Dunne, Mike" Subject: Re: up to 36 and counting... > Even if there is only > one combination, which I don't believe having currently got over 400 > solutions for the delta puzzle, ... Jason, I don't want to depress you, but have you solved the heart puzzle ? I've analysed all possible positions and found only 1 solution ! (ignoring symmety's and ignoring the possibility of a bug in my program). Can anyone else verify this ? Mike. P.S. On another note, I too have observed Patrick's "E-property".