The shape of the cages (structure and names)
Author 
Message 
clm
Posted on: Fri Sep 30, 2011 12:20 am
Posts: 713 Joined: Fri May 13, 2011 6:51 pm

The shape of the cages (structure and names)
The shape of the cages (structure and names). Hi, calcudokers, have a look to this funny game. Here I have represented (in a total of five graphics) the shape of the cages of 2, 3, 4, 5 and 6 cells (numbering them). Symmetries have been supressed; for instance, these three 6cells structures (that would correspond to figure 6.25) are all the same (from the first to the second by a symmetrie with respect to the horizontal axis, from the second to the third rotating 90 degrees to the right), that is:  XX X  X XXXXXXXXX XXX X   X
A cage is valid if every cell is “connected” to another by a segment (not by a point or vertex). By adding a cell in any position of a lower order cage we go to a higher order cage (i.e., if we add a cell to the figure 5.12 in m13 we obtain the figure 6.28, where the cell k3 is the added cell). Then, all the next order figures can be generated by adding a cell in all positions of the previous order figures; later we erase the symmetries. Obviously, for 2 cells there is only 1 cage type. There are 2 different aspects for the cages of 3cells, 5 for the cages of 4cells, 12 for 5cells and I have found (subjected to corrections) 35 for 6cells. The sequence 1, 2, 5, 12, 35, …, looks like increasing geometrically. How many different aspects could be conceived for a 7cells cage? (I have not calculated them yet) (this size is not very frequent, but it appears form time to time like, recently, in the tuesday Sep 27, 10x10, Puzzle id: 350207, cage “25+”). Finally, could we assign some names to those cages?. What names to assign them? (certainly the name is subjective since using any simmetrie the apparent “image” of the cage changes). What about “5inline” like 5.1, “Lshape” like 6.2, “long Lshape”, “squared box” like 4.5, “rhomboid” boxes like 6.18 and 6.21, “rectangle”, “Sshape”, “stairs”, “podium” like 4.3 and 6.15, etc.?.




jomapil
Posted on: Fri Oct 07, 2011 9:20 am
Posts: 246 Location: Lisbon, Portugal Joined: Sun Sep 18, 2011 5:40 pm

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)+(n1). Will it be, ever, u(n+1)>2 x u(n)+(n1) 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.
_________________Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.




starling
Posted on: Fri Oct 07, 2011 12:22 pm
Posts: 175 Joined: Fri May 13, 2011 2:11 am

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.




clm
Posted on: Sat Oct 08, 2011 10:13 am
Posts: 713 Joined: Fri May 13, 2011 6:51 pm

Re: The shape of the cages (structure and names)
jomapil wrote: ...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)+(n1). Will it be, ever, u(n+1)>2 x u(n)+(n1) 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 am sure that the mathematics (able to calculate the configurations of the Rubik’s cube, the total number of different sudokus, etc., following the Euler’s problems, …) will find the formula and derive from it the “exact” number of configurations for each category. Meanwhile, your idea, “interpolating” the actual known results, looks very interesting, because the “memory” of the previous forms is fundamental. This, as you suggest, it is more a mathematical problem, going beyond the calcudoku, because we could imagine cages of, i.e., 25 cells, too big for a “calcudoku” puzzle. As we have seen, for 3cells, we have only two configurations, but if we now think in a 3 dimentions space we would have 5 configurations of “cubes” (supressing the symmetries and regardless of the “gravity”), 2 in the floor and 3 more in the third dimension (another mathematical problem, configurations of cubes are used in some buildings in Architecture…). I am not thinking for the moment in a “three dimensional calcudoku” (125 cubes for a 5x5x5) but perhaps someone will play that in the future…. starling wrote: …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….
It is curious that the number of cells that can de added encircling a lower category depends much on the shape of the cage you depart from. The procedure I have followed is very simple: since these “fractals” grow continuously (the lower categories are obviously “inside” the higher categories or, inversely, by “cutting” cells  correctly, that is, leaving the rest “connected” by sides and not by points  we arrive to a lower category), we produce the 5cells, i.e., from all the configurations of four cells, adding (clockwise) an addtional cell in each available position and supressing later the symmetries. We may observe that figure 5.1 has initially 12 possible positions for an additional cell (graphic), while figure 5.11 has only 8. This number, then, varies much (in the case of figures 6.1 and 6.32, from 14 to 9, but think in 100 cells in line, initially you would have 202 possible positions while a square of 10x10 had only 40, so it depends on the compactness of the original cage); in the case of figure 5.1 we have 12 free “faces” (because from a total of 20 for the five indepenent cells we loose 8 in the “glueing”). Considering this, the maximum number of faces for any 6x6 is 14 (when 6 in line) and as we have 35 figures, the upper limit for 7cells would be 14x35 = 490, a little less than your 560. But I have counted one by one the free faces of all those 35 figures and I have found a total (unless mistakes) of 387. Your initial idea of fitting the solutions into boxes is very interesting and we could apply that point of view to the already known shapes of the 6cells cages.




clm
Posted on: Fri Nov 04, 2011 1:48 am
Posts: 713 Joined: Fri May 13, 2011 6:51 pm

