Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 11:44
Оценка: 36 (2)
Товарищу Pushkin'у, я так полагаю, просто сны снятся про полимино. Вот ему некоторые результаты:

Степень, количество вместе с поворотами и отражениями, и количество без поворотов и отражений.

 1:      1,     1
 2:      2,     1
 3:      6,     2
 4:     19,     5
 5:     63,    12
 6:    216,    35
 7:    760,   108
 8:   2725,   369
 9:   9910,  1285
10:  36446,  4655
11: 135268, 17073


И тут же вопрос: является ли это полимино?
***
* *
***


P.S. В слове полимино на какой слог ударение?
Re: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 11:52
Оценка:
Здравствуйте, RS, Вы писали:

RS>Товарищу Pushkin'у, я так полагаю, просто сны снятся про полимино. Вот ему некоторые результаты:



Я тоже было начал, но не успел, там до фига работы, если хочешь серьёзной цифры достигнуть.
Обязаюсь на трёх ближайших выходных тоже что-нить выдать.
Гей, программеры, не всё вам за мимозой бегать, подсоединяйтесь !

RS> 7: 760, 108


У Гарднера 105.
Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.
ххх
х х
хх


RS>И тут же вопрос: является ли это полимино?

RS>
RS>***
RS>* *
RS>***
RS>


Думаю, да. Зачем искусственно усложнять себе жизнь.

RS>P.S. В слове полимино на какой слог ударение?


Логично как в домино — на последний.
Re[2]: <3^N
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 11:56
Оценка:
P>Здравствуйте, RS, Вы писали:

Кстати, я получил теоретический результат.

Для больших N число полимино растет как k^N, где 2<k<3
Re[2]: Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 12:03
Оценка:
Здравствуйте, Pushkin, Вы писали:

Вопрос то про полимино встал, когда нужно было придумать способ сгенерить все лабиринты из N клеток. Можно сделать это так:

Берем каждую полимино из N клеток, каждую клетку рассматриваем как взвешенный неориентированный граф из четырех вершин и четырех ребер, у каждого ребра вес равен единице (граф в виде квадрата, думаю, это понятно). Объединяем графы каждой клетки полимино по следующему правилу:
множество вершин — объединение множеств вершин графов каждой клетки,
множество ребер — объединение множеств ребер графов каждой клетки,
вес ребра — сумма весов этого ребра в каждом графе клеток полимино.

Тогда ребра с весом 1 — граница лабиринта (стопудовая стенка),
ребра с весом 2 — стенка может быть, может не быть. Вот это и надо перебирать, проверяя для каждого варианта доступность всех клеток.
Если ребро имеет вес, меньший единицы или больший двух, напиши жалобное письмо Б.Гейтсу на хинди или китайском
Re[2]: Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 12:39
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>У Гарднера 105.

P>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.

А кто это? И хотелось бы увидеть все 105 и сравнить (моя софтина генерит их в emf)
Re[3]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 12:45
Оценка:
Здравствуйте, RS, Вы писали:

P>>У Гарднера 105.

P>>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.
RS>А кто это? И хотелось бы увидеть все 105 и сравнить (моя софтина генерит их в emf)

Я дома ещё раз гляну в книжку, может там нарисовано, а может я и цифру забыл.
А так дождись ещё чьей-нибудь софтины, например моей

Кстати, сколько байт нужно твоей софтине, чтобы хранить все 108 ?
Re[4]: Количество полимино
От: RS Земля ICQ: 148844272
Дата: 05.03.03 13:00
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Кстати, сколько байт нужно твоей софтине, чтобы хранить все 108 ?


Во первых, софтин две. Одна генерит и пишет в compound file storage (StgCreateDocfile). И вот ей не хватило памяти (320 Мб) для 13-ой степени. Начинала по-черному свопиться, и я ее убил . А вторая открывает сгенеренный файл и рисует полимино, сгруппированные по 1-8 штук (повороты и отражения) на каждой отдельной emf. Эта софтина загнулась на 12-й степени, когда писала ~60000-ый файл.
Ну а во-вторых, чтобы просто хранить все 108, ей надо 760*7*2 байт, плюс издержки std::set. Группировка повернутых/отраженных производится при сохранении.
Re[5]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 05.03.03 13:24
Оценка:
Здравствуйте, RS, Вы писали:

RS>Во первых, софтин две. Одна генерит и пишет в compound file storage (StgCreateDocfile). И вот ей не хватило памяти (320 Мб) для 13-ой степени. Начинала по-черному свопиться, и я ее убил

RS>Ну а во-вторых, чтобы просто хранить все 108, ей надо 760*7*2 байт,

Многовато.
Думаю, это центральный вопрос всей задачи.
Re[3]: <5^N :)
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 06:49
Оценка: 6 (1)
Здравствуйте, Pushkin, Вы писали:

P>Кстати, я получил теоретический результат.

P>Для больших N число полимино растет как k^N, где 2<k<3

Как всякий нормальный теоретик , получив экспериментальные данные, явно опровергающие теорию, я пересмотрел решение ещё раз и нашёл небольшую ошибку, исправив которую, имею результат, в котором (на сегодняшний день ) уверен.

2<k<5

С точки зрения математики результат собственно не изменился.
Сам факт степенного роста замечательно подтверждился результатами RS.
Экстраполировав отношения величин в соседних строчках, имеем

k ~ 4
Re[2]: Количество полимино
От: MichaelP  
Дата: 06.03.03 06:50
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, RS, Вы писали:



RS>> 7: 760, 108


P>У Гарднера 105.

P>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.

У RS все данные правильные см. здесь

А вот формулы Puskin-а по оценке количества полимино расходятся с мировой научной мыслью

Как выглядят полимино вплоть до 8-го порядка можно посмотреть здесь.
Re[3]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 07:01
Оценка:
Здравствуйте, RS, Вы писали:

RS>Здравствуйте, Pushkin, Вы писали:


P>>У Гарднера 105.

P>>Хотя он вполне может выкидывать дырявые, но я вижу всего одну такую.

RS>А кто это?


Вчера не заметил этого просто неприличного на данном форуме вопроса.
Мартин Гарднер один из самых известных, по крайней мере у нас, "заниматетьных математиков". Он долгое время вёл колонку в уважаемом Scientific American и написал уйму книжек на эту тему. Совсем недавно здесь переиздали три, по-моему, штуки. Очень занимательное чтение, почти детектив.

Кстати, у него есть и собственные научные успехи. Например, он был один из тех, кто научился разрезать квадрат на неповторяющиеся квадраты. (То, что это сильно нетривиальная задача, видно хотя бы из того, что сделали её только во второй половине 20 века, и не потому что не хотели).

RS>И хотелось бы увидеть все 105 и сравнить (моя софтина генерит их в emf)


Каюсь, память подвела. Вчера посмотрел — действительно 108, включая одну дырявую. Так что вплоть до N=7 твои результаты можно считать верными. Весьма вероятно, что и дальше тоже.
Re[4]: Количество полимино
От: mrhru Россия  
Дата: 06.03.03 07:16
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>>>У Гарднера 105.


RS>>А кто это?


P>Вчера не заметил этого просто неприличного на данном форуме вопроса.


и так:

P>Мартин Гарднер один из самых известных, по крайней мере у нас, "заниматетьных математиков". Он долгое время вёл колонку в уважаемом Scientific American и написал уйму книжек на эту тему. Совсем недавно здесь переиздали три, по-моему, штуки. Очень занимательное чтение, почти детектив.




У меня дома, издания выпуска 196.. года и если не ошибаюсь, их периодически переиздавали раз в десятилетие.
Евгений
Re[3]: Количество полимино
От: Pushkin Россия www.linkbit.com
Дата: 06.03.03 07:22
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>У RS все данные правильные см. здесь

MP>А вот формулы Puskin-а по оценке количества полимино расходятся с мировой научной мыслью

А клёво я успел поправиться за минутту до того, как ты меня вывел на чистую воду
Хорошая ссылка, спасибо. На том же самом сайте, золотая жила однако
Выходит у меня всё правильно было, только границы для k можно ещё сжать.
Я кстати удивлён, что так широко они продолжают стоять.
У меня была иллюзия, что только лень не даёт мне получить ТОЧНОЕ значение для k.
Там надо перебирать чёртову прорву вариантов, но всё же вроде как конечное число.
Попробую поколдовать ещё, вдруг удастся двинуть вперёд мировую научную мысль

PS
Я так и не понял, для какого максимального N получено F(N)

PPS
А вообще-то ты нам конкурс тут не порть!
Когда ответы известны, глупо как-то напрягаться...
Re[4]: Количество полимино
От: MichaelP  
Дата: 06.03.03 07:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Я так и не понял, для какого максимального N получено F(N)


