Решение проблемы упаковки площади для отдыха

Мне было предложено найти сетку 11x11, содержащую цифры, так что можно прочитать квадраты 1,..., 100. Здесь чтение означает, что вы фиксируете начальное положение и направление (8 возможностей), и если вы можете найти, например, цифры 1,0,0,0,0,4 последовательно, вы нашли квадраты 1, 2, 10, 100 и 20. Я сделал программу (алгоритм не мой. Я немного изменил программу, которая использует лучший поиск для поиска решения, но он слишком медленный. Кто-нибудь знает лучший алгоритм для решения проблемы?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <vector>
#include <algorithm>

using namespace std;
int val[21][21];//number which is present on position
int vnum[21][21];//number of times the position is used - useful if you want to     backtrack

//5 unit borders
int mx[4]={-1,0,1,0};//movement arrays
int my[4]={0,-1,0,1};

int check(int x,int y,int v,int m)//check if you can place number - if you can, return    number of overlaps

{
int c=1;
while(v)//extract digits one by one
{
    if(vnum[x][y] && (v%10)!=val[x][y])
        return 0;
    if(vnum[x][y])
        c++;
    v/=10;
    x+=mx[m];
    y+=my[m];
}
return c;
} 

void apply(int x,int y,int v,int m)//place number - no sanity checks
{
while(v)//extract digits one by one
{
    val[x][y]=v%10;
    vnum[x][y]++;
    v/=10;
    x+=mx[m];
    y+=my[m];
}
}

void deapply(int x,int y,int v,int m)//remove number - no sanity checks
{
while(v)
{
    vnum[x][y]--;
    v/=10;
    x+=mx[m];
    y+=my[m];
}
}

int best=100;
void recur(int num)//go down a semi-random path
{
if(num<best)
{
    best=num;
        if(best)
        printf("FAILED AT %d\n",best);
    else
        printf("SUCCESS\n");
    for(int x=5;x<16;x++)           // 16 and 16
    {
        for(int y=5;y<16;y++)
        {
            if(vnum[x][y]==0)
                putchar('.');
            else
                putchar(val[x][y]+'0');
        }
        putchar('\n');
    }
    fflush(stdout);
}
if(num==0)
    return;
int s=num*num,t;
vector<int> poss;
for(int x=5;x<16;x++)
    for(int y=5;y<16;y++)
        for(int m=0;m<4;m++)
            if(t=check(x,y,s,m))
                poss.push_back((x)|(y<<8)|(m<<16)|(t<<24));//compress four numbers into an int
if(poss.size()==0)
    return;

sort(poss.begin(),poss.end());//essentially sorting by t
t=poss.size()-1;
while(t>=0 && (poss[t]>>24)==(poss.back()>>24))
    t--;
t++;

//t is now equal to the smallest index which has the maximal overlap
t=poss[rand()%(poss.size()-t)+t];//select random index>=t
apply(t%256,(t>>8)%256,s,(t>>16)%256);//extract random number
recur(num-1);//continue down path
}

int main()
{   
srand((unsigned)time(0));//seed
while(true)
{
    for(int i=0;i<21;i++)//reset board
    {
        memset(val[i],-1,21*sizeof(int));
        memset(vnum[i],-1,21*sizeof(int));
    }
    for(int i=5;i<16;i++)
    {
        memset(val[i]+5,0,11*sizeof(int));
        memset(vnum[i]+5,0,11*sizeof(int));
    }
    recur(100);
}
}

Ответы

Ответ 1

У вас есть 100 номеров и 121 ячеек для работы, поэтому вам нужно быть очень эффективным. Мы должны попытаться создать сетку, чтобы каждый раз, когда мы заполняем ячейку, мы получаем новое число в нашем списке.

В настоящее время позвольте беспокоиться только о 68 четырехзначных числах. Я думаю, что хороший кусок более коротких номеров будет в нашей сетке без каких-либо усилий.

Начните с набора чисел 3x3 или 4x4 в левом верхнем углу вашей сетки. Он может быть произвольным или тонко настраиваться для получения немного лучших результатов. Теперь позвольте заполнить остальную часть сетки по одному квадрату за раз.

Повторите следующие шаги:

  • Заполните пустую ячейку цифрой
  • Проверьте, какие номера выбили из списка
  • Если он не сбил никаких 4-значных чисел, попробуйте другую цифру или ячейку

В конце концов вам может понадобиться заполнить 2 ячейки или даже 3 ячейки, чтобы получить новое 4-значное число, но это должно быть необычным, кроме как в конце (в этот момент, надеюсь, там много пустого пространства). Продолжите процесс для оставшихся трехзначных чисел (несколько?).

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

Update

Я пробовал свой подход и получил только 87 из 100:

10894688943
60213136008
56252211674
61444925224
59409675697
02180334817
73260193640
.5476685202
0052034645.
...4.948156
......4671.

Ответ 2

Используя случайный поиск, я добрался до 92 квадратов с одним неиспользованным пятном (8 недостающих чисел: 5041 9025 289 10000 4356 8464 3364 3249)

1 5 2 1 2 9 7 5 6 9 5 
6 1 0 8 9 3 8 4 4 1 2 
9 7 2 2 5 0 0 4 8 8 2 
1 6 5 9 6 0 4 4 7 7 4 
4 4 2 7 6 1 2 9 0 2 2 
2 9 6 1 7 8 4 4 0 9 3 
6 5 5 3 2 6 0 1 4 0 6 
4 7 6 1 8 1 1 8 2 8 1 
8 0 1 3 4 8 1 5 3 2 9 
0 5 9 6 9 8 8 6 7 4 5 
6 6 2 9   1 7 3 9 6 9

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

Код вообще не оптимизирован и способен декодировать несколько сотен решений в секунду. Текущее решение найдено после попыток 196k.

UPDATE

Лучшим решением с таким подходом является 93 без свободных отверстий (7 недостающих номеров: 676 7225 3481 10000 3364 7744 5776):

9 6 0 4 8 1 0 0 9 3 6 
6 4 0 0 2 2 5 6 8 8 9 
1 7 2 9 4 1 5 4 7 6 3 
5 8 2 3 8 6 4 9 6 5 7 
2 4 4 4 1 8 2 8 2 7 2 
1 0 8 9 9 1 3 4 4 9 1 
2 1 2 9 6 1 0 6 2 4 1 
2 3 5 5 3 9 9 4 0 9 6 
5 0 0 6 1 0 3 5 2 0 3 
2 7 0 4 2 2 5 2 8 0 9 
9 8 2 2 6 5 3 4 7 6 1

Это решение (все 100 номеров размещены), однако с использованием сетки 12x12 (MUCH easy)

9 4 6 8 7 7 4 4 5 5 1 7
8 3 0 5 5 9 2 9 6 7 6 4
4 4 8 3 6 2 6 0 1 7 8 4
4 8 4 2 9 1 4 0 5 6 1 4
9 1 6 9 4 8 1 5 4 2 0 1
9 4 4 7 2 2 5 2 2 5 0 0
4 6 2 2 5 8 4 2 7 4 0 2
0 3 3 3 6 4 0 0 6 3 0 9
9 8 0 1 2 1 7 9 5 5 9 1
6 8 4 2 3 5 2 6 3 2 0 6
9 9 8 2 5 2 9 9 4 2 2 7
1 1 5 6 6 1 9 3 6 1 5 4

Он был найден с использованием по-настоящему "грубой силы" подхода, начиная с случайной матрицы и сохраняя случайное изменение цифр, когда это улучшило охват. Это решение было найдено с помощью высокоразвитой С++-программы, автоматически генерируемой Python script.

Обновление 2

Используя инкрементный подход (т.е. сохраняя более сложную структуру данных, чтобы при изменении матричного элемента число охваченных целей можно было обновить, а не пересчитывать), я получил гораздо более быстрый поиск (около 15 тыс. матриц в секунду, исследованных с помощью Python реализация выполняется с PyPy).

Через несколько минут эта версия смогла найти 99-квази-решение (число все еще отсутствует):

7 0 5 6 5 1 1 5 7 1 6
4 6 3 3 9 8 8 6 7 6 1
3 9 0 8 2 6 1 1 4 7 8
1 1 0 8 9 9 0 0 4 4 6
3 4 9 0 4 9 0 4 6 7 1
6 4 4 6 8 6 3 2 5 2 9
9 7 8 4 1 1 4 0 5 4 2
6 2 4 1 5 2 2 1 2 9 7
9 8 2 5 2 2 7 3 6 5 0
3 1 2 5 0 0 6 3 0 5 4
7 5 6 9 2 1 6 5 3 4 6

ОБНОВЛЕНИЕ 3

Ok. Через некоторое время (не знаю, сколько) одна и та же программа Python действительно нашла полное решение (несколько действительно)... вот один

6 4 6 9 4 1 2 9 7 3 6
9 2 7 7 4 4 8 1 2 1 7
1 0 6 2 7 0 4 4 8 3 4
2 1 2 2 5 5 9 2 9 6 5
9 2 5 5 2 0 2 6 3 9 1
1 6 3 6 0 0 9 3 7 0 6
6 0 0 4 9 0 1 6 0 0 4
9 8 4 4 8 0 1 4 5 2 3
2 4 8 2 8 1 6 8 6 7 5
1 7 6 9 2 4 5 4 2 7 6
6 6 3 8 8 5 6 1 5 2 1

Поиск программы можно найти здесь...

Ответ 3

Я предполагаю, что оба алгоритма слишком медленные. Некоторые алгоритмы оптимизации могут работать как лучший поиск или имитированный отжиг, но у меня нет большого опыта в программировании.

Ответ 4

Пробовали ли вы какие-либо первичные исследования алгоритмов двумерной бинарной упаковки (2DBP)? Google Scholars - хорошее начало. Я сделал это некоторое время назад при создании приложения для создания мозаик.

Все алгоритмы упаковки прямоугольных бинов можно разделить на 4 группы на основе их поддержки следующих ограничений:

  • Должен ли полученный бит быть гильотиной? То есть вам нужно позже нарезать корзину (-ы) пополам, пока все части не будут распакованы?
  • Можно ли поворачивать куски, чтобы поместиться в корзину? Не проблема с квадратными частями, поэтому это делает больше алгоритмов доступными для вас.

Из всех рассмотренных нами алгоритмов наиболее эффективным решением является алгоритм альтернативных направлений (AD) с уровнем оптимизации поиска в Tabu. Имеются диссертации, подтверждающие это. Возможно, я смогу выкопать некоторые ссылки, если это поможет.

Ответ 5

Некоторые идеи с моей головы, не вкладывая много времени в размышления о деталях.

Я бы начал с подсчета числа вхождений каждой цифры во всех квадратах 1..100. Общее число цифр будет явно больше 121, но, анализируя отдельные частоты, вы можете вывести, какие цифры должны быть сгруппированы по одной строке, чтобы сформировать как можно больше различных квадратов. Например, если 0 имеет самую высокую частоту, вы должны попытаться поместить столько квадратов, содержащих 0 в одной строке.

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

Итак, программа по-прежнему будет грубой силой, но она значительно улучшит структуру проблемы.

PS: Частоты счетных цифр - самый простой способ решить, является ли определенная перестановка цифр квадратом.