Re: The shape of the cages (structure and names)
The 107 aspects of the 7cells cages Apparently there are 107 different aspects of the 7cells cages (unless mistakes, corrections welcome). This number has resulted much lower than the initially thought. Here I have represented (in a total of four graphics) those figures (numbering them) (symmetries have been supressed). A cage is valid if every cell is “connected” to another by a segment (not by a point or vertex). I have followed the idea of adding a cell in all positions of the lower order cages (in this case the 35 different 6x6 cages) and that explains the sequence shown. The figure inserted between 7.102 and 7.103 could be discussed but I have preferred to supress it since it looks more like an 8cells cage when bolding lines (apart of the fact that a single digit must necessarily be “inside” restricting the freedom of this cell to be part of a bigger cage). The 107 aspects can be drawn inside the Starling’s boxes (rectangles) (probably the Starling’s idea is the only way for the mathematicians to arrive to an exact calculation of the aspects, but it is difficult to define the process and to obtain that final formula). The 8 types of Starling’s boxes for the 7x7’s cages: Type 7x1 (total of figures 01): 7.1 Type 6x2 (total of figures 05): 7.2, 7.3, 7.4, 7.5 and 7.24 Type 5x3 (total of figures 25): 7.6, 7.11, 7.12, 7.13, 7.14, 7.15, 7.16, 7.19, 7.20, 7.21, 7.22, 7.23, 7.25, 7.26, 7.30, 7.31, 7.32, 7.33, 7.34, 7.68, 7.69, 7.70, 7.71, 7.90 and 7.96 Type 5x2 (total of figures 11): 7.7, 7.8, 7.9, 7.10, 7.17, 7.18, 7.27, 7.28, 7.29, 7.67 and 7.86 Type 4x4 (total of figures 18): 7.35, 7.40, 7.41, 7.42, 7.43, 7.58, 7.60, 7.64, 7.65, 7.72, 7.76, 7.77, 7.78, 7.82, 7.83, 7.91, 7.100 and 7.107 Type 4x3 (total of figures 39): 7.36, 7.37, 7.38, 7.39, 7.44, 7.47, 7.48, 7.49, 7.50, 7.51, 7.52, 7.53, 7.54, 7.55, 7.56, 7.57, 7.59, 7.61, 7.62, 7.63, 7.66, 7.73, 7.74, 7.75, 7.79, 7.80, 7.81, 7.84, 7.85, 7.87, 7.88, 7.89, 7.92, 7.93, 7.94, 7.95, 7.97, 7.98 and 7.99 Type 4x2 (total of figures 02): 7.45 and 7.46 Type 3x3 (total of figures 06): 7.101, 7.102, 7.103, 7.104, 7.105 and 7.106 I have found an expression that “adjusts” quite well the number of aspects giving the “upper limit”: F(n) < 17 x n! / (5 x 2 ^ n), where F(n) represents the known number of figures for a cage with n cells (n! is the n factorial). Let’s see: F(1) = 1 < 1,7 F(2) = 1 < 1,7 F(3) = 2 < 2,55 F(4) = 5 < 5,1 F(5) =12 < 12,75 F(6) = 35 < 38,25 F(7) = 107 (108) < 133,875 F(8) = ??? < 535,5 F(9) = ??? < 2409,75 F(10)= ??? < 12048,75. The number of possible configurations for the 8cells cages, 535, is much lower than 1728 (= 108 x 16) that we know is an upper limit considering all 107 (108) figures of the 7cells cages and the maximum number of “faces”, 16, to add a new cell. However, my feeling is that the real value for F(8) is even much lower than 535. I have adjusted the formula to this other one (that fails for 1, 2, 3 and 4cells cages but adjusts better the big cages): F(n) <= 4 x 3 ^ (n  4). Let’s see: F(1) = 1 <= 0,1481 (fails) F(2) = 1<= 0,4444 (fails) F(3) = 2 <= 1,3333 (fails) F(4) = 5 <= 4 (fails) F(5) = 12 <= 12 F(6) = 35 <= 36 F(7) = 107 (108) <= 108 F(8) = ??? <= 324 F(9) = ??? <= 972 F(10) = ??? <= 2916. This gives 324 as as upper limit for the 8cells cages. The expression F(n) < 4 x n! / (2 ^ n) (this is the original formula I deduced observing the way of creating the higher order cages from the lower order) works very well but perhaps “opens” much the upper limits when n is big: F(1) = 1 < 2 F(2) = 1 < 2 F(3) = 2 < 3 F(4) = 5 < 6 F(5) = 12 < 15 F(6) = 35 < 45 F(7) = 107 (108) < 157,5 F(8) = ??? < 630 F(9) = ??? < 2835 F(10) = ??? < 14175.




pnm
Posted on: Fri Nov 04, 2011 12:02 pm
Posts: 2313 Joined: Thu May 12, 2011 11:58 pm

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




clm
Posted on: Fri Nov 04, 2011 7:51 pm
Posts: 713 Joined: Fri May 13, 2011 6:51 pm

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 6cells cages, assuming that figures grow as fractals, I started obtaining the 7cells 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 8cells, perhaps 300, ...!!!).




giulio
Posted on: Sun Nov 06, 2011 10:13 am
Posts: 54 Joined: Thu Nov 03, 2011 8:52 am

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 7cell 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 8cell cages. It might fail, but you never know. In any case, I expect that it will take a while. Already the 7cell 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 7cell 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.




giulio
Posted on: Sun Nov 06, 2011 12:24 pm
Posts: 54 Joined: Thu Nov 03, 2011 8:52 am

Re: The shape of the cages (structure and names)
Good news! The program, after at least a quarter of an hour processing, calculated the 8cell 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 topleft 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 9cell 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).




clm
Posted on: Sun Nov 06, 2011 1:13 pm
Posts: 713 Joined: Fri May 13, 2011 6:51 pm

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 8cell 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 topleft 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 9cell 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 3dimensions shapes, for instance, for 6 cubes (I referred to this, Oct 08, in my answer to jomapil and starling)?. Best, clm.






You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum

