Calcudoku puzzle forumhttp://www.calcudoku.org/forum/ The shape of the cages (structure and names)http://www.calcudoku.org/forum/viewtopic.php?f=3&t=73 Page 1 of 2

 Author: clm  [ Fri Sep 30, 2011 12:20 am ] Post subject: 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 6-cells 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-------XXX---------XXX----------XXX-------X----------XX---------- ----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 3-cells, 5 for the cages of 4-cells, 12 for 5-cells and I have found (subjected to corrections) 35 for 6-cells. The sequence 1, 2, 5, 12, 35, …, looks like increasing geometrically. How many different aspects could be conceived for a 7-cells 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 “5-in-line” like 5.1, “L-shape” like 6.2, “long L-shape”, “squared box” like 4.5, “rhomboid” boxes like 6.18 and 6.21, “rectangle”, “S-shape”, “stairs”, “podium” like 4.3 and 6.15, etc.?.

 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=312=(5+5)+2 n=435=/(12+12)+5 n=5and 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 = 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: clm  [ Sat Oct 08, 2011 10:13 am ] Post subject: 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=312=(5+5)+2 n=435=/(12+12)+5 n=5and 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 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 3-cells, 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 toohigh, 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 = to 7. Thus, with7 cells, it can be in a box 1x7, 2x6, 3x5, 4x4, etc. These all calculate easily, since a1x7 can contain 1 possibility, a 2x6 6, a 3x5 5, a 4x4 4, and everything else isredundant. 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 5-cells, 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 7-cells 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 interestingand we could apply that point of view to the already known shapes of the 6-cells cages.

 Author: clm  [ Fri Nov 04, 2011 1:48 am ] Post subject: Re: The shape of the cages (structure and names) The 107 aspects of the 7-cells cages Apparently there are 107 different aspects of the 7-cells 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 8-cells 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.1Type 6x2 (total of figures 05): 7.2, 7.3, 7.4, 7.5 and 7.24Type 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.96Type 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.86Type 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.107Type 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.99Type 4x2 (total of figures 02): 7.45 and 7.46Type 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,7F(2) = 1 < 1,7F(3) = 2 < 2,55F(4) = 5 < 5,1F(5) =12 < 12,75F(6) = 35 < 38,25F(7) = 107 (108) < 133,875F(8) = ??? < 535,5F(9) = ??? < 2409,75F(10)= ??? < 12048,75. The number of possible configurations for the 8-cells cages, 535, is much lower than 1728 (= 108 x 16) that we know is an upper limit considering all 107 (108) figures of the 7-cells 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 4-cells 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 <= 12F(6) = 35 <= 36F(7) = 107 (108) <= 108F(8) = ??? <= 324F(9) = ??? <= 972F(10) = ??? <= 2916. This gives 324 as as upper limit for the 8-cells 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 < 2F(2) = 1 < 2F(3) = 2 < 3F(4) = 5 < 6F(5) = 12 < 15F(6) = 35 < 45F(7) = 107 (108) < 157,5F(8) = ??? < 630F(9) = ??? < 2835F(10) = ??? < 14175.

 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 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 Grouphttp://www.phpbb.com/