The shape of the cages (structure and names)
Author 
Message 
giulio
Posted on: Sun Nov 06, 2011 2:37 pm
Posts: 54 Joined: Thu Nov 03, 2011 8:52 am

Re: The shape of the cages (structure and names)
I used the brute force approach because I didn't want to [re]learn the symmetries. But I just had a look at some web pages.
At first sight, it seems that it should be possible to adapt the program to 3D. But it would be a problem to display the solutions. I really wouldn't like to look into 3D graphics (which I don't know and have never used). And to show the slices side by side (i.e., six 6x6 squares for a cube of side 6) doesn't really cut it. Another [potential] problem would be the amount of computational effort. If now, with 2D, the computer spends at least 1/4 hour to find the 7patters, with 3D, the 6patterns might be already too hard.
But the major problem would be to filter all the symmetries. The square has seven: 2 rotations by 90°, rotation by 180°, vertical flip, horizontal flip, 2 diagonal flips. Notice that the flips are in fact rotations in a third dimension about an axis on the plane of the square. But you can rotate the cube about axes through the centre of opposite faces (+90°, 90°, and 180° for each one of the three pairs of faces), through the middle of opposide edges (180° for each one of the six pairs of edges), and through opposite vertices (+120° and 120° for each one of the four pairs of vertices). And then there are the flippings...
It's a bit too much...




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

Re: The shape of the cages (structure and names)
giulio wrote: I used the brute force approach because I didn't want to [re]learn the symmetries. But I just had a look at some web pages.
At first sight, it seems that it should be possible to adapt the program to 3D. But it would be a problem to display the solutions. I really wouldn't like to look into 3D graphics (which I don't know and have never used). And to show the slices side by side (i.e., six 6x6 squares for a cube of side 6) doesn't really cut it. Another [potential] problem would be the amount of computational effort. If now, with 2D, the computer spends at least 1/4 hour to find the 7patters, with 3D, the 6patterns might be already too hard.
But the major problem would be to filter all the symmetries. The square has seven: 2 rotations by 90°, rotation by 180°, vertical flip, horizontal flip, 2 diagonal flips. Notice that the flips are in fact rotations in a third dimension about an axis on the plane of the square. But you can rotate the cube about axes through the centre of opposite faces (+90°, 90°, and 180° for each one of the three pairs of faces), through the middle of opposide edges (180° for each one of the six pairs of edges), and through opposite vertices (+120° and 120° for each one of the four pairs of vertices). And then there are the flippings...
It's a bit too much... In fact the 3D is a speculation that goes beyond the "Calcudoku". I see the difficulties, thank you again, for the moment I will try to play with 4 or 5 cubes ... and see what happens. The 8cells cages are not being used actually but, if the Patrick's idea of introducing sometime a 17x17 or a 19x19 advances, we may work with them in the future.




giulio
Posted on: Tue Nov 08, 2011 8:26 am
Posts: 54 Joined: Thu Nov 03, 2011 8:52 am

Re: The shape of the cages (structure and names)
I started my cages program with a cage length of 9, but, after 24 hours, it was still working... To get the result, I modified the program to do what clm did by hand: I started with 8cell cages and added one cell in all possible positions adjacent to the existing cells. In this way, I avoided having to generate all possible distributions of 9 cells in a 9x9 square and then remove the fragmented shapes. After about 47 minutes, the program listed 1285 shapes. I have uploaded the list to http://good.at.it/calcudokuforum/cages9.txt. There will be several cages with holes, like clm's 7cell cage 108. This is also true for the 369 8cell cages that you find at http://good.at.it/calcudokuforum/cages8.txt. To be consistent, I have also uploaded the 108 7cell cages, which you will find at http://good.at.it/calcudokuforum/cages7.txt. FYI, I don't intend to generate the 10cell cages...




clm
Posted on: Tue Nov 08, 2011 1:09 pm
Posts: 713 Joined: Fri May 13, 2011 6:51 pm

Re: The shape of the cages (structure and names)
giulio wrote: I started my cages program with a cage length of 9, but, after 24 hours, it was still working... To get the result, I modified the program to do what clm did by hand: I started with 8cell cages and added one cell in all possible positions adjacent to the existing cells. In this way, I avoided having to generate all possible distributions of 9 cells in a 9x9 square and then remove the fragmented shapes. After about 47 minutes, the program listed 1285 shapes. I have uploaded the list to http://good.at.it/calcudokuforum/cages9.txt. There will be several cages with holes, like clm's 7cell cage 108. This is also true for the 369 8cell cages that you find at http://good.at.it/calcudokuforum/cages8.txt. To be consistent, I have also uploaded the 108 7cell cages, which you will find at http://good.at.it/calcudokuforum/cages7.txt. FYI, I don't intend to generate the 10cell cages... Very interesting result for the 9cell (adjusts to the prediction). There are not so many "strange cages" like the 108 (only one in the case of 7cell, only 5 or 6 in the 8cell shapes I have to count them again). The "strange cages" come generally at the end of the process and go inside the smaller "starling's boxes" as logically expected. Now, I am curious, if the same method (growing from the 7cell) is applied to the generation of the 8cell cages, would that confirm the number of 369 shapes?. And, would you as a calcudoku designer admit those "strange cases"? (the cells are well connected anyway, they are correct fractals). In 3D those "strange 3D cages" would create what we could call "Keops" holes. Finally (I forgot this in the first edition of the post) a comment: 4cell cages: fit in "starling's boxes" 4x1, 3x2 and 2x2 5cell cages: fit in "starling's boxes" 5x1, 4x2, 3x3 and 3x2 6cell cages: fit in "starling's boxes" 6x1, 5x2, 4x3, 4x2, 3x3 and 3x2 7cell cages: fit in "starling's boxes" 7x1, 6x2, 5x3, 5x2, 4x4, 4x3, 4x2 and 3x3. The addition of the sides of the rectangle has a maximum value of n+1 (5 for 4cell, 6 for 5cell, 7 for 6cell, 8 for 7cell) but it can be lower with the only condition that the area >= n. That is, a 9 cell cage would never require a 6x5 rectangle or wider, for instance, because the addition of the the sides of the rectangle must have a maximum value of 10, so it is not necessary to generate all the shapes in a 9x9 matrix, a lot of computer time due to the high number of combinations to be generated.
Last edited by clm on Tue Nov 08, 2011 1:38 pm, edited 1 time in total.




giulio
Posted on: Tue Nov 08, 2011 1:37 pm
Posts: 54 Joined: Thu Nov 03, 2011 8:52 am

Re: The shape of the cages (structure and names)
It seems to me that with 8cell cages there must be at least 6 "holed" cages, depending on how you attach the 8th cell to 7cage 108: Code:  #  #    ###  ##  ##  ###  ##  ## # #  # #  # #  # #  ## #  # # ###  ###  ###  ###  ###  #### I did apply the "addon" method to 7cages and obtained 369 shapes for the 8cages (cages8.txt is the new one, so that the shapes are ordered like in cages7.txt and cages9.txt). But this doesn't prove anything, because the algorithms I have used to remove duplicates after applying the various symmetries have remained the same. I would admit the "strange cases", at the very least because I don't see any reason to exclude them. They are valid cages, even if they force you to fill the "hole" with a 1cage. The 8cage: is beautiful, isn't it?




clm
Posted on: Tue Nov 08, 2011 4:49 pm
Posts: 713 Joined: Fri May 13, 2011 6:51 pm

Re: The shape of the cages (structure and names)
giulio wrote: It seems to me that with 8cell cages there must be at least 6 "holed" cages, depending on how you attach the 8th cell to 7cage 108: Code:  #  #    ###  ##  ##  ###  ##  ## # #  # #  # #  # #  ## #  # # ###  ###  ###  ###  ###  #### I did apply the "addon" method to 7cages and obtained 369 shapes for the 8cages (cages8.txt is the new one, so that the shapes are ordered like in cages7.txt and cages9.txt). But this doesn't prove anything, because the algorithms I have used to remove duplicates after applying the various symmetries have remained the same. I would admit the "strange cases", at the very least because I don't see any reason to exclude them. They are valid cages, even if they force you to fill the "hole" with a 1cage. The 8cage: is beautiful, isn't it? Yes, it is. Those 6 "strange cages" have 1cell hole (like the "strange cage" of the 7cell cages). With 9cell we start having 2 holes, in a unique 2cell "cage" like this one ...### #.....# #### but to have two holes separate we probably must wait until the 11cell like in this case ####.. #..#..# ..#### So 369 (363 + 6 "strange") for 8cell, thank you.






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

