Программу, решающую головоломку «пентамино» я написал в качестве одной из первых своих программ. Дело было давно, программа как-то работала, всех вариантов найти не успела… В общем, написал и забыл.
На днях, наводя порядок на столе, решил, что пора бы убрать валяющуюся без дела головоломку «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 поднятых битов. Требуется определить, какой бит поднят в наибольшем количестве этих чисел. Как это сделать наиболее эффективно?
Второй вопрос — скорее, философский. Почему наиболее эффективным оказывается заполнение клеток именно по строкам, потом по слоям? Я пробовал заполнять вершины, потом ребра… Результат был на несколько порядков хуже, чем в случае лексикографического порядка. В чем тут может быть дело?
