Re: Я дошёл до N=20
От: Pushkin Россия www.linkbit.com
Дата: 11.03.03 08:37
Оценка: 60 (4)
Йессс, я сделал это!
С самого начала поставил себе этот рубеж как предел мечтаний,
и вот наконец после 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;
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.