View unanswered posts | View active topics It is currently Tue Oct 17, 2017 5:51 am



← Back to the Calcudoku puzzle page




Reply to topic  [ 16 posts ]  Go to page Previous  1, 2
 The shape of the cages (structure and names) 
Author Message

Posted on: Sun Nov 06, 2011 2:37 pm




Posts: 54
Joined: Thu Nov 03, 2011 8:52 am
Post 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 7-patters, with 3D, the 6-patterns 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...


Profile

Posted on: Sun Nov 06, 2011 10:19 pm




Posts: 690
Joined: Fri May 13, 2011 6:51 pm
Post 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 7-patters, with 3D, the 6-patterns 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 8-cells 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.


Profile

Posted on: Tue Nov 08, 2011 8:26 am




Posts: 54
Joined: Thu Nov 03, 2011 8:52 am
Post 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 8-cell 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 7-cell cage 108. This is also true for the 369 8-cell cages that you find at http://good.at.it/calcudokuforum/cages8.txt. To be consistent, I have also uploaded the 108 7-cell cages, which you will find at http://good.at.it/calcudokuforum/cages7.txt.

FYI, I don't intend to generate the 10-cell cages... :)


Profile

Posted on: Tue Nov 08, 2011 1:09 pm




Posts: 690
Joined: Fri May 13, 2011 6:51 pm
Post 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 8-cell 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 7-cell cage 108. This is also true for the 369 8-cell cages that you find at http://good.at.it/calcudokuforum/cages8.txt. To be consistent, I have also uploaded the 108 7-cell cages, which you will find at http://good.at.it/calcudokuforum/cages7.txt.

FYI, I don't intend to generate the 10-cell cages... :)


Very interesting result for the 9-cell (adjusts to the prediction).
There are not so many "strange cages" like the 108 (only one in the case of 7-cell, only 5 or 6 in the 8-cell 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 7-cell) is applied to the generation of the 8-cell 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:
4-cell cages: fit in "starling's boxes" 4x1, 3x2 and 2x2
5-cell cages: fit in "starling's boxes" 5x1, 4x2, 3x3 and 3x2
6-cell cages: fit in "starling's boxes" 6x1, 5x2, 4x3, 4x2, 3x3 and 3x2
7-cell 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 4-cell, 6 for 5-cell, 7 for 6-cell, 8 for 7-cell) 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.



Profile

Posted on: Tue Nov 08, 2011 1:37 pm




Posts: 54
Joined: Thu Nov 03, 2011 8:52 am
Post Re: The shape of the cages (structure and names)
It seems to me that with 8-cell cages there must be at least 6 "holed" cages, depending on how you attach the 8th cell to 7-cage 108:
Code:
     |   #   |  #    |        |        |
###  |  ##   |  ##   |  ###   |   ##   |   ##
# #  |  # #  |  # #  |   # #  |  ## #  |   # #
###  |  ###  |  ###  |   ###  |   ###  |  ####


I did apply the "add-on" method to 7-cages and obtained 369 shapes for the 8-cages (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 1-cage. The 8-cage:
Code:
###
# #
###

is beautiful, isn't it?


Profile

Posted on: Tue Nov 08, 2011 4:49 pm




Posts: 690
Joined: Fri May 13, 2011 6:51 pm
Post Re: The shape of the cages (structure and names)
giulio wrote:
It seems to me that with 8-cell cages there must be at least 6 "holed" cages, depending on how you attach the 8th cell to 7-cage 108:
Code:
     |   #   |  #    |        |        |
###  |  ##   |  ##   |  ###   |   ##   |   ##
# #  |  # #  |  # #  |   # #  |  ## #  |   # #
###  |  ###  |  ###  |   ###  |   ###  |  ####


I did apply the "add-on" method to 7-cages and obtained 369 shapes for the 8-cages (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 1-cage. The 8-cage:
Code:
###
# #
###

is beautiful, isn't it?


Yes, it is. Those 6 "strange cages" have 1-cell hole (like the "strange cage" of the 7-cell cages). With 9-cell we start having 2 holes, in a unique 2-cell "cage" like this one
...###
#.....#
####

but to have two holes separate we probably must wait until the 11-cell like in this case
####..
#..#..#
..####

So 369 (363 + 6 "strange") for 8-cell, thank you.


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 16 posts ]  Go to page Previous  1, 2

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

Search for:
Jump to:  
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.