Программу, решающую головоломку «пентамино» я написал в качестве одной из первых своих программ. Дело было давно, программа как-то работала, всех вариантов найти не успела… В общем, написал и забыл.
На днях, наводя порядок на столе, решил, что пора бы убрать валяющуюся без дела головоломку «Mini Bedlam Cube»:
А перед этим ее неплохо бы собрать. Головоломка состоит из 13 фигур — 12 составлены из 5 кубиков, одна из четырех; шесть фигур симметричные, три из них — плоские. Фигуры нужно уложить в коробку 4x4x4. Надо сказать, что периодически я вспоминал об этих кубиках, пытался с ними справиться, но так ничего и не вышло. Поэтому возникла идея — написать программу, решающую головоломку, причем затратить как можно меньше усилий, а потом решить старый вопрос: что выгоднее — перебирать фигуры или клетки, и в каком порядке.
Поскольку число клеток в коробке совершенно случайно оказалось не больше, чем число бит в одном из представлений целых чисел, именно это представление было выбрано в качестве основного: как текущее состояние поля, так и каждое положение каждой фигуры хранится в виде битовой маски unsigned __int64 (для C# — ulong). Количество ориентаций каждой фигуры — не более 24, количество положений при данной ориентации — не более 27. Итого, возможно не более 648 положений каждой фигуры — мы легко можем позволить себе хранить их в памяти. Надо только как-то эти положения получить.
Можно было бы явно задать 24 ориентации куба, указав порядок осей и их направление, но это долго. Проще сделать так: выбрать в группе поворотов куба две образующих (одной, к сожалению, найти нельзя), и применять их к одному состоянию, пока результаты не стабилизируются. Я выбрал преобразования (x,y,z) -> (y,z,x) и (x,y,z) -> (-x,z,y).
Получился такой код:
Функция Turn() выполняет один из двух поворотов. Константы XHIGH, XLOW и т.п. соответствуют граням куба, и позволяют определить, можно ли двигать фигуру в ту или иную сторону. Инициализация всего набора фигур теперь выглядит совсем просто:
Здесь я учитываю, что крест может занимать только два существенно различных положения. Это гарантирует, что все найденные в дальнейшем решения будут различны.
Искать решения будем в глубину. На каждом шаге мы можем либо выбрать какую-то клетку и перебрать все свободные фигуры, которыми ее можно закрыть, либо наоборот — выбрать какую-нибудь фигуру и разместить ее на поле всеми возможными способами. Кроме того, мы можем проверить — есть ли клетка, которую уже нельзя закрыть или фигура, которую никак нельзя поставить — в обоих случаях анализ ветки можно прекратить. От того, какую стратегию мы выберем, и будем ли проверять ситуации на невозможность, зависит сложность алгоритма.
В простейшем варианте — перебор по фигурам в фиксированном порядке — поиск решений пишется в 20 строк:
Положения фигур сохраняются в массиве FState, и функция Print() легко может напечатать найденное решение.
Итого — получилась программа в 110 строк.
Первое решение программа нашла за пару секунд, но потом задумалась. На коробке написано «19186 Solutions», и мне, конечно, захотелось найти их все (а заодно и проверить, правильно ли посчитали авторы). Печать статистики показала следующее:
Первые 500 миллионов вызовов Solve выполнялись 295 секунд, и найдено было только 44 решения. Это дает 1.7 млн вызовов в секунду, и 6.7 секунд на одно решение. Ориентировочное время работы для поиска всех решений — 36 часов.
Многовато.
Первая оптимизация, которая приходит в голову — проверить, нет ли на поле изолированной пустой клетки, и если есть — не рассматривать это положение дальше. Проверка оказалась совсем простой:
После ее включения в Solve, результат оказался на порядок лучше: 1.9 млн вызовов в секунду и примерно 1.8 решения в секунду! Можно уложиться в 3 часа. Можно было также попробовать поискать изолированные области из 2 и 3 клеток, но тут морфологией справиться трудно, нужна полноценная трехмерная заливка.
Следующая попытка — поиск клетки, которая закрывается наименьшим возможным числом способов, и перебор этих способов. Функция Solve стала работать примерно в 20 раз медленнее, но общая скорость поиска решения осталась
прежней — 1.8 решения в секунду.
Чтобы не тратить время на поиск оптимальной пустой клетки, я решил перебирать их по порядку. Очевидно, что если клетки 0..N-1 уже заполнены, а клетка N — пустая, то эту клетку можно заполнить только теми положениями фигур, которым клетка N принадлежит, и при этом является минимальной по номеру из всех клеток фигуры. Так что, отсортировав фигуры по номеру минимальной клетки, можно заметно сократить перебор.
Код получается таким (приведены только измененные функции):
Удивительно, но этот вариант оказался быстрее предыдущего в 50 с лишним раз — он находит 95 решений в секунду, и полный перебор всей головоломки происходит за 203 секунды. Причину пока понять не удалось. Любая попытка изменить порядок перебора приводит к увеличению числа вызовов Solve(). Но зато время можно уменьшить еще вдвое, если искать свободную клетку, начиная с найденной в прошлый раз:
Полное время работы — 102 секунды, примерно в 1250 раз меньше, чем в первом рассмотренном варианте. При этом программа удлинилась ненамного: около 130 строк на всё.
Первый вопрос — технический. Есть поток 64-битных чисел в количестве от 10 до 10000 штук. В каждом числе не более 5 поднятых битов. Требуется определить, какой бит поднят в наибольшем количестве этих чисел. Как это сделать наиболее эффективно?
Второй вопрос — скорее, философский. Почему наиболее эффективным оказывается заполнение клеток именно по строкам, потом по слоям? Я пробовал заполнять вершины, потом ребра… Результат был на несколько порядков хуже, чем в случае лексикографического порядка. В чем тут может быть дело?
На днях, наводя порядок на столе, решил, что пора бы убрать валяющуюся без дела головоломку «Mini Bedlam Cube»:
А перед этим ее неплохо бы собрать. Головоломка состоит из 13 фигур — 12 составлены из 5 кубиков, одна из четырех; шесть фигур симметричные, три из них — плоские. Фигуры нужно уложить в коробку 4x4x4. Надо сказать, что периодически я вспоминал об этих кубиках, пытался с ними справиться, но так ничего и не вышло. Поэтому возникла идея — написать программу, решающую головоломку, причем затратить как можно меньше усилий, а потом решить старый вопрос: что выгоднее — перебирать фигуры или клетки, и в каком порядке.
Представление данных и простейший поиск
Поскольку число клеток в коробке совершенно случайно оказалось не больше, чем число бит в одном из представлений целых чисел, именно это представление было выбрано в качестве основного: как текущее состояние поля, так и каждое положение каждой фигуры хранится в виде битовой маски unsigned __int64 (для C# — ulong). Количество ориентаций каждой фигуры — не более 24, количество положений при данной ориентации — не более 27. Итого, возможно не более 648 положений каждой фигуры — мы легко можем позволить себе хранить их в памяти. Надо только как-то эти положения получить.
Можно было бы явно задать 24 ориентации куба, указав порядок осей и их направление, но это долго. Проще сделать так: выбрать в группе поворотов куба две образующих (одной, к сожалению, найти нельзя), и применять их к одному состоянию, пока результаты не стабилизируются. Я выбрал преобразования (x,y,z) -> (y,z,x) и (x,y,z) -> (-x,z,y).
Получился такой код:
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];
}
Функция Turn() выполняет один из двух поворотов. Константы XHIGH, XLOW и т.п. соответствуют граням куба, и позволяют определить, можно ли двигать фигуру в ту или иную сторону. Инициализация всего набора фигур теперь выглядит совсем просто:
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]);
}
}
Здесь я учитываю, что крест может занимать только два существенно различных положения. Это гарантирует, что все найденные в дальнейшем решения будут различны.
Искать решения будем в глубину. На каждом шаге мы можем либо выбрать какую-то клетку и перебрать все свободные фигуры, которыми ее можно закрыть, либо наоборот — выбрать какую-нибудь фигуру и разместить ее на поле всеми возможными способами. Кроме того, мы можем проверить — есть ли клетка, которую уже нельзя закрыть или фигура, которую никак нельзя поставить — в обоих случаях анализ ветки можно прекратить. От того, какую стратегию мы выберем, и будем ли проверять ситуации на невозможность, зависит сложность алгоритма.
В простейшем варианте — перебор по фигурам в фиксированном порядке — поиск решений пишется в 20 строк:
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++;
}
Положения фигур сохраняются в массиве FState, и функция Print() легко может напечатать найденное решение.
Результаты и оптимизация
Итого — получилась программа в 110 строк.
Первое решение программа нашла за пару секунд, но потом задумалась. На коробке написано «19186 Solutions», и мне, конечно, захотелось найти их все (а заодно и проверить, правильно ли посчитали авторы). Печать статистики показала следующее:
Первые 500 миллионов вызовов Solve выполнялись 295 секунд, и найдено было только 44 решения. Это дает 1.7 млн вызовов в секунду, и 6.7 секунд на одно решение. Ориентировочное время работы для поиска всех решений — 36 часов.
Многовато.
Первая оптимизация, которая приходит в голову — проверить, нет ли на поле изолированной пустой клетки, и если есть — не рассматривать это положение дальше. Проверка оказалась совсем простой:
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;
}
После ее включения в Solve, результат оказался на порядок лучше: 1.9 млн вызовов в секунду и примерно 1.8 решения в секунду! Можно уложиться в 3 часа. Можно было также попробовать поискать изолированные области из 2 и 3 клеток, но тут морфологией справиться трудно, нужна полноценная трехмерная заливка.
Следующая попытка — поиск клетки, которая закрывается наименьшим возможным числом способов, и перебор этих способов. Функция Solve стала работать примерно в 20 раз медленнее, но общая скорость поиска решения осталась
прежней — 1.8 решения в секунду.
Чтобы не тратить время на поиск оптимальной пустой клетки, я решил перебирать их по порядку. Очевидно, что если клетки 0..N-1 уже заполнены, а клетка N — пустая, то эту клетку можно заполнить только теми положениями фигур, которым клетка N принадлежит, и при этом является минимальной по номеру из всех клеток фигуры. Так что, отсортировав фигуры по номеру минимальной клетки, можно заметно сократить перебор.
Код получается таким (приведены только измененные функции):
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++;
}
Удивительно, но этот вариант оказался быстрее предыдущего в 50 с лишним раз — он находит 95 решений в секунду, и полный перебор всей головоломки происходит за 203 секунды. Причину пока понять не удалось. Любая попытка изменить порядок перебора приводит к увеличению числа вызовов Solve(). Но зато время можно уменьшить еще вдвое, если искать свободную клетку, начиная с найденной в прошлый раз:
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++;
}
Полное время работы — 102 секунды, примерно в 1250 раз меньше, чем в первом рассмотренном варианте. При этом программа удлинилась ненамного: около 130 строк на всё.
Открытые вопросы
Первый вопрос — технический. Есть поток 64-битных чисел в количестве от 10 до 10000 штук. В каждом числе не более 5 поднятых битов. Требуется определить, какой бит поднят в наибольшем количестве этих чисел. Как это сделать наиболее эффективно?
Второй вопрос — скорее, философский. Почему наиболее эффективным оказывается заполнение клеток именно по строкам, потом по слоям? Я пробовал заполнять вершины, потом ребра… Результат был на несколько порядков хуже, чем в случае лексикографического порядка. В чем тут может быть дело?
