Решение развлекательной квадратной задачи упаковки

Question

Меня попросили найти сетку 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);
}
}

Answer 1

Используя случайный поиск, я получил только 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!), А затем помещает каждое число в «верхнюю» правовую позицию. Значение решения измеряется как сумма квадратов длин помещенных чисел (чтобы придать большее значение длинным числам) и количеству оставшихся «дырок» (увеличение количества отверстий в ИМО должно повысить вероятность того, что другое число будет вписывается).

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

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 (НАМНОГО проще)

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

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

Обновление 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

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

Answer 2

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

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

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

Повторите эти шаги:

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

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

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

---

Обновление

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

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

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

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

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