Calcudoku puzzle forum https://www.calcudoku.org/forum/ |
|
The shape of the cages (structure and names) https://www.calcudoku.org/forum/viewtopic.php?f=3&t=73 |
Page 1 of 2 |
Author: | jomapil [ Fri Oct 07, 2011 9:20 am ] |
Post subject: | Re: The shape of the cages (structure and names) |
Interesting matter! I tried to obtain a formula for the number of cages: 5=(2+2)+1 n=3 12=(5+5)+2 n=4 35=/(12+12)+5 n=5 and it fails u(n+1)=2 x u(n)+(n-1). Will it be, ever, u(n+1)>2 x u(n)+(n-1) for n>4? In that case For n+1=6 (7cages ) we only can say u(6)>82. Can any accredited mathematic obtain a formula? I'm waiting more curiosities from clm. |
Author: | starling [ Fri Oct 07, 2011 12:22 pm ] |
Post subject: | Re: The shape of the cages (structure and names) |
I think the formula's going to be based off the number of available surfaces at any given point, and then removing rotationally similar ones, but can't think of a way to avoid things like counting ones that end up identical separately. I can give you a theoretical max for any number, but can't get it lower than that because I haven't thought of a way to exclude identical solutions. There can't be more than 560 containing 7 cells. Obviously this number is far too high, but it does provide some sort of an upper limit. Actually, I may have a solution. Every single solution must fit into an x by y box, where x+y<or =(the number of cells + 1), and xy must be > or = to 7. Thus, with 7 cells, it can be in a box 1x7, 2x6, 3x5, 4x4, etc. These all calculate easily, since a 1x7 can contain 1 possibility, a 2x6 6, a 3x5 5, a 4x4 4, and everything else is redundant. That gives us a really easy 16. However, this gets harder when x + y is less than 8. 2x5 produces 5C2 solutions, which is 10. 3x4 produces 2 different sets of solutions. One is by running four across the bottom, and then producing a column of 2, and then placing a random other, which gives four placements for the column, and 2 of those have 4 placements for the random, which is 8, and the other two have 5 placements, which is 10. The next set is by running four across the middle, and then placing one on either side. This gives 16, 4 positions on one side, and 4 on the other. Those total out to 44. Then, 2x4 means you have to place four across the bottom, and then it's 4C3 across the top, which is 4. 3x3 gives... I'm going to edit this post later in the day. It is currently 5:19 A.M. my time, and I have a Calculus test at 9. I'm going to have to edit a couple of the numbers, because I didn't account for bending. Basically, I think I have a solution using the boxes to restrict possibilities, but it's still much longer than it should be. |
Author: | pnm [ Fri Nov 04, 2011 12:02 pm ] |
Post subject: | Re: The shape of the cages (structure and names) |
Hi clm, I'm curious: did you write a program to compute these cage possibilities, or did you find them by hand (?!) Patrick |
Author: | clm [ Fri Nov 04, 2011 7:51 pm ] |
Post subject: | Re: The shape of the cages (structure and names) |
pnm wrote: Hi clm, I'm curious: did you write a program to compute these cage possibilities, or did you find them by hand (?!) Patrick Hi, Patrick: I found them by hand (rough procedure), it takes time but it is the only way I know in this moment (I have not enough programming knowledge or experience for this geometric calculation, because symmetries must be carefully detected and supressed, etc.). Since I followed the process of adding a cell in all possible positions of all the previous low order 6-cells cages, assuming that figures grow as fractals, I started obtaining the 7-cells cages and observed that there were not so many (60 different obtained after completing the figure 6.12, 66 after completing the figure 6.17, ..., there are more initially then decrease, I decided to continue to the end) (I would not do it for the 8-cells, perhaps 300, ...!!!). |
Author: | giulio [ Sun Nov 06, 2011 10:13 am ] |
Post subject: | Re: The shape of the cages (structure and names) |
clm, you did a great job! After reading your post, I absolutely had to develop a program to generate the cage shapes! The program confirms all your shapes, including the 108/107 of 7-cell cages. It took a while to ensure that all symmetries were covered. I also had problems with the heap space allocated by Eclipse to Java applications. But it was a satisfaction to match each one of my shapes with yours. Mine [obviously] come in a different order and with different orientations/rotations/mirroring, which made the matching a good mental exercise. While I am writing this post, I have started the program for 8-cell cages. It might fail, but you never know. In any case, I expect that it will take a while. Already the 7-cell cages took a few minutes. It is not a very efficient program, because I wanted to write it as quickly as possible. If it succeeds, I will store a PDF with all the shapes in a place where you can download them from. If it fails, I will have to improve it, perhaps by calculating the shapes in chunks, without changing the logic. In any case, it could be that I have still overlooked a symmetry not detectable with smaller cages. I had forgotten one and realised it only when I calculated the 7-cell shapes. I had 109 shapes instead of 108. The duplicate one "told" me what I had overlooked. I know: I should check the relevant symmetry group (I knew it but have forgotten it, because it was some time ago) and do it properly... The program is still going. I will submit this now, have dinner (here it is 19:12), and let you know later. And, if you would like to know more about the program, or have the source, just let me know. I will upload it to the website that I use for permanent storage and tell you how to get it. But it is not an elegant program , so don't come back to me and complain about it. |
Author: | giulio [ Sun Nov 06, 2011 12:24 pm ] |
Post subject: | Re: The shape of the cages (structure and names) |
Good news! The program, after at least a quarter of an hour processing, calculated the 8-cell shapes. They are 369. As I said in my previous post, I cannot guarantee that they are correct. To be completely sure, an independent verification is necessary. But I am very confident that I haven't missed any valid shape. At worst, I have duplicated a small number of them (although I consider it likely that I didn't). This is because I started the program by making an 8x8 square of cells and then trying every possible choice of 8 cells, saving only the patterns in which the cells were contiguous. In case you are interested, the patterns were 64,678. After shifting all shapes to the top-left corner of the 8x8 square and removing the straight duplicates, 2,725 patterns were left. I have uploaded the shapes to http://good.at.it/calcudokuforum/cages8.txt. Now, concerning 9-cell cages, I suspect that the program will not manage to do it, but if it did, as inefficient as it is, it would probably take hours. Rather than leave it unattended, I will start it tomorrow morning (it is currently 21:24 where I live). |
Author: | clm [ Sun Nov 06, 2011 1:13 pm ] |
Post subject: | Re: The shape of the cages (structure and names) |
giulio wrote: Good news! The program, after at least a quarter of an hour processing, calculated the 8-cell shapes. They are 369. As I said in my previous post, I cannot guarantee that they are correct. To be completely sure, an independent verification is necessary. But I am very confident that I haven't missed any valid shape. At worst, I have duplicated a small number of them (although I consider it likely that I didn't). This is because I started the program by making an 8x8 square of cells and then trying every possible choice of 8 cells, saving only the patterns in which the cells were contiguous. In case you are interested, the patterns were 64,678. After shifting all shapes to the top-left corner of the 8x8 square and removing the straight duplicates, 2,725 patterns were left. I have uploaded the shapes to http://good.at.it/calcudokuforum/cages8.txt. Now, concerning 9-cell cages, I suspect that the program will not manage to do it, but if it did, as inefficient as it is, it would probably take hours. Rather than leave it unattended, I will start it tomorrow morning (it is currently 21:24 where I live). Thank you very much, giulio, for your support, good job. I am really happy with your results, 369 < 535, that was the superior limit obtained with the expression I have developped: F(n) < 17 x n! / (5 x 2 ^ n) I was suspecting that the other expression F(n) <= 4 x 3 ^ (n - 4) could not interpolate well the points of this "discrete function" (it gave 324 as an upper limit) and started failing and "crossing the reality" at some near point. Probably, if you continue with this curiosity, you may find the "exact" algebraic expression, that requires to know how the symmetries are being produced in order to efficiently supress them, or even better, the "exact" rules to work with the "starling's boxes" referred to in my post. New subject: Would it be possible to adapt the program (in the near future) to calculate the different 3-dimensions shapes, for instance, for 6 cubes (I referred to this, Oct 08, in my answer to jomapil and starling)?. Best, clm. |
Page 1 of 2 | All times are UTC + 1 hour [ DST ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |