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 лабиринты выдаст.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.