Йессс, я сделал это!
С самого начала поставил себе этот рубеж как предел мечтаний,
и вот наконец после 6 часов раздумий мой Celeron 1300 выдал строку
N=20: 2870671950
Именно столько уникальных полимино 20-го порядка существует с точностью до отражений.
Кто пытался что-то колдовать на эту тему, поймёт, что дойти до N=20 не просто.
Дело в том, что число позиций нарастает примерно вчетверо с каждым следующим N.
Случай N=12, на котором засвопилась прога уважаемого RS, у меня считается менее секунды.
С другой стороны максимально известный результат N=28 потребует 50 лет моего счёта,
так что явно есть куда расти
Помимо итогового результата перечислю ещё
несколько вкусностей своего алгоритма.
(Могу я доставить себе удовольствие после двухдневного трещания мозгами?
)
— Только проц!
Совсем не нужно памяти (кроме нескольких килобайт "на текущие нужды") На самом деле, если хранить уже найденные полимино, то даже при нереальной упаковке каждого из них в 1 байт суммарный размер достигнет гигабайт — придётся с диском работать, и конечно не закончить в разумные времена.
—
Линейная зависимость от окончательного числа вариантов. Иными словами, прога выдаёт сто с чем-то тысяч уникальных полимино в секунду, а уж сколько их окажется всего — это не от неё зависит. (На самом деле производительность чуть падает, что связано с увеличением каждой полимино, так что правильнее говорить, что прога выдаёт два с чем-то миллиона клеток в секунду)
—
Прямой счёт нужного N без подсчёта всех предыдущих.
—
Неиспользование стандартных библиотек - всё своё ношу с собой.
— Вполне себе
коротенький текст - 3 функции, 3 страницы.
— Алгоритм явно
можно ещё ускорить в разы, а то и на порядки.
Теперь вкратце кому интересно,
как оно работает.
(Для тех, кто лучше читает прямо на Си, внизу весь код.
Его также можно откомпилить и поиграться.)
Основной вопрос — как кодировать одну конфигурацию.
Я искал кратчайшую кодировку для хранения,
а найдя, построил на ней алгоритм вовсе без хранения.
Итак,
кодировать одно полимино порядка N будем массивом из N-1 чисел.
Каждое полимино имеет верхнюю строчку. А в ней есть самая левая клетка.
Это старт — поставим там первую клетку полимино.
Все верхние строчки и левую часть этой сразу замажем (запретим).
Из старта можно выйти всего двумя
возможностями — вправо и вниз.
Либо полимино для постановки следующей клетки использует первую же возможность,
либо пропускает несколько возможностей.
Число пропущенных возможностей при постановки n+1 клетки и есть n-й элемент массива.
Каждая вновь поставленная клетка замазывает поле и ставит себя в очередь.
Когда до неё дойдут, то она родит 1,2, или 3 (но не больше) возможностей развития,
которые опять же могут быть использованы или пропущены.
Таким образом мы
волновым алгоритмом получаем всё полимино по массиву.
Замечательно, что полимино
однозначно кодируются и декодируются.
Но не все массивы могут быть декодированы.
Если в нём есть слишком большие числа, особенно в начале,
то это означает требование пропустить много возможностей выхода,
что грозит обрубанием полимино и недостижением проектной величины.
Поэтому мы имеем что-то вроде позиционной системы с N-1 позицией,
вот только основание не константа — каждый раз надо проверять отдельно,
можно ли сейчас увеличить вот эту цифру, раскодируется ли последовательность.
Алгоритм перебора выглядит очень похоже на алгоритм
перебора всех 19-значных чисел.
Причём из-за отмеченной выше однозначности мы встретим все полимино и ровно по 1 разу.
Последний вопрос — как
отбрасывать отражения.
Очень просто! Надо лишь ввести какое-либо правило, говорящее,
"главное" это полимино или нет среди всех своих отражений.
Например, взять полимино, отразить его 7 раз и выбрать "минимальный" массив (memcmp).
Но есть и гораздо более быстрые простые способы
Ну и наконец,
собственно код.
Это не оконнчательный вариант, он в 3 раза медленнее, зато в 5 раз прозрачнее.
Если вдруг найдётся желающий это ускорить, буду очень рад. (А это точно можно —
основная функция Decode() всё время раскрывает почти одно и то же и каждый раз сначала. )
// Polymino.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <stdlib.h>
//максимальный порядок полимино
#define N 20
//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
char board[N+1][2*N-2];
// полимино в раскодированном виде, удобном для отражений
//поле битвы и результат работы основной функции Decode()
//матрица [y][x], в ячейках одно из 3-х значений:
//-1 - запрет - точно нет заполненной клетки
// 1 - стоит - точно есть заполненная клетки
// 0 - туман - пока неизвестно, есть ли клетка
int x1,x2,y1,y2; //границы полимино, лежащего в board[][]
//основная функция
//декодирует в board последовательность
//лежащую в массиве pack[n]
//останавливается в конце массива
//или при невозможности двигаться дальше
//в последнем случае возвращает false
//верхняя строка в результирующем board пустая
//вторая сверху строка начинается с клетки N-2
bool Decode(int pack[],int n)
{
static int fifo_x[N-1];
static int fifo_y[N-1];
static int fifo_tail=0;
static int fifo_head=0;
memset(board, 0,sizeof(board)); //заполняем всё туманом
memset(board,-1,sizeof(board[0][0])*(3*N-4)); //заполняем начало запретами
//поставим первую клетку
fifo_x[0]=N-2;
fifo_y[0]=1;
fifo_tail=1;
fifo_head=0;
board[fifo_y[0]][fifo_x[0]]=1;
x1=x2=fifo_x[0];
y1=y2=fifo_y[0];
//основной цикл декодирования
int pos=0,count=0;
while(fifo_tail>fifo_head)
{
for(int d=0;d<4;d++)
{
int y=fifo_y[fifo_head]+dy[d];
int x=fifo_x[fifo_head]+dx[d];
if(board[y][x]==0) //в тумане
{
if(count==pack[pos])
{
board[y][x]=1; //поставили
//поправим границы
if(y>y2) y2=y;
else if(x<x1) x1=x;
else if(x>x2) x2=x;
//переходим к следующему элементу pack
if(++pos==n)
return true; //если конец - уходим
count=0;
//помещаем поставленную клетку в очередь
fifo_y[fifo_tail]=y;
fifo_x[fifo_tail]=x;
fifo_tail++;
}
else
{
count++; //считаем отказы
board[y][x]=-1; //помечаем отказ
}
}
}
fifo_head++; //убираем обработанную клетку из очереди
}
return false;
}
//возвращает true если в board находится "правильно" повёрнутая конфигурация
//"правильность" можно задавать довольно произвольно, важно чтобы однозначно -
//среди всех 8 отражений должно быть ровно 1 правильное
bool IsMainBoard()
{
int ny=y2-y1, nx=x2-x1;
if(nx<ny)
return false;
int reflect_impossible[2][2][2]={0};//[x<->y][y<->ny-y][x<->nx-x]
for(int y=0;y<=ny;y++)
for(int x=0;x<=nx;x++)
{
if(1==board[y1+y][x1+x])
{
if(1!=board[y1+y ][x1+nx-x]) reflect_impossible[0][0][1] =1;
if(1!=board[y1+ny-y][x1+x ]) reflect_impossible[0][1][0] =1;
if(1!=board[y1+ny-y][x1+nx-x]) reflect_impossible[0][1][1] =1; if(nx==ny) {
if(1!=board[y1+x ][x1+y ]) reflect_impossible[1][0][0] =1;
if(1!=board[y1+x ][x1+nx-y]) reflect_impossible[1][0][1] =1;
if(1!=board[y1+nx-x][x1+y ]) reflect_impossible[1][1][0] =1;
if(1!=board[y1+nx-x][x1+nx-y]) reflect_impossible[1][1][1] =1; }
}
else if( 1==board[y1+y ][x1+nx-x] && reflect_impossible[0][0][1]==0 ||
1==board[y1+ny-y][x1+x ] && reflect_impossible[0][1][0]==0 ||
1==board[y1+ny-y][x1+nx-x] && reflect_impossible[0][1][1]==0 || nx==ny &&(
1==board[y1+x ][x1+y ] && reflect_impossible[1][0][0]==0 ||
1==board[y1+x ][x1+nx-y] && reflect_impossible[1][0][1]==0 ||
1==board[y1+nx-x][x1+y ] && reflect_impossible[1][1][0]==0 ||
1==board[y1+nx-x][x1+nx-y] && reflect_impossible[1][1][1]==0 ) )
{
return false;
}
}
return true;
}
//подсчитывает все полимино порядка n
void Enum(int n, unsigned int& countAll, unsigned int& countMain)
{
countAll=countMain=0;
if(n<2)
{
if(n==1)
countAll++,countMain++;
return;
}
int* pack=new int[n-1];
memset(pack,0,(n-1)*sizeof(int));
while(1)
{
if(Decode(pack,n-1))
{
countAll++; //считает все полимино
if(IsMainBoard())
countMain++; //считает с точностью до отражений
pack[n-2]++;
}
else
{
for(int i=n-2;pack[i]==0;i--)
{
}
if(i==0)
{
delete[] pack;
return;
}
pack[i]=0;
pack[i-1]++;
}
}
}
int main(int argc, char* argv[])
{
while(1)
{
char s[80];
gets(s);
if(s[0]=='?' || strlen(s)==0 || strlen(s)>N-1)
{
if(strlen(s)>N-1 || atoi(s+1)>N)
{
printf("To work with such big polyminoes change \"#define N ...\" line in code.\n\n");
continue;
}
if(atoi(s+1)<=0)
{
printf("Examples:\nEnter ?10 to count polyminos with order 10.\nEnter sequence 0102 to decode it.\n\n");
continue;
}
//считает все полимино
unsigned int countAll,countMain,n=atoi(s+1);
Enum(n,countAll,countMain);
printf("N=%u Total=%u Main=%u\n\n",n,countAll,countMain);
}
else
{
int pack[N-1];
int n=strlen(s);
for(int i=0;i<n;i++) //читает набитую последовательность
pack[i]=s[i]-'0';
bool res1=Decode(pack,n),res2=IsMainBoard();
printf("%s %s\n\n", res1?"OK":"Fails",res1&&res2?" Main":"");
//говорит, можно ли её декодировать и "правильная" ли она
//затем выводит саму полимино - результат декодирования
for(int y=0;y<=y2-y1;y++)
{
for(int x=0;x<=x2-x1;x++)
printf(board[y1+y][x1+x]==1? "\1":" ");
printf("\n");
}
printf("\n\n");
}
}
while(getchar());
return 0;
}