Pull to refresh

Собираем Mini Bedlam Cube

Algorithms *
Программу, решающую головоломку «пентамино» я написал в качестве одной из первых своих программ. Дело было давно, программа как-то работала, всех вариантов найти не успела… В общем, написал и забыл.

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

Второй вопрос — скорее, философский. Почему наиболее эффективным оказывается заполнение клеток именно по строкам, потом по слоям? Я пробовал заполнять вершины, потом ребра… Результат был на несколько порядков хуже, чем в случае лексикографического порядка. В чем тут может быть дело?
Tags:
Hubs:
Total votes 36: ↑33 and ↓3 +30
Views 4.6K
Comments Comments 26