До 28. Вторая таблица содержит непроверенные данные.
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;
}
Re[2]: Re[2]: Я дошёл до N=20
От: mrhru Россия  
Дата: 11.03.03 10:08
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Йессс, я сделал это!


Йессс, ты сделал это!

Громадьё свершений не позволяют даже в полной мере сразу оценить это!
Евгений
Re[4]: <5^N :)
От: RS Земля ICQ: 148844272
Дата: 11.03.03 10:08
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>2<k<5


А где выкладки? Очень интересно.
Re[2]: Я дошёл до N=20
От: RS Земля ICQ: 148844272
Дата: 11.03.03 10:12
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Йессс, я сделал это!


Проклятье! А я только до N=15
Re[5]: <5^N :)
От: Pushkin Россия www.linkbit.com
Дата: 11.03.03 12:42
Оценка:
Здравствуйте, RS, Вы писали:

P> 2<k<5

RS>А где выкладки? Очень интересно.

Выкладки, к сожалению, не слишком строги.
Более того, чем дальше, тем менее очевидными они мне кажутся.
Но идея базируется на представлении, предложенном в базовой статье
Автор: Pushkin
Дата: 11.03.03


Любое полимино порядка N получается волновым алгоритмом из массива N-1 чисел.
Поначалу мне казалось, что в этом массиве могут быть только числа 0,1,2.
Действительно, раз мы вошли в клетку через одну стенку, то возможностей для выхода всего 3.
Если учесть ещё максимум 2 упущенных выхода из предпоследней клетки, получается, что всяких цепочек никак не больше, чем 5^N.

Но к сожалению, для разветвлённых полимино легко придумать допустимую последовательность со сколь угодно большими числами. Для этого надо устраивать несколько путей и потом одновременно из зарезать, т.е. устроить "миг упущенных возможностей".

Единственная надежда, что таких специальных полимино с большим количеством одновременно обрубающихся концов статистически мало. Большинство имеет 1-2-3 конца (чтобы не было недоразумений, концом я называю те клетки, которые остались в очереди к моменту исчерпания всех N клеток полимино).

Короче неясно всё...
Re[6]: О базовой статье
От: RS Земля ICQ: 148844272
Дата: 11.03.03 12:51
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Но идея базируется на представлении, предложенном в базовой статье
Автор: Pushkin
Дата: 11.03.03


Не понял я твою базовую статью, да и ручку дома забыл, порисовать нечем
Было бы неплохо, если бы ты ее объяснил поподробнее, не упуская ничего из виду, давая определения своим терминам.

P.S. Я за выходные (вернее ночь с пятницы на субботу) немного усовершенствовал старый алгоритм, но так и не придумал никакого, которому бы не нужна была память (в таких количествах).
Re[2]: Пояснения к базовой статье
От: Pushkin Россия www.linkbit.com
Дата: 11.03.03 14:07
Оценка: 15 (1)
Для тех, кто правда хочет понять как работает приведённый выше код,
приведу кодирование ручками вот такого полимино:

    оo 
     oо
     o
     о


Функция Decode() в тексте делает обратное преобразование,
(а функция Code() удивительным образом не понадобилась).

Кстати неплохо откомпилить и вводить тестовые последовательности
в окно проги процессе разбирательства.

Нарисуем на бумаге здоровую матрицу
(достаточно N+1 ячеек по Y и 2N-2 по X, но можете нарисовать побольше)

Поставим первую клетку — будем обозначать их цифрами по возрастанию.
(На бесконечной бумаге в клетку всё равно где поставить,
на конечной — в середине второй сверху строки)


     1


Будем считать, что это самая первая сверху-вниз-слева-направо клетка будущего полимино.
(Все его клетки ведь можно упорядочить как буквы в книжке, правда? И всегда есть первая.)
Поэтому замажем всё, что сверху и слева

...........
.....1


Пока в нашей кодирующей последовательности не появилось ни одного числа — потому что у нас не было никакого выбора и значит нет информации. Ставим следующие клетки, появляются первые байты:

Из любой поставленной клетки можно выйти ровно 4-мя способами — налево, вверх, направо, вниз.
Раз и навсегда зафиксируем именно такой порядок попыток выхода.
Но в некоторые стороны можно даже не пытаться выходить.
Из нашей первой клетки например можно даже не пытаться выходить налево и наверх — там всё замазано.
Ближайшая возможность выйти (по порядку) — направо.
И мы её не упускаем — идём.

0
............
.....12


Т.е. при постановке следующей клетки мы не упустили ни одной возможности по порядку.
Поэтому первой цифрой в нашей кодирующей последовательности будет 0.

Далее нам надо поставить клетку вниз от 2.
Давайте посмотрим, сколько возможностей мы похерим по дороге.
Прежде всего мы похерили следующий по порядку путь из 1 — вниз.
Далее мы похерили путь из 2 вправо, а он более предпочтителен,
чем вниз согласно нашему фиксированному порядку.
(Пути из 2 влево и вверх мы даже возможностями не считаем —
влево и так ясно, что стоит, а вверх нельзя)
Таким образом, мы похерили ровно две реальных возможности
расширения нашего полимино и вторая цифра кода 2.

02
............
.....12.
     .3


Обратите внимание, все похеренные возможности мы тоже замазываем,
чтобы в будущем даже не считать их за возможности
.

Дальше из точки 3 у нас есть всего два возможных пути и мы оба их используем —
в последовательности появляется ешё два нуля.

0200
............
.....12.
     .34
      5


Первый раз возник момент, когда у нас дожидаются в очереди на обслуживание
две клетки, из которых можно расти дальше — 4 и 5.

Следующую клетку надо поставить под пятой.
Но сначала надо учесть, сколько раз мы не вышли из четвёртой — она появилась у нас раньше.
Из неё мы могли ходить вправо и вниз, но никуда не пошли, значит имем +2 похеренные возможности и 2 замазанные клетки.

............
.....12.
     .34.
      5.


Из пятой мы тоже идём вниз, а не налево, как положено по порядку, поэтому добавляем к счётчику ещё 1.
(вверх и направо мы даже и не пытаемся — там не чистая бумага). Поэтому последняя цифра 3.

02003
............
.....12.
     .34.
     .5.
      6


Всё приехали!
Мы поставили 6-1=5 цифр в кодирующую последовательность
и значит зашифровали 6-мино (первая клетка далась на халяву).
Можете набрать эту строчку 02003 в консольном окне проги и увидите именно эту раскоряку.
А если вы наберёте вместо последней тройки четвёрку, то прога напишет Fails —
ей просто некуда поставить последнюю клетку, вы пропустили все возможности!
Кстати все промежуточные последовательности тоже можно набивать — получите промежуточные позиции.
Re[2]: Я дошёл до N=20
От: MichaelP  
Дата: 11.03.03 19:52
Оценка: 20 (1)
Здравствуйте, Pushkin, Вы писали:

Отлично!
Даешь 21!

Чтобы приблизить это событие рискну предложить следующее улучшение:

В процессе операции Decode, насколько я понял, заодно получается объемлющий прямоугольник. Можно заодно посчитать и центр тяжести полимино. Если он(ц.т.) не попадает на диагонали или вертикаль(горизонталь), делящие объемлющий прямоугольник пополам, то очень легко выбрать главный, по положению центра тяжести.
А если уж попали на одну из этих линий — возвращаемся к старому алгоритму.
Здесь вполне можно обойтись целочисленной арифметикой, т.к. при нахождении ц.т. можно обойтись без деления на кол-во клеточек.
Re[3]: Я дошёл до N=20
От: Pushkin Россия www.linkbit.com
Дата: 12.03.03 06:38
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Чтобы приблизить это событие рискну предложить следующее улучшение:

MP>В процессе операции Decode, насколько я понял, заодно получается объемлющий прямоугольник. Можно заодно посчитать и центр тяжести полимино. Если он(ц.т.) не попадает на диагонали или вертикаль(горизонталь), делящие объемлющий прямоугольник пополам, то очень легко выбрать главный, по положению центра тяжести.
MP>А если уж попали на одну из этих линий — возвращаемся к старому алгоритму.

IsMainBoard() вполне совершенна и быстра.
По крайней мере она точно не жрёт основную долю времени.
Если её вовсе закомментарить, убыстрится даже не вдвое.
Поэтому мне кажется на этом пути нас не ждут сияющие вершины.
Мне кажется, что персперктивней объединять Decode() и Enum() в одну, вероятно рекурсивную, функцию.
Чтобы Decode() не пахал много раз по уже вспаханному.
Re[4]: Я дошёл до N=20
От: MichaelP  
Дата: 12.03.03 06:51
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>IsMainBoard() вполне совершенна и быстра.

P>По крайней мере она точно не жрёт основную долю времени.
P>Если её вовсе закомментарить, убыстрится даже не вдвое.
P>Поэтому мне кажется на этом пути нас не ждут сияющие вершины.
P>Мне кажется, что персперктивней объединять Decode() и Enum() в одну, вероятно рекурсивную, функцию.
P>Чтобы Decode() не пахал много раз по уже вспаханному.

Логично. Но тогда можно отказаться от кодирования числом и заменить поиск в ширину (волновой алгоритм) поиском в глубину. Тогда глубина вложенности равна количеству квадратов, и очень просто делать "откат" назад.
Re[5]: Я дошёл до N=20
От: Pushkin Россия www.linkbit.com
Дата: 12.03.03 06:55
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Логично. Но тогда можно отказаться от кодирования числом и заменить поиск в ширину (волновой алгоритм) поиском в глубину. Тогда глубина вложенности равна количеству квадратов, и очень просто делать "откат" назад.


Уверен, что ты справишься
Re[6]: Я дошёл до N=20
От: MichaelP  
Дата: 12.03.03 07:27
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Уверен, что ты справишься


Мне бы с работой справиться
Re: 22: 345532572678 43191857688
От: Pushkin Россия www.linkbit.com
Дата: 14.03.03 09:26
Оценка: 53 (3)
Вот до такой строчки мой комп додумался сегодня ночью Не сам, конечно, а после сильной переработки кода. По сравнению с ранее опубликованным всё бегает раз в 15 быстрее. Прога по-прежнему нагружает только проц. Можно перевести её в низкий приоритет и комфортно работать на компе. И лет через 8 я достигну инетовского рекорда 28

Замечательно, что ускорение совпало с сильным упрощением текста. Пропало сложное и немного искусственное понятие "кодирующей последовательности". Две функции слились в одну весьма прозрачную, рекурсивную, как и просилось сразу. Она ровно по разу обходит все полимино порядка n и считает их, а заодно (почти без потерь времени) и все меньшие порядки.

После ускорения перебора в полный рост встал вопрос об ускорении отсеивания отражений (который раньше был не критичен). Здесь крайне своевременной оказалась идея МихаилаП о "центре тяжести". (В моём воспалённом мозгу она тоже бродила, но давно и не столь ясно.) Забавно, что при внешней простоте, идея потребовала очень аккуратной реализации — я долго не мог добиться одновременно верного ответа и ясного понимания, что делаю. (Хотя порознь было много раз )

Ниже приведён код, который можно откомпилировать и поиграться (даже порисовать). Я нахожу его совершенным и потому больше не буду терроризировать ни себя ни вас. Если кому-то удастся серьёзно ускорить, оценку обещаю Пояснять код нет большого смысла, тем более, что там половина строк комментарии.

// 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 33 //странная цифра, но почему нет :-)

//если не жалко времени, можно рисовать полимино
//либо для всех порядков либо только для старшего 
//причём выводим не в банальный столбик, а в строчку ;-)
//#define NEED_DRAW_ALL 
//#define NEED_DRAW_HIGH
#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
char out[N+1][80]={0};
#endif

//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

char board[N+1][2*N-2];
// полимино в раскодированном виде, удобном для отражений
//поле битвы и результат работы основной функции Enum()
//матрица [y][x], в ячейках одно из 3-х значений:
//-1 - запрет - точно нет заполненной клетки
// 1 - стоит - точно есть заполненная клетки
// 0 - туман - пока неизвестно, есть ли клетка
int x1,x2,y1,y2;//границы полимино, лежащего в board[][]
int x0,y0;      //а здесь лежать суммы всех x и y для вычисления среднего

//довесок к board - перспективы заполнения
int fifo_x[N-1]; 
int fifo_y[N-1];
int fifo_tail=0;
int fifo_head=0;

int n; //порядок полимино (цель)
int k; //сколько клеток уже поставлено
__int64 countTotal[N], countMain[N];//здесь будем считать, 
//причём сразу оба (всего и без отражений) и для всех порядков

//вспомогательная функция для отсеивания отражений
bool IsMainBoard();

//основная рекурсивная функция
//в результате её работы вглубь от k=0 до k=n
//в board последовательно перебывают ровно по одному разу (!)
//все полимино порядка не больше n (вообще все, с отражениями)
//стартуя с того, что сейчас лежит в board+fifo+k
//подсчитывет число продолжений до порядка n
//в результате board+fifo+k остаётся без изменений (!)
void Enum()
{
    if(k==0) //первый вход
    {
        memset(countTotal,0,sizeof(countTotal));
        memset(countMain ,0,sizeof(countMain ));
        
        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; 
        x0=x1=x2=fifo_x[0];
        y0=y1=y2=fifo_y[0];
        
        k=1;
        Enum();
        k=0;                  //board+fifo можно не восстанавливать - 
        return;               //при следующем входе всё равно обнулим
    }
        
    int save_fifo_head=fifo_head; //сохраним чтобы потом вернуть

    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)     //точка в тумане - нашли !
            {                
                board[y][x]=1; //сначала попробуем сюда поставить
                k++;
            
                int save_y2=y2;//поправим границы
                int save_x1=x1;
                int save_x2=x2;
                if(y>y2) y2=y;
                if(x<x1) x1=x;
                if(x>x2) x2=x;
                x0+=x;
                y0+=y;
                
                //помещаем поставленную клетку в очередь 
                fifo_y[fifo_tail]=y;
                fifo_x[fifo_tail]=x;
                fifo_tail++;
            
                countTotal[k]++;
                if(IsMainBoard())
                {
                    countMain[k]++;

#ifdef NEED_DRAW_HIGH
                    if(k==n)
#endif
#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
                    {
                        if(strlen(out[0])+n+1>75)
                        for(int y=0;y<n+1;y++)
                            printf("%s\n",out[y]),out[y][0]=0;
                        for(int y=1;y<n+1;y++)
                        for(int x=0;x<n+1;x++)
                            strcat(out[y-1],board[y][x1+x]==1? "\1":" ");
                    }
#endif
                }
                                
                if(k<n)         //продолжение банкета
                    Enum(); //сколько развитий при поставленной

                //теперь попробуем наоборот запретить
                board[y][x]=-1;    
                k--;
                
                //вернём границы
                y2=save_y2;
                x1=save_x1;
                x2=save_x2;
                x0-=x;
                y0-=y;
                
                //убираем из очереди 
                fifo_tail--;
                
                Enum(); //сколько развитий при запрещённой

                //наконец, не забудем отыграть всё обратно
                board[y][x]=0;    
                fifo_head=save_fifo_head;

                return; //никакого цикла реально нет - 
                //нашли первую возможность и либо ставим либо нет 
            }
        }
        
        //из этой фишки идти уже некуда - идём к следующей
        fifo_head++; 
    }

    //не нашли ни одной возможности, куда бы поставить 
    //возвращаем всё как было и уходим 
    fifo_head=save_fifo_head;

#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
    if(k==1)//конец игре - распечатаем остаток
        for(int y=0;y<n+1;y++)
            printf("%s\n",out[y]),out[y][0]=0;
#endif
}


//возвращает true если в board находится "правильно" повёрнутая конфигурация 
//"правильность" можно задавать довольно произвольно, важно чтобы однозначно - 
//среди всех 8 отражений должно быть ровно 1 правильное
//эта реализация обычно проверяет попадание центра тяжести в нужную восьмушку
//и только в пограничных случаях врубает полную мощь вычислений
//можно попробовать поулучшать, но ускорить вдвое - это вряд ли 
bool IsMainBoard()
{
    int bx=x0*2-(x1+x2)*k;
    int by=y0*2-(y1+y2)*k;

    if(bx==0 && by<0)
    {
        //проверка, а не симметричная ли фигура относительно вертикали
        int ny=y2-y1, nx=x2-x1;
        for(int y=0;y<=ny;y++)
        for(int x=0;x<(nx+1)/2;x++)
        {
            if(board[y1+y][x1+x]==1 && board[y1+y][x1+nx-x]!=1)
                return true;
            if(board[y1+y][x1+x]!=1 && board[y1+y][x1+nx-x]==1)
                return false;
        }
        return true;
    }

    else if(bx<0 && by==bx)
    {
        //проверка, а не симметричная ли фигура относительно диагонали
        int ny=y2-y1, nx=x2-x1;
        if(nx<ny)
            return false;
        if(nx>ny)
            return true;

        for(int y=0;y<=ny;y++)
        for(int x=0;x<y;x++)
        {
            if(board[y1+y][x1+x]==1 && board[y1+x][x1+y]!=1)
                return true;
            if(board[y1+y][x1+x]!=1 && board[y1+x][x1+y]==1)
                return false;
        }
        return true;
    }

    else if(bx==0 && by==0)
    {
        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;
    }

    //почти всегда доходим до этого места, особенно для больших порядков

    if(bx<0 && by<bx)
        return true; //здесь выходим примерно 1/8 случаев

    return false; //здесь выходим примерно в 7/8 случаев
}


int main(int argc, char* argv[])
{
    while(1)
    {
        char s[80];
        gets(s);
        n=atoi(s);
        if(n<1 || n>31)
        {
            printf("Enter a polyominoe size 0<N<32\n\n");
            continue;
        }
        printf("--\n");

        k=0;Enum();
        
        printf("\n");
        for(k=2;k<=n;k++)
        {
            char s1[80],s2[80];
            _i64toa(countTotal[k],s1,10);
            _i64toa(countMain [k],s2,10);
            printf("%2d: %16s %16s\n",k,s1,s2);
        }
        printf("\n\n");
    }

    while(getchar());
    return 0;
}
Re[2]: 22: 345532572678 43191857688
От: MichaelP  
Дата: 14.03.03 10:33
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Ниже приведён код, который можно откомпилировать и поиграться (даже порисовать). Я нахожу его совершенным и потому больше не буду терроризировать ни себя ни вас. Если кому-то удастся серьёзно ускорить, оценку обещаю Пояснять код нет большого смысла, тем более, что там половина строк комментарии.


Несмотря на совершенство рискну предложить улучшения. Идея заключается в отсечении вариантов перебора по симметрии промежуточного полимино. Эта идея у меня бродила давно, но, за недостатком времени, я только вчера вечером более-менее придумал как побороть конфликт между отсечением по симметрии и идеей выбора "главного" полимино. Конфликт заключается в том, что при отсечении по симметрии мы можем выбросить и "главное". Попробую сформулировать основные "положения".

1. Если промежуточное полимино симметрично, то нам не имеет смысла пребирать симметричные варианты его дальнейшего роста.
2. Чтобы не пропустить "главное" полимино запомним "текущую" симметрию и при получении очередного решения будем проверять на "главность" не только его, но и полученные из него в результате применения данной симметрии. В случае проверки по центру тяжести это свдется к обычным сложениям/вычитаниям.

Если проверять на симметрию каждый промежуточный случай окажется слишком накладным, то можно ограничиться отдельными симметриями и/или случаями прямоугольных промежуточных решений (или даже прямоугольниками единичной толщины).

В этом случае отсечение даже только по начальному домино уменьшит количество пребираемых решений в два раза.
Re[3]: 22: 345532572678 43191857688
От: MichaelP  
Дата: 14.03.03 10:44
Оценка:
MP>1. Если промежуточное полимино симметрично, то нам не имеет смысла пребирать симметричные варианты его дальнейшего роста.
MP>2. Чтобы не пропустить "главное" полимино запомним "текущую" симметрию и при получении очередного решения будем проверять на "главность" не только его, но и полученные из него в результате применения данной симметрии. В случае проверки по центру тяжести это свдется к обычным сложениям/вычитаниям.

Забыл добавить:
Не могу доказать точно, но мне кажется, что не нужно запоминать "стек" симметрий, а можно ограничиться запоминанием последней.
Re[4]: 22: 345532572678 43191857688
От: Pushkin Россия www.linkbit.com
Дата: 14.03.03 11:13
Оценка:
Здравствуйте, MichaelP, Вы писали:

Да ты маньяк! Я только хотел отдохнуть
И отдохну, если не убедишь

1) Идея отсекать ветки пораньше конечно и у меня бродила.
Но я не смог придумать, как это сделать.
И твои мысли пока не могу понять
Может на примере объяснишь.
Как например посчитать вот эти кучки?
Что отбрасывать, где отсекать?

o o    o   ooo 
ooo   ooo    o 
o o    o   ooo
       o
       o


2) Не думаю, что это ускорит радикально.
Если я выкину вовсе проверку на главность, даже вдвое не ускорит.
А если идеально пойду вместо всех по уникальным (ах, мечта ),
то это очевидно быстрее всего в 8 раз.
Но при этом я потеряю первый столбик цифр, немного жалко.
Хотя это, конечно, заманчиво, пойти по уникальным
Re[5]: 22: 345532572678 43191857688
От: MichaelP  
Дата: 14.03.03 11:54
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, MichaelP, Вы писали:


P>
P>o o    o   ooo 
P>ooo   ooo    o 
P>o o    o   ooo
P>       o
P>       o
P>


P>2) Не думаю, что это ускорит радикально.

P>Если я выкину вовсе проверку на главность, даже вдвое не ускорит.
P>А если идеально пойду вместо всех по уникальным (ах, мечта ),
P>то это очевидно быстрее всего в 8 раз.
P>Но при этом я потеряю первый столбик цифр, немного жалко.
P>Хотя это, конечно, заманчиво, пойти по уникальным

разберу идею на примере домино:
oo


из трех вариантов продолжения
ooo   oo   oo
      o     o

третий можно отбросить, т.к. все его продолжения будут симметричны прордолжениям второго. Единственно, что нам надо запомнить это то, что у нас "потенциально" существуют продолжения третьего и при проверке на "главность" проверять заодно и варианты симметричные относительно вертикальной линии делящей исходное домино пополам.

Если у нас получился:
oo
oo

то надо продолжать только одно продолжение, но проверять на "главность" все восемь (а может и меньше, тут надо думать)

Естественно из симметричных продолжений надо выбирать то, которое потенциально скорее всего будет главным.

Далее:
из домино, отсеяв третий вариант, мы получили
ooo

У него своя ось симметрии. Надо ли проверять на "главность" варианты симметричные относительно только его оси симметрии или также относительно оси симметрии исходного домино? Мне кажется, что можно "забыть" об исходной оси симметрии (как минимум если появляется новая "аналогичная" симметрия). Единственно — надо не забыть востановить ось симметрии при откате назад.

Идея мне пришла в голову недавно и я не успел обдумать сложные моменты, на которые обратил здесь внимание.
Re[6]: 22: 345532572678 43191857688
От: Pushkin Россия www.linkbit.com
Дата: 17.03.03 07:48
Оценка:
Здравствуйте, MichaelP, Вы писали:


MP>разберу идею на примере домино:

MP>
MP>oo
MP>


MP>из трех вариантов продолжения

MP>
MP>ooo   oo   oo
MP>      o     o
MP>

MP>третий можно отбросить, т.к. все его продолжения будут симметричны прордолжениям второго.

Нет. Из третьего можно получить это

   ooо
    o


А из второго симметрично нельзя, т.к. по построению стартуем с верхнего левого.

И почему ты выбросил вертикальную полоску? Только из неё можно получить крест.

Вообще, начало построения (замазывание верха и лева) несимметрично.
Поэтому, не думаю, что симметрия поможет в его продолжении.
Если же пытаться сделать его полностью симметричным, то замедлишься в N раз,
поскольку начать можно с любой клетки.
Re: Пушкину: а теперь подсчитай количество лабиринтов
От: RS Земля ICQ: 148844272
Дата: 17.03.03 12:06
Оценка:
сабж.

Я пробовал чуть-чуть изменить твою прогу (при отсечении варианта не клетку замазываю, а стенку ставлю), так вот не получилось.

+--+--+
|     |
+  +  |
|  |  |
+--+--+

Такую получить нельзя (при пом же порядке просмотра направлений расширения).

Так что скажет автор Алгоритма?

P.S. Когда-нибудь этот алгоритм будут называть "Алгоритм Пушкина поиска полимино" и проходить в школе.
Re[2]: Пушкину: а теперь подсчитай количество лабиринтов
От: Pushkin Россия www.linkbit.com
Дата: 18.03.03 07:17
Оценка:
Здравствуйте, RS, Вы писали:

RS>
RS>+--+--+
RS>|     |
RS>+  +  |
RS>|  |  |
RS>+--+--+
RS>

RS>Такую получить нельзя (при пом же порядке просмотра направлений расширения).
RS>Так что скажет автор Алгоритма?

Да, с ходу не ясно...
Вообще продолжать вниз линейку шириной 2 — никогда не поставишь ни одной центральной стенки.
Надо будет подумать на досуге...
Эх, жаль Lermontov пропал куда-то, он бы смог
Re[3]: Пушкину: а теперь подсчитай количество лабиринтов
От: RS Земля ICQ: 148844272
Дата: 27.03.03 09:32
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Да, с ходу не ясно...

P>Эх, жаль Lermontov пропал куда-то, он бы смог

Вот пока не будет придуман способ перебора всех лабиринтов, не будет решена задача про несчастного робота. А получать все лабиринты из всех полимино очень не хочется. Хотелось бы иметь лабиринт в виде строки (как, например, твои полимино), которой можно было бы либо непосредственно оперировать, либо можно было бы легко отрендерить эту строку во что-либо удобное.

Я надеюсь, ты что-нибудь все-таки придумаешь. Удачи!
Re[4]: Пушкину: а теперь подсчитай количество лабиринтов
От: Pushkin Россия www.linkbit.com
Дата: 27.03.03 09:42
Оценка:
Здравствуйте, RS, Вы писали:


RS>Вот пока не будет придуман способ перебора всех лабиринтов, не будет решена задача про несчастного робота.


Ультиматум однако

RS>Я надеюсь, ты что-нибудь все-таки придумаешь. Удачи!


Я честно мозгой трещал пол-воскресенья прошлого.
Но потом отвлёкся на попроще
Автор: Pushkin
Дата: 24.03.03
.
Ну ничего, будем-искать-будем-искать
А чо всё пушкин? Больше некому что ли? Баллов дадим
Re[5]: Пушкину: а теперь подсчитай количество лабиринтов
От: RS Земля ICQ: 148844272
Дата: 27.03.03 10:33
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Ультиматум однако


Он самый

P>А чо всё пушкин?


Ну потому что Пушкин придумал способ представления полимино строкой. Вот и представляется мне, что Пушкин все может представить строкой, и лабиринт — не исключение.

P>Больше некому что ли?


У меня диплом

P>Баллов дадим


Заманчиво, конечно. Но времени нету, чтобы думать. А робот пока носится по лабиринтам 2x3 и 3x3. Посмотрим, что из этого выйдет. Сейчас я использую поиск в ширину до определенного момента (то есть ограничиваю сверху использование памяти), а затем перехожу к поиску в глубину. После нахождения удачного решения провожу прореживание и снова поиск в ширину. Если интересно, могу поподробнее.
Re[6]: С твоего робота пиво :)
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 07:06
Оценка: 9 (1)
http://www.rsdn.org/File/13542/Screen2.jpg

Вот так оно перебрало все лабиринты площадью 4. Площади 5 и 6 я ручками проверил, тоже вроде всё верно. Дальше надеюсь тоже не врёт. Считает довольно шустро.

Ниже код, вполне готовый к компиляции. Основная идея не сильно изменилась — волновое распространение. Начинаем с верхней-левой клетки. В неё можно поставить трёх разных "ёжиков" — только_направо, только_вниз, направо_и_вниз. Пробуем поставить каждого и пораспространяться с этого обрывка. И так далее. Каждый раз, ставя ёжика, смотрим, куда он ОБЯЗАН торчать, а куда ПО ЖЕЛАНИЮ. Все желания реализуем по очереди. Основная проблема — перебрать быстро и уникально — для этого, как обычно, организуем fifo.

Кодирующая последовательность мне здесь совсем не нужна — перебираю сразу раскодированные лабиринты. Но для понимания того, что происходит, могу описать. Каждый лабиринт кодируется линейкой полубайт — по одному на каждую занятую клетку. В каждом полубайте лежат 4 бита — наличие выходов из этой клетки во все 4 стороны. Они зависимы — каждая стенка по сути помечается дважды, поэтому кодировка явно не плотнейшая, но нам по фигу. Последовательность полубайт в линейке определяется распространением от верхней левой клетки — куда раньше пришли, та клетка раньше и описывает в линейке свои выходы.

Всё, на вопросы по коду готов ответить.
RS, как твой робот вылезет из площади 4, напиши, интересно.


// PolyminoLab.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 33 //странная цифра, но почему нет :)

//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

//если не жалко времени, можно рисовать лабиринт
//либо для всех порядков либо только для старшего 
int need_draw;

char board[N+1][2*N-2];
//поле битвы и результат работы основной функции Enum()
//матрица [y][x], в ячейках битсеты 000DRUL - 
//есть ли выходы отсюда в каждом из 4-х направлений 
//  0 - клетка точно не заполнена    
// -1 - пока неизвестно, заполнена ли клетка (туман) 
inline int GetWay(int y,int x,int d)    
    {return (board[y][x]>>d) & 1;}
inline void SetWay(int y,int x,int d,int w)
    { w? board[y][x]|=1<<d:board[y][x]&=~(1<<d); }

//довесок к board - перспективы заполнения
int fifo_x[N-1]; 
int fifo_y[N-1];
int fifo_tail=0;
int fifo_head=0;

int n;//сколько клеток надо поставить (цель)
__int64 countTotal;//здесь будем считать

//распечатывает превдографикой лабиринт, лежащий в board 
//некоторая морока связана с тем, чтобы вывести "в строчку"
//параметр end нужен только для того, чтобы допечатать последнюю строчку
void DrawLab(bool end=false)
{
    static const int pseudo[16]={' ',0xb5,0xd0,0xbc,0xc6,0xcd,0xc8,0xca,
                                     0xd2,0xbb,0xba,0xb9,0xc9,0xcb,0xcc,0xce};
    static char out[N+1][80];

    if(end || strlen(out[0])+n+1>75)
        for(int y=0;y<n+1;y++)
            printf(" %s\n",out[y]),out[y][0]=0;

    if(!end)
    for(int y=1;y<n+1;y++)
    for(int x=N-2-n;x<N-2+n;x++)
    {
        char ss[2];
        sprintf(ss,"%c",pseudo[board[y][x]>0? board[y][x]:0]);
        strcat(out[y-1],ss);
    }
}

//основная рекурсивная функция, в результате её работы вглубь 
//в board последовательно перебывают ровно по одному разу (!)
//все лабиринты порядка не больше n (с отражениями)
//стартуя с того, что сейчас лежит в board+fifo
//подсчитывает число продолжений до порядка n
//в результате board+fifo остаётся без изменений (!)
void Enum()
{
    if(fifo_tail==0) //первый вход
    {
        fifo_head=0;
        countTotal=0;
        
        memset(board,-1,sizeof(board));               //заполняем всё туманом
        memset(board, 0,sizeof(board[0][0])*(3*N-4)); //заполняем начало запретами

        //занесём первую клетку в fifo
        fifo_x[fifo_tail]=N-2;
        fifo_y[fifo_tail]=1;
        board[fifo_y[fifo_tail]][fifo_x[fifo_tail]]=-2;
        fifo_tail++;

        Enum();

        fifo_tail=0;        

        if(need_draw)
            DrawLab(true); //дорисуем остатки (последнюю строку)

        return;
    }

    if(fifo_tail>fifo_head)    //последовательное распространение 
    {           //выбираем один из концов и развиваемся с него
        int y=fifo_y[fifo_head];
        int x=fifo_x[fifo_head];
        fifo_head++; 
        
        // сейчас board[y][x]==-2 - признак постановки в fifo        
        board[y][x]=0; //разогнали туман

        //из точки можно пойти или не пойти в 4 разных стороны
        //цикл по разным вариантам заполнить вот именно эту клетку
        int w[4];
        for(w[3]=0;w[3]<2;w[3]++)
        for(w[2]=0;w[2]<2;w[2]++)
        for(w[1]=0;w[1]<2;w[1]++)
        for(w[0]=0;w[0]<2;w[0]++)
        {            
            int save_fifo_tail=fifo_tail;

            for(int d=0;d<4;d++)
            {
                //выясняем, какие пути уже известны
                if(board[y+dy[d]][x+dx[d]]>-1 && //точка уже стоит
                    GetWay(y+dy[d],x+dx[d],(d+2)%4)!=w[d]) //поругались
                        break;

                SetWay(y,x,d,w[d]);
                
                if(w[d]==1 && board[y+dy[d]][x+dx[d]]==-1) //реальное распространение
                {
                    //помещаем новую клетку в очередь 
                    fifo_y[fifo_tail]=y+dy[d];
                    fifo_x[fifo_tail]=x+dx[d];
                    board[fifo_y[fifo_tail]][fifo_x[fifo_tail]]=-2;
                    if(++fifo_tail>n) //переразвивались
                        break;
                }
            }

            if(d==4)//ни с кем не поругались и не переразвивались
                Enum();

            //возвращаем как было, это очень важно
            while(save_fifo_tail<fifo_tail)
            {
                fifo_tail--;
                board[fifo_y[fifo_tail]][fifo_x[fifo_tail]]=-1;
            }
        }

        //возвращаем как было, это очень важно
        board[y][x]=-2;
        fifo_head--; 
        return;
    }


    if(fifo_tail==n)//поставлено ровно n точек и дальше ставить некуда
    {
        countTotal++;

        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        //вот именно в этом месте мы побываем ровно столько раз, 
        //сколько есть уникальных лабиринтов площади n (с отражениями)
        //в этот момент в board лежит очередной уникальный лабиринт
        //если элемент (байт) равен 0 или -1, то клетка не входит в лабиринт
        //если имеет вид 0000DRUL, то L,U,R,D==1 если в эту сторону есть выход
        //значений другого вида в board быть не может
        //в этом месте с лабиринтом можно что-то сделать, например распечатать
        //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                
        if(need_draw)
            DrawLab();
    }
}


int main()
{
    printf("\n Enter max labirint size 0<N<32 to count.\n Add '+' after N to draw labirints while counting.\n\n");
    
    while(1)
    {
        char s[80];
        printf(" N=");
        gets(s);
        n=atoi(s);
        if(n<1 || n>31)
        {
            printf(" Labirint size must be 0<N<32.\n\n");
            continue;
        }
        if(n>10 && s[strlen(s)-1]=='+')
        {
            printf(" Too many labirints to draw!\n");
            need_draw=0;
        }
        else
        {
            need_draw = (s[strlen(s)-1]=='+');
        }
        printf("\n");

        Enum();
        
        printf("\n");
        _i64toa(countTotal,s,10);
        printf(s);
        printf("\n\n");
    }

    return 0;
}
Re[7]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 07:16
Оценка: 10 (1)
Здравствуйте, Pushkin, Вы писали:

P>Вот так оно перебрало все лабиринты площадью 4. Площади 5 и 6 я ручками проверил, тоже вроде всё верно. Дальше надеюсь тоже не врёт. Считает довольно шустро.


А вот мое. Думаю, алгоритм такой же, твою пока не смотрел.

И, кстати, это строго доказывает, что количество полимино не более, чем 8^N

// Основана на проге Пушкина от 11.03.03 11:37.
// Hail Pushkin!

#include <iostream>
#include <cassert>
#include <windows.h>

using namespace std;
// Ansifixion :)
#define for if(false); else for

// Ну это как-бы максимальное количество клеток лабиринта.
#define N 20

typedef unsigned short cell_type;

// Поле. Размер больше чем у Пушкина, так как мне пришлось еще санитарную 
// зону сделать.
cell_type field[N+2][2*N];

#define L_MASK    0x03
#define L_PASS    0x00
#define L_WALL    0x01
#define L_UNK     0x02

#define U_MASK    0x0C
#define U_PASS    0x00
#define U_WALL    0x04
#define U_UNK     0x08

#define R_MASK    0x30
#define R_PASS    0x00
#define R_WALL    0x10
#define R_UNK     0x20

#define D_MASK    0xC0
#define D_PASS    0x00
#define D_WALL    0x40
#define D_UNK     0x80

#define OCCUPIED    0x0100
#define DENIED      0x0200

cell_type dir_mask[4]={L_MASK, U_MASK, R_MASK, D_MASK};
cell_type dir_pass[4]={L_PASS, U_PASS, R_PASS, D_PASS};
cell_type dir_wall[4]={L_WALL, U_WALL, R_WALL, D_WALL};
cell_type dir_unk[4]={L_UNK, U_UNK, R_UNK, D_UNK};

int dx[4]={-1, 0, +1, 0};
int dy[4]={0, -1, 0, +1};
//int opp[4]={2, 3, 0, 1};
#define opp(d) ((d)^2)

int xmin, xmax, ymin, ymax;

#if !defined(NOBREAK)

// Эта штука нужна, чтобы можно было прервать нумерацию лабиринтов при помощи 
// Ctrl-Break или Ctrl-C, а сама прога осталась жива.
class BreakHandler
{
public:
    BreakHandler()
    {
        _stopflag=false;
        ::SetConsoleCtrlHandler(HandlerRoutine, TRUE);
    }
    ~BreakHandler()
    {
        ::SetConsoleCtrlHandler(HandlerRoutine, FALSE);
    }

    bool IsBreak()
    {
        if(!_stopflag)
            return false;
        _stopflag=false;
        return true;
    }
private:
    static BOOL WINAPI HandlerRoutine(DWORD dwCtrlType)
    {
        switch(dwCtrlType)
        {
        case CTRL_C_EVENT:
        case CTRL_BREAK_EVENT:
            _stopflag=true;
            break;
        default:
            return FALSE;
        }
        return TRUE;
    }
private:
    volatile static bool _stopflag;
};

volatile bool BreakHandler::_stopflag=false;

#endif // !defined(NOBREAK)

// Декодирует строку. Возвращает:
// 0 - строка нормально декодирована, лабиринт закрыт.
// 1 - строка не может быть декодирована - элемент последовательности принимает
//     слишком большое значение, или заперлись.
// 2 - строка декодирована, но лабиринт не закрыт.
// size - количество клеток лабиринта. Длина кодирующей последовательности 
// должна быть равна size.
int Decode(int *code, int size)
{
    int fifo_x[N];
    int fifo_y[N];
    int fifo_tail=0;
    int fifo_head=0;

    for(int y=0; y<N+2; ++y)
        for(int x=0; x<2*N; ++x)
            field[y][x]=L_UNK|U_UNK|R_UNK|D_UNK;
    for(int x=0; x<2*N; field[0][x++]|=DENIED);
    for(int x=0; x<N-1; field[1][x++]|=DENIED);

    int x=N-1;
    int y=1;
    
    xmin=xmax=x;
    ymin=ymax=y;

    for(;;)
    {
        // Занимаем клетку.
        field[y][x]|=OCCUPIED;

        // отгораживаемся от запрещенных клеток.
        for(int d=0; d<4; ++d)
            if((field[y+dy[d]][x+dx[d]]&DENIED)!=0 &&
               (field[y][x]&dir_mask[d])==dir_unk[d])
                field[y][x]^=dir_unk[d]^dir_wall[d];

        //*/ Ставим стенки согласно символу кодовой последовательности.
        int wallflags=*code;
        for(int d=0; d<4; ++d)
            if((field[y][x]&dir_mask[d])==dir_unk[d])
            {
                field[y][x]^=dir_unk[d];
                field[y][x]^=(wallflags&1)?dir_wall[d]:dir_pass[d];
                field[y+dy[d]][x+dx[d]]^=dir_unk[opp(d)];
                field[y+dy[d]][x+dx[d]]^=(wallflags&1)?dir_wall[opp(d)]:dir_pass[opp(d)];
                wallflags>>=1;
            }
        if(wallflags!=0)
            return 1;
        /**/

        // Добавляем данную клетку в начало очереди.
        fifo_x[fifo_head]=x;
        fifo_y[fifo_head]=y;
        ++fifo_head;

        // не пора ли сваливать?
        ++code;
        if(--size==0)
            break;

        while(fifo_head>fifo_tail)
        {
            // Это как бы "break 2;"
            bool bBreak=false;
            
            register int tail_x=fifo_x[fifo_tail];
            register int tail_y=fifo_y[fifo_tail];
            for(int d=0; d<4; ++d)
                if((field[tail_y][tail_x]&dir_mask[d])==dir_pass[d] &&
                   (field[tail_y+dy[d]][tail_x+dx[d]]&OCCUPIED)==0)
                {
                    x=tail_x+dx[d];
                    y=tail_y+dy[d];
                    
                    // break 2;
                    bBreak=true;
                    break;
                }

            if(bBreak)
                break;

            ++fifo_tail;
        }

        // Заперлись (кодовая последовательность не исчерпана, а очередь клеток
        // для развития опустошена).
        if(fifo_head==fifo_tail)
            return 1;

        // Подправим границы.
        if(x<xmin)      xmin=x;
        else if(x>xmax) xmax=x;

        if(y<ymin)      ymin=y;
        else if(y>ymax) ymax=y;
    }

    // Проверим, закрыт ли лабиринт. Воспользуемся тем, что к настоящему моменту
    // координаты всех клеток находятся в очереди.
    for(int i=0; i<fifo_head; ++i)
    {
        register int x=fifo_x[i];
        register int y=fifo_y[i];
        for(int d=0; d<4; ++d)
            if((field[y][x]&dir_mask[d])==dir_pass[d] &&
               (field[y+dy[d]][x+dx[d]]&OCCUPIED)==0)
                return 2;
    }

    return 0;
}

void Print()
{
    for(int y=ymin; y<=ymax; ++y)
    {
        for(int x=xmin; x<=xmax; ++x)
        {
            if((field[y][x]&U_MASK)==U_WALL) cout<<"+--";
            else                             cout<<"+  ";
        }
        cout<<'+'<<endl;
        for(int x=xmin; x<=xmax; ++x)
        {
            if((field[y][x]&L_MASK)==L_WALL) cout<<'|';
            else                             cout<<' ';
            if((field[y][x]&OCCUPIED)!=0) cout<<"\xDB\xDB";
            else                          cout<<"  ";
        }
        if((field[y][xmax]&R_MASK)==R_WALL) cout<<'|';
        cout<<endl;
    }
    for(int x=xmin; x<=xmax; ++x)
    {
        if((field[ymax][x]&D_MASK)==D_WALL) cout<<"+--";
        else                                cout<<"+  ";
    }
    cout<<'+'<<endl;
}

void Enum(int n, int verbose)
{
    if(n>N)
    {
        cout<<"Code sequence is too long"<<endl;
        return;
    }
    if(n==0)
        return;

#if !defined(NOBREAK)
    BreakHandler bh;
#endif // !defined(NOBREAK)

    int *pack=new int[n];
    memset(pack, 0, n*sizeof(int));

    int count=0;

    for(;;)
    {

#if !defined(NOBREAK)
        if(bh.IsBreak())
        {
            delete[] pack;
            cerr<<"^C"<<endl;
            return;
        }
#endif // !defined(NOBREAK)

        int res=Decode(pack, n);
        if(res==2)
        {
            ++(pack[n-1]);
        }
        else if(res==0)
        {
            if(verbose>0)
            {
                for(int i=0; i<n; cout<<pack[i++]);
                cout<<endl;
            }
            if(verbose>1)
            {
                Print();
                cout<<endl;
            }
            ++count;
            ++(pack[n-1]);
        }
        else if(res==1)
        {
            int i;
            for(i=n-1; pack[i]==0; --i) continue;
            if(i==0)
            {
                delete[] pack;
                cout<<"Mazes counted: "<<count<<endl<<endl;
                return;
            }
            pack[i]=0;
            ++(pack[i-1]);
        }
    }
}

int main()
{
    for(;;)
    {
        cerr<<'>';

        string str;
        getline(cin, str);

        if(str=="quit" || str=="exit")
            break;
        else if(str=="?" || str=="help")
        {
            cout<<
                "quit or exit - quit the program\n"
                "\? or help    - show this help message\n"
                "\?<n>         - show number of mazes composed of n cells\n"
                "\?\?<n>        - show number of mazes composed of n cells and code sequence\n"
                "               of each maze\n"
                "\?\?\?<n>       - show number of mazes composed of n cells and code sequence\n"
                "               and picture of each maze\n"
                "<ccccc>      - decode code sequence and show maze picture\n"
                "\n";
        }
        else if(str[0]=='?')
        {
            int verbose=-1;
            string::iterator itr;
            for(itr=str.begin(); itr!=str.end() && *itr=='?'; ++itr, ++verbose);
            
            Enum(atoi(string(itr, str.end()).c_str()), verbose);
        }
        else
        {
            if(str.length()>N)
                cout<<"Code sequence is too long"<<endl;
            else
            {
                int *pack=new int[str.length()];

                string::const_iterator itr;
                int pos;
                for(itr=str.begin(), pos=0; itr!=str.end(); ++itr, ++pos)
                    pack[pos]=(*itr)-'0';

                switch(Decode(pack, str.length()))
                {
                case 0:
                    Print();
                    cout<<endl;
                    break;
                case 1:
                    cout<<"Invalid code sequence"<<endl;
                    break;
                case 2:
                    cout<<"Maze is not closed"<<endl;
                    Print();
                    cout<<endl;
                    break;
                }

                delete[] pack;
            }
        }
    }

    return 0;
}
Re[8]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 07:20
Оценка:
P.S. Вот кой-какие результаты:

1: 1
2: 2
3: 6
4: 23
5: 95
6: 420
7: 1920
8: 9047
9: 43462
10: 212203
11: 1049053
12: 5239622

P.P.S. Я то знаю, у Пушкина прога с минуты на минуту для N=50 лабиринты выдаст.
Re[7]: Робот не мой, а государственный
От: RS Земля ICQ: 148844272
Дата: 31.03.03 07:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

хъ

PolyminoLab — это сильно!

P>Вот так оно перебрало все лабиринты площадью 4. Площади 5 и 6 я ручками проверил, тоже вроде всё верно. Дальше надеюсь тоже не врёт. Считает довольно шустро.


А вот у меня на Атлоне 800 для N=12 считала час.

P>Ниже код, вполне готовый к компиляции. Основная идея не сильно изменилась — волновое распространение. Начинаем с верхней-левой клетки. В неё можно поставить трёх разных "ёжиков" — только_направо, только_вниз, направо_и_вниз. Пробуем поставить каждого и пораспространяться с этого обрывка. И так далее. Каждый раз, ставя ёжика, смотрим, куда он ОБЯЗАН торчать, а куда ПО ЖЕЛАНИЮ. Все желания реализуем по очереди. Основная проблема — перебрать быстро и уникально — для этого, как обычно, организуем fifo.


Можно четвертого — лысого. Но это для лабиринта из одной клетки.

P>Кодирующая последовательность мне здесь совсем не нужна — перебираю сразу раскодированные лабиринты. Но для понимания того, что происходит, могу описать. Каждый лабиринт кодируется линейкой полубайт — по одному на каждую занятую клетку. В каждом полубайте лежат 4 бита — наличие выходов из этой клетки во все 4 стороны. Они зависимы — каждая стенка по сути помечается дважды, поэтому кодировка явно не плотнейшая, но нам по фигу. Последовательность полубайт в линейке определяется распространением от верхней левой клетки — куда раньше пришли, та клетка раньше и описывает в линейке свои выходы.


У меня трех битов хватает — раз прошли в клетку, значит позади нас стенки нету.

P>Всё, на вопросы по коду готов ответить.

P>RS, как твой робот вылезет из площади 4, напиши, интересно.

Самому интересно, я еще не смотрел. В среду че-нить принесу.
А пока для 2x3 27, для 2x3&3x2 33, для 3x3 140.
Re[9]: С твоего робота пиво :)
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 07:38
Оценка:
Здравствуйте, RS, Вы писали:

RS>P.S. Вот кой-какие результаты:


RS>1: 1

RS>2: 2
RS>3: 6
RS>4: 23
RS>5: 95
RS>6: 420
RS>7: 1920
RS>8: 9047
RS>9: 43462
RS>10: 212203
RS>11: 1049053
RS>12: 5239622

RS>P.P.S. Я то знаю, у Пушкина прога с минуты на минуту для N=50 лабиринты выдаст.


У меня за минуту Celeron 1200 посчитал N=13.

Но хуже другое — начиная с N=8 у нас с тобой результаты расходятся!!! У меня 9049.
Как проверить, кто прав, не знаю. Ау, MichaelP, где твои любимые сайты?
Возможно N=8 выделно тем, что это первая площадь, где возможна честная петля.
Re[8]: Робот не мой, а государственный
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 07:47
Оценка:
Здравствуйте, RS, Вы писали:

RS>Можно четвертого — лысого. Но это для лабиринта из одной клетки.


Лысых не учитываем

RS>У меня трех битов хватает — раз прошли в клетку, значит позади нас стенки нету.


Думаю, если поставить такую задачу, то можно и ещё зажать. КАЖДАЯ ВНУТРЕННЯЯ стенка может быть учтена лишь один раз.

RS>А пока для 2x3 27, для 2x3&3x2 33, для 3x3 140.


Мне кстати не очевидно, как ты генеришь стенки для скажем 3х3.
Надо же, чтоб односвязным получилось.
Неужели просто генеришь все варианты стенок и проверяешь, зальётся ли?
Может есть какой особый алгоритм быстрого перебора для прямоугольных лабиринтов?
Кстати задача:

Сколько стенок можно поставить в кваднате NxN так, чтобы он остался односвязным?

Re[10]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 07:51
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Но хуже другое — начиная с N=8 у нас с тобой результаты расходятся!!! У меня 9049.

P>Как проверить, кто прав, не знаю. Ау, MichaelP, где твои любимые сайты?
P>Возможно N=8 выделно тем, что это первая площадь, где возможна честная петля.

Ну тут три варианта:
1. У тебя есть одинаковые — проверь (само изображение).
2. У меня чего-то не хватает (а вот тут хрен проверишь — 9 килолабиринтов — сдохнуть можно).
3. Сочетание (1) и (2).
Re[9]: Робот не мой, а государственный
От: RS Земля ICQ: 148844272
Дата: 31.03.03 07:57
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Лысых не учитываем


Вообще лысых — конечно. Но если не четыре бита, а три — то вполне будут лысые (то, через что пришли — не иголка, а что-то еще).

P>Думаю, если поставить такую задачу, то можно и ещё зажать. КАЖДАЯ ВНУТРЕННЯЯ стенка может быть учтена лишь один раз.


Более того — у меня не стабильно три бита, а от 0 до трех. Смотри код. То есть, если решили, что тут стенка есть, а тут ее нет, то в обоих случаях, оказавшись в соседних клетках, эти стенки уже не рассматриваем, и биты на них не отводим.

P>Мне кстати не очевидно, как ты генеришь стенки для скажем 3х3.

P>Надо же, чтоб односвязным получилось.
P>Неужели просто генеришь все варианты стенок и проверяешь, зальётся ли?

Мне очень стыдно, но до позавчера я именно так и делал

P>Может есть какой особый алгоритм быстрого перебора для прямоугольных лабиринтов?


Может и есть.

P>Кстати задача:

P>

P>Сколько стенок можно поставить в кваднате NxN так, чтобы он остался односвязным?


Для 3х3 внутренних стенок максимум 4 (из 12).
Re[11]: С твоего робота пиво :)
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 09:31
Оценка:
Здравствуйте, RS, Вы писали:

RS>Ну тут три варианта:

RS>1. У тебя есть одинаковые — проверь (само изображение).

Хорошо, проверю. Не изображение, конечно
Множество поюзаю эстээльное...

RS>2. У меня чего-то не хватает


Очень надеюсь
Re[12]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 09:41
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Хорошо, проверю. Не изображение, конечно

P>Множество поюзаю эстээльное...

Ну конечно не изображение, но и не его представление в виде кодирующей последовательности.

RS>>2. У меня чего-то не хватает


P>Очень надеюсь


Если у меня не хватает, я бы попросил тебя прислать мне на мыло все твои 9 килолабиринтов в некотором общем для нас формате, и я тогда буду сравнивать.
Готов начать обсуждение формата. Но ты сперва у себя дупликаты поищи, это все-таки проще (для меня, во всяком случае).

P.S. Что-то мне подсказывает (лень, скорее всего), что у меня все правильно.
Re[13]: С твоего робота пиво :)
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 10:06
Оценка:
Здравствуйте, RS, Вы писали:

RS>Ну конечно не изображение, но и не его представление в виде кодирующей последовательности.

RS>Если у меня не хватает, я бы попросил тебя прислать мне на мыло все твои 9 килолабиринтов в некотором общем для нас формате, и я тогда буду сравнивать.
RS>Готов начать обсуждение формата. Но ты сперва у себя дупликаты поищи, это все-таки проще (для меня, во всяком случае).

OK, но не факт что сегодня...
Re[14]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 10:13
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>OK, но не факт что сегодня...


Ну я и сам попробую, сорец-то твой есть.
Но что-то мне не нравится идея, что у тебя у стенок нет неопределенного состояния. Эдак, не поставив стенку один раз, мы можем поставить ее, подойдя к ней с другой стороны. И тогда две разные кодирующие последовательности опишут один, по сути, лабиринт.
Поправь (сегодня), если я чего не понял.
Re[15]: С твоего робота пиво :)
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 10:23
Оценка:
Здравствуйте, RS, Вы писали:

RS>Здравствуйте, Pushkin, Вы писали:


P>>OK, но не факт что сегодня...


RS>Ну я и сам попробую, сорец-то твой есть.

RS>Но что-то мне не нравится идея, что у тебя у стенок нет неопределенного состояния. Эдак, не поставив стенку один раз, мы можем поставить ее, подойдя к ней с другой стороны. И тогда две разные кодирующие последовательности опишут один, по сути, лабиринт.
RS>Поправь (сегодня), если я чего не понял.

Поместив ёжика куда-то, мы поместили его всего, такого, какой он есть, со всеми его иголками и мягкими боками. Всякий другой ёжик перед тем как сесть в другую клетку исследует соседей. Если от соседа торчит иголка, то и он пускает. А если там мягко, то не пускает. В те же стороны, где нет соседей, ёжик пускает иголки по желанию, т.е. и так и так.

Иными словами у моих кодирующих последовательностей есть жёсткое свойство — всякая внутренняя стенка или отсутствие внутренней стенки описано ровно дважды , причём одинаково.

А неопределённые состояния у меня есть только для клеток.
Re[16]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 10:33
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Поместив ёжика куда-то, мы поместили его всего, такого, какой он есть, со всеми его иголками и мягкими боками. Всякий другой ёжик перед тем как сесть в другую клетку исследует соседей. Если от соседа торчит иголка, то и он пускает. А если там мягко, то не пускает. В те же стороны, где нет соседей, ёжик пускает иголки по желанию, т.е. и так и так.


P>Иными словами у моих кодирующих последовательностей есть жёсткое свойство — всякая внутренняя стенка или отсутствие внутренней стенки описано ровно дважды , причём одинаково.


P>А неопределённые состояния у меня есть только для клеток.


Да, все вроде правильно. И не придраться.

А вот как у меня (может найдешь ошибку?).
У стенок есть три состояния — стенка, проход, неопределено. Когда ставим ежика, его иголки и мягкие бока направляем только в стороны неопределенных стенок. Новый ежик добавляется в фифо, скажем, в начало. Развитие (гду будет следующий ежик) определяется последним ежиком из фифо, чей проход открыт в свободную клетку.

Похоже, все тоже самое, но у тебя попроще (и явно быстрее).
Re[17]: С твоего робота пиво :)
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 11:03
Оценка:
Здравствуйте, RS, Вы писали:

RS>А вот как у меня (может найдешь ошибку?).

RS>У стенок есть три состояния — стенка, проход, неопределено.

Я сначала тоже на эту тему колдовал, но потом почему-то бросил, не выходило... Попробую поглядеть твой код на досуге, сейчас надо хоть что-то по работе сделать

Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...
Re[18]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 11:11
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...


Исключено. Тогда бы у меня больше насчиталось. А до использования рекурсии я пока не дошел.
Re[18]: С твоего робота пиво :)
От: RS Земля ICQ: 148844272
Дата: 31.03.03 11:18
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...


А эта неестественная "примочка" тебя не раздражает? Я пока до ее смысла не дошел, ибо не читал код. Может из-за нее у тебя насчитываются лишние?
Re[19]: С твоего робота пиво :)
От: Pushkin Россия www.linkbit.com
Дата: 31.03.03 11:27
Оценка:
Здравствуйте, RS, Вы писали:

P>>Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...


RS>А эта неестественная "примочка" тебя не раздражает? Я пока до ее смысла не дошел, ибо не читал код. Может из-за нее у тебя насчитываются лишние?


Всё может быть, вскрытие покажет
На самом деле она не такая уж неестественная, я к ней спокойно отношусь. Просто в процессе подсчёта объективно есть 4 типа клеток:

0    - ежа нету и быть не может (вверху)
-1   - фиг его знает, есть ли там ёжик
-2   - ёжик точно есть (т.к. другие ёжики пальцем показали), но неясно какой, надо ещё проверить
1-15 - стоит вполне определённый ёжик
Re[20]: Пиво
От: RS Земля ICQ: 148844272
Дата: 02.04.03 07:58
Оценка:
Прав был Пушкин, а я не прав.

Но!
Ошибка у меня была не в Decode, а в Enum, и вот какая она была:
Enum у меня работает так же, как в первой версии проги Пушкина, которая полимино считала.
Смотрим:
13665040 — Decode говорит, что она плохая,
13665100 — и эта тоже плохая.
И дальше Enum проверяет 13666000 (так уж Enum устроен), и пропускает 13665213. Точно так же была пропущена и еще одна, опять таки по вине Enum.
Итого из 8 клеток 9049 лабиринтов.

Теперь про робота.
По лабиринтам из трех клеток одна последовательность из 9-ти команд (и 7 ее поворотов и отражений):
DRDURLUDL

А вот для четырех клеток я пока не порверил. Просто из-за лени я начал полным последовательным перебором — и пока не добрался. Но в последовательности больше 15-ти команд, это уже точно известно.
Re[21]: Пиво
От: Pushkin Россия www.linkbit.com
Дата: 02.04.03 08:16
Оценка:
Здравствуйте, RS, Вы писали:

RS>Прав был Пушкин, а я не прав.


Прости

RS>И дальше Enum проверяет 13666000 (так уж Enum устроен), и пропускает 13665213. Точно так же была пропущена и еще одна, опять таки по вине Enum.


Мне вообще всегда чудом казалось, что сложные алгоритмы работают

RS>А вот для четырех клеток я пока не порверил. Просто из-за лени я начал полным последовательным перебором — и пока не добрался. Но в последовательности больше 15-ти команд, это уже точно известно.


Ну, это и я да 18 дошёл.
Имхо полный перебор ценнее.
Если его удаётся провести быстро.
Но поиски вширь и вглубь тоже очень интересны.
Как говорится, "не можешь как надо — сделай как можешь"
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.