We collect Mini Bedlam Cube
I wrote the program solving the “pentamino” puzzle as one of my first programs. It was a long time ago, the program somehow worked, I did not have time to find all the options ... In general, I wrote and forgot.
The other day, putting things in order on the table, I decided that it was time to remove the puzzle “Mini Bedlam Cube”:
')
And before that it would be nice to collect it. The puzzle consists of 13 figures - 12 are made up of 5 cubes, one of four; six figures are symmetrical, three of them are flat. Figures need to be placed in a 4x4x4 box. I must say that from time to time I remembered these dice, I tried to cope with them, but nothing happened. Therefore, an idea arose - to write a program that solves a puzzle, and to spend as little effort as possible, and then to solve the old question: what is more profitable - to sort out shapes or cells, and in what order.
Since the number of cells in the box quite accidentally turned out to be no more than the number of bits in one of the representations of integers, it was this representation that was chosen as the main one: both the current state of the field and each position of each figure is stored as an unsigned __int64 bitmask (for C # - ulong). The number of orientations of each figure is no more than 24, the number of positions for this orientation is no more than 27. Total, maybe no more than 648 positions of each figure we can easily afford to keep them in memory. It is only necessary to get these provisions somehow.
It would be possible to explicitly specify 24 orientations of the cube, indicating the order of the axes and their direction, but this is a long time. It is easier to do this: choose two generators in the cube rotation group (one, unfortunately, cannot be found), and apply them to one state until the results stabilize. I chose the transformations (x, y, z) -> (y, z, x) and (x, y, z) -> (-x, z, y).
Such code turned out:
The Turn () function performs one of two turns. Constants XHIGH, XLOW, etc. correspond to the faces of the cube, and allow you to determine whether you can move the shape in one direction or another. Initializing the entire set of shapes now looks completely simple:
Here I consider that the cross can occupy only two essentially different positions. This ensures that all solutions found in the future will be different.
We will look for solutions in depth. At each step, we can either choose some cell and sort through all the free shapes with which it can be closed, or vice versa - choose some shape and place it on the field in all possible ways. In addition, we can check whether there is a cell that can no longer be closed or a figure that cannot be placed at all - in both cases the analysis of the branch can be stopped. The complexity of the algorithm depends on which strategy we choose and whether we will check the situations for impossibility.
In the simplest version - iteration over the figures in a fixed order - the search for solutions is written in 20 lines:
The positions of the figures are saved in the FState array, and the Print () function can easily print the solution found.
Total - the program in 110 lines turned out.
The program found the first solution in a couple of seconds, but then thought about it. The “19186 Solutions” is written on the box, and I, of course, wanted to find them all (and at the same time to check whether the authors considered it right). Printing statistics showed the following:
The first 500 million calls to Solve ran for 295 seconds, and only 44 solutions were found. This gives 1.7 million calls per second, and 6.7 seconds for one solution. Approximate working time for finding all solutions is 36 hours.
Too much.
The first optimization that comes to mind is to check whether there is an isolated empty cell on the field, and if there is, not to consider this situation further. The check turned out to be quite simple:
After its inclusion in Solve, the result was an order of magnitude better: 1.9 million calls per second and about 1.8 solutions per second! You can meet at 3 o'clock. It was also possible to try to look for isolated areas of 2 and 3 cells, but here it is difficult to cope with the morphology, we need a full three-dimensional fill.
The next attempt is to search for a cell that is closed by the smallest possible number of methods, and a search through these methods. The Solve function began to work about 20 times slower, but the overall solution search speed remained
former - 1.8 solutions per second.
In order not to waste time searching for the optimal empty cell, I decided to sort through them in order. Obviously, if the cells 0..N-1 are already filled, and the cell N is empty, then this cell can be filled only with those positions of the figures to which the cell N belongs, and at the same time is the minimum number of all cells of the figure. So, sorting out the figures according to the number of the minimum cell, you can significantly reduce the search.
The code is as follows (only changed functions are shown):
Surprisingly, this option turned out to be more than 50 times faster than the previous one - it finds 95 solutions per second, and a complete bust of the entire puzzle occurs in 203 seconds. The cause has not yet been understood. Any attempt to change the iteration order results in an increase in the number of calls to Solve (). But on the other hand, time can be reduced by half if we look for a free cell, starting with the one found last time:
The total running time is 102 seconds, approximately 1250 times shorter than in the first considered variant. At the same time, the program was lengthened slightly: about 130 lines for everything.
The first question is technical. There is a stream of 64-bit numbers in the amount of from 10 to 10,000 pieces. In each number no more than 5 raised bits. It is required to determine which bit is raised in the greatest number of these numbers. How to do it most effectively?
The second question is rather philosophical. Why is the most effective filling of cells exactly in rows, then in layers? I tried to fill the vertices, then the edges ... The result was several orders of magnitude worse than in the case of the lexicographic order. What could be wrong here?
The other day, putting things in order on the table, I decided that it was time to remove the puzzle “Mini Bedlam Cube”:
')
And before that it would be nice to collect it. The puzzle consists of 13 figures - 12 are made up of 5 cubes, one of four; six figures are symmetrical, three of them are flat. Figures need to be placed in a 4x4x4 box. I must say that from time to time I remembered these dice, I tried to cope with them, but nothing happened. Therefore, an idea arose - to write a program that solves a puzzle, and to spend as little effort as possible, and then to solve the old question: what is more profitable - to sort out shapes or cells, and in what order.
Data presentation and simplest search
Since the number of cells in the box quite accidentally turned out to be no more than the number of bits in one of the representations of integers, it was this representation that was chosen as the main one: both the current state of the field and each position of each figure is stored as an unsigned __int64 bitmask (for C # - ulong). The number of orientations of each figure is no more than 24, the number of positions for this orientation is no more than 27. Total, maybe no more than 648 positions of each figure we can easily afford to keep them in memory. It is only necessary to get these provisions somehow.
It would be possible to explicitly specify 24 orientations of the cube, indicating the order of the axes and their direction, but this is a long time. It is easier to do this: choose two generators in the cube rotation group (one, unfortunately, cannot be found), and apply them to one state until the results stabilize. I chose the transformations (x, y, z) -> (y, z, x) and (x, y, z) -> (-x, z, y).
Such code turned out:
typedef unsigned __int64 ulong; const ulong XLOW=0x1111111111111111LL; const ulong YLOW=0xF000F000F000FLL; const ulong ZLOW=0xFFFFLL; const ulong XHIGH=0x8888888888888888LL; const ulong YHIGH=0xF000F000F000F000LL; const ulong ZHIGH=0xFFFF000000000000LL; struct Fig{ int NF; ulong *Arr; Fig(){ Arr=0;} void Init(ulong fig0); void Init(int nf,ulong *arr); ~Fig(){ delete Arr; } }; ulong Turn(ulong v,int rt){ ulong res=0; for(int a=0;a<64;a++){ int b=rt==0 ? (a>>2)|((a&3)<<4) : (~a&3)|((a>>2)&12)|((a<<2)&48); if((v>>a)&1) res|=1LL<<b; } if(rt) while((res&XLOW)==0) res>>=1; return res; } ulong arr0[648]; void Fig::Init(ulong fig0){ int p=0,q=1; arr0[0]=fig0; while(p<q){ ulong a=arr0[p++]; for(int u=0;u<2;u++){ ulong b=Turn(a,u); int i; for(i=0;i<q;i++) if(arr0[i]==b) break; if(i==q) arr0[q++]=b; } } for(p=0;p<q;p++) if((arr0[p]&XHIGH)==0) arr0[q++]=arr0[p]<<1; for(p=0;p<q;p++) if((arr0[p]&YHIGH)==0) arr0[q++]=arr0[p]<<4; for(p=0;p<q;p++) if((arr0[p]&ZHIGH)==0) arr0[q++]=arr0[p]<<16; Init(q,arr0); } void Fig::Init(int q,ulong *arr){ NF=q; Arr=new ulong[q]; for(int p=0;p<q;p++) Arr[p]=arr[p]; } The Turn () function performs one of two turns. Constants XHIGH, XLOW, etc. correspond to the faces of the cube, and allow you to determine whether you can move the shape in one direction or another. Initializing the entire set of shapes now looks completely simple:
ulong Cross[2]={0x4E40000000000000LL,0x4E4000000000LL}; const int NFig=13; ulong Figs0[NFig]={0x4E4,0x136,0x263,0x10027,0x20027,0x20063,0x10063,0x30062,0x10047, 0x100017,0x10017,0x20072,0x10031}; Fig Figs[NFig]; int FState[NFig]; void InitFigs(){ Figs[0].Init(2,Cross); for(int i=1;i<NFig;i++){ Figs[i].Init(Figs0[i]); } } Here I consider that the cross can occupy only two essentially different positions. This ensures that all solutions found in the future will be different.
We will look for solutions in depth. At each step, we can either choose some cell and sort through all the free shapes with which it can be closed, or vice versa - choose some shape and place it on the field in all possible ways. In addition, we can check whether there is a cell that can no longer be closed or a figure that cannot be placed at all - in both cases the analysis of the branch can be stopped. The complexity of the algorithm depends on which strategy we choose and whether we will check the situations for impossibility.
In the simplest version - iteration over the figures in a fixed order - the search for solutions is written in 20 lines:
void Solve(int n,ulong x){ if(n==NFig){ NSolve++; Print(); return; } Fig &F=Figs[n]; for(int i=0;i<F.NF;i++){ ulong s=F.Arr[i]; if((s&x)==0){ FState[n]=i; Solve(n+1,x|s); FState[n]=-1; } } NBack++; } The positions of the figures are saved in the FState array, and the Print () function can easily print the solution found.
Results and optimization
Total - the program in 110 lines turned out.
The program found the first solution in a couple of seconds, but then thought about it. The “19186 Solutions” is written on the box, and I, of course, wanted to find them all (and at the same time to check whether the authors considered it right). Printing statistics showed the following:
The first 500 million calls to Solve ran for 295 seconds, and only 44 solutions were found. This gives 1.7 million calls per second, and 6.7 seconds for one solution. Approximate working time for finding all solutions is 36 hours.
Too much.
The first optimization that comes to mind is to check whether there is an isolated empty cell on the field, and if there is, not to consider this situation further. The check turned out to be quite simple:
bool HaveIsolPoint(ulong x){ ulong y=((x>>1)|XHIGH)&((x<<1)|XLOW)& ((x>>4)|YHIGH)&((x<<4)|YLOW)& ((x>>16)|ZHIGH)&((x<<16)|ZLOW); return (~x&y)!=0; } After its inclusion in Solve, the result was an order of magnitude better: 1.9 million calls per second and about 1.8 solutions per second! You can meet at 3 o'clock. It was also possible to try to look for isolated areas of 2 and 3 cells, but here it is difficult to cope with the morphology, we need a full three-dimensional fill.
The next attempt is to search for a cell that is closed by the smallest possible number of methods, and a search through these methods. The Solve function began to work about 20 times slower, but the overall solution search speed remained
former - 1.8 solutions per second.
In order not to waste time searching for the optimal empty cell, I decided to sort through them in order. Obviously, if the cells 0..N-1 are already filled, and the cell N is empty, then this cell can be filled only with those positions of the figures to which the cell N belongs, and at the same time is the minimum number of all cells of the figure. So, sorting out the figures according to the number of the minimum cell, you can significantly reduce the search.
The code is as follows (only changed functions are shown):
struct Fig{ int NF; ulong *Arr; int Ind[65]; Fig(){ Arr=0;} void Init(ulong fig0); void Init(int nf,ulong *arr); ~Fig(){ delete Arr; } }; extern "C" int i64cmp(const void *a,const void *b){ ulong A=*(const ulong*)a,B=*(const ulong*)b; return A<B ? -1 : A==B ? 0 : 1; } void Fig::Init(int q,ulong *arr){ NF=q; Arr=new ulong[q]; for(int p=0;p<q;p++) Arr[p]=CVT(arr[p]); qsort(Arr,q,sizeof(ulong),i64cmp); int j=0; for(int p=0;p<q;p++){ while(Arr[p]&(-1LL<<j)) Ind[j++]=p; } while(j<=64) Ind[j++]=q; } void Solve(ulong x){ int mb=63; while(mb>=0){ if((x&1)==0) break; x>>=1; mb--; } if(mb<0){ NSolve++; Print(); return; } for(int f=0;f<NFig;f++) if(FState[f]<0){ Fig &F=Figs[f]; int r1=F.Ind[mb],r2=F.Ind[mb+1]; for(int u=r1;u<r2;u++){ ulong s=F.Arr[u]; if((x&s)==0){ FState[f]=u; Solve(x|s,mb,z); } } FState[f]=-1; } NBack++; } Surprisingly, this option turned out to be more than 50 times faster than the previous one - it finds 95 solutions per second, and a complete bust of the entire puzzle occurs in 203 seconds. The cause has not yet been understood. Any attempt to change the iteration order results in an increase in the number of calls to Solve (). But on the other hand, time can be reduced by half if we look for a free cell, starting with the one found last time:
void Solve(ulong x,int mb,ulong z){ while(z!=0){ if((x&z)==0) break; z>>=1; mb--; } if(mb<0){ NSolve++; Print(); return; } for(int f=0;f<NFig;f++) if(FState[f]<0){ Fig &F=Figs[f]; int r1=F.Ind[mb],r2=F.Ind[mb+1]; ulong *aa=F.Arr+r1; for(int u=r1;u<r2;u++){ ulong s=*aa++; if((x&s)==0){ FState[f]=u; Solve(x|s,mb,z); } } FState[f]=-1; } NBack++; } The total running time is 102 seconds, approximately 1250 times shorter than in the first considered variant. At the same time, the program was lengthened slightly: about 130 lines for everything.
Open questions
The first question is technical. There is a stream of 64-bit numbers in the amount of from 10 to 10,000 pieces. In each number no more than 5 raised bits. It is required to determine which bit is raised in the greatest number of these numbers. How to do it most effectively?
The second question is rather philosophical. Why is the most effective filling of cells exactly in rows, then in layers? I tried to fill the vertices, then the edges ... The result was several orders of magnitude worse than in the case of the lexicographic order. What could be wrong here?
Source: https://habr.com/ru/post/114457/
All Articles