Алгоритмическая задача о красках.

man «Задача о раскраске карты» :)

...

Вообще-то, 4-х красок достаточно, чтобы раскрасить любую плоскую конфигурацию.

http://ru.wikipedia.org/wiki/Проблема_четырёх_красок

> Вообще-то, 4-х красок достаточно, чтобы раскрасить любую плоскую конфигурацию.

Задаче не в доказательстве существования решения. А в нахождении рандомного решения.

> Но давольно много мегабайтов такой файл занимает, даже если отсеч одинаковые (через поворот, а точнее 5 поворотов) комбинации.

1. отсечь отражения х/=2

2. отсечь перестановки красок abc х/=6

3. отсечь перестановки красок de х/=2

или, альтернативно, забить на мегабайты.

> 1. отсечь отражения ... или, альтернативно, забить на мегабайты.

Файл все равно получается достаточно большой относительно решаемой задачи. В любом случае этим вариантом я пользовался давно порядка 6-8 лет назад. Все повороты были отброшены, файл ЕМНИП занимал более 50МБ.

> 1. отсечь отражения х/=2

поворотов может быть всего 6 (включая оригинал). x/=6

> 2. отсечь перестановки красок abc х/=6

а вот тут наоборот x/=4

abc, bac, cba, acb - всего 4 перестановки.

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

>Задаче не в доказательстве существования решения. А в нахождении рандомного решения.

Так в классическом решении задачи что тебе не нравится? Решение-то примитивное и не одну сотню лет известное. Это доказать его смогли лишь недавно.

Берёшь любую клетку (в твоём случае - ту, что уже предварительно окрашена) и закрашиваешь соседей, чередуя два цвета. Если число соседей нечётное, то во избежание совмещения цветов используется третий цвет. Всё :)

А рандомно выбирать можно из какого-то множества решений или именно из всех?

А что если взять какое-то одно решение. Например такое: по внешнему периметру acabcbacabcb, по внутреннему (вокруг центра) - dedede (лично мне проще на это смотреть как на граф: в центры шестиугольников нарисовать вершины, и соеденить их соответственно тому как они соприкасаются друг с другом; тогда на концах любого ребра графа не должно быть одинаковых значений). К решению затем применять какие-то случайные трансформации, которые бы генерировали другие конфигурации. Правда тебе надо доказать, что существует последовательность трансформаций, такая, что применив её, ты можешь получить любую конфигурацию из множества допустимых конфигураций. Или более общно: для любых двух конфигураций из множества решений существует последовательность трансформаций, превращающая одну в другую. Или доказать обратное и искать другое вариант решения задачи. :-)

> поворотов может быть всего 6 (включая оригинал). x/=6

Отражение *не может* быть заменено поворотом, если у тебя не все решения зеркально симметричные.

> abc, bac, cba, acb - всего 4 перестановки.

Чувак, ты похоже совсем не в теме. Перестановок 6=3! abc acb bac bca cab cba

Вывод: юзай 50МВ файл.

А решение то простое:

нумеруешь клетки слева напрво и сверху вниз:

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

Легко доказать, что если первые n клеток раскрашены так, что удовлетворяют требованию соседства, то и n+1 - ую тоже можно так раскрасить.
Вот и раскрашивай их в таком порядке. Сперва первую в случайный цвет. 
Потом вторую из оставшихся. Потом 3-ю, 4-ю. Потом 5-ую случайно одним из цветов не совпадающих с 4, 1, 2. Потом 6-ую. итд...

Так гарантировано можно получить любую из допустимых раскрасок. 
Хотя гарантировать равномерное распределение не берусь, но все-же.

Следуя твоему алгоритму, получаю:

  a d e
 b c a b
a d   c d
 b c e b
  a 

осталось е и с, которые некуда вставить.

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

1. Грамматика ни к чёрту. Тебя трудно воспринимать всерьёз.

2. Пойми в чём отличие грани от угла.

2. Геометрия задачи слишком специфична, чтобы искать красивое решение. Хотя стремление к лаконичности похвально и приветствуется.

4. Не знаю, чего тебе советуют в коментах, но перестановок красок 5!. И упрощение идет изменением алгоритма перебора во вложенных циклах, стартуя индексную переменную со значения, не меньшего текущего значения индексной переменной внешнего цикла. Лишь потом на полученные решения для 5 красок накладывается маска-условие того что три краски по 4, а две — по 3.

5. Ускорить алгоритм перебора можно, введя матрицу связности для графа карты и обходя в лоб уже её. Заодно решится более общая задача раскрашивания произвольной карты заданным числом красок.

Вердикт: школотоподобный неуч, приобщающийся к Истине. Что ж, успехов.

> > abc, bac, cba, acb - всего 4 перестановки.

> Чувак, ты похоже совсем не в теме. Перестановок 6=3! abc acb bac bca cab cba

Да, извиняюсь. Что-то меня переклинило, про остальные 2 подстановки. Видимо мозг уже не работал, когда писал (у нас уже ночь была). Но тем не менее - это не желаемое решение.

> > поворотов может быть всего 6 (включая оригинал). x/=6

> Отражение *не может* быть заменено поворотом, если у тебя не все решения зеркально симметричные.

шесть поворотов по 30 градусов, в силу специфики фигуры. Что я не так понял?

> Waterlaz (*) (19.07.2009 23:14:13)

Такой вариант рассматривался. Он не гарантирует успешного нахождения решения. Хотя если луна будет в нужной фазе - то получим рандомное решение.

> 1. Грамматика ни к чёрту. Тебя трудно воспринимать всерьёз.

Да ну? Другие что-то не жалуются.

> 2. Пойми в чём отличие грани от угла.

Отличие прекрасно понимаю. А ты знаешь что количество углов равно количеству сторон (граней) ?

> 2. Геометрия задачи слишком специфична, чтобы искать красивое решение. Хотя стремление к лаконичности похвально и приветствуется.

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

> 4. Не знаю, чего тебе советуют в коментах, но перестановок красок 5!. И упрощение идет изменением алгоритма перебора во вложенных циклах, стартуя индексную переменную со значения, не меньшего текущего значения индексной переменной внешнего цикла. Лишь потом на полученные решения для 5 красок накладывается маска-условие того что три краски по 4, а две — по 3.

Единственное дельное замечание из твоего комментария. Но есть одно "но": самым большим тормозом будет как-раз проверка на валидность решения. А этим ты еще и уменьшаешь вероятность получения правильного решения. Может получиться так, что какой-то краски будет использовано 6 штук, или что 5ая краска задействована не будет вообще. Что в принципе математически допустимо. Читай первые комментарии KRoN73.

Диагноз: ЧСВ не позволяет нормально жить.

>>Есть поле, состоящее из 19 шестигранников, распологающихся в след форме:

>шестигранников

>>Да ну? Другие что-то не жалуются.

Ты что, носом быть тыкуемым приучен?

->Сколько не продумывал

->давольно

->отсеч

>>сторон (граней) ?

Epic doublefacepalmfail.

>>Но есть одно "но": самым большим тормозом будет как-раз проверка на валидность решения.

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

Экспертное заключение: irq упорот и борз больше достаточного для ментального прогресса.

>>Диагноз: ЧСВ не позволяет нормально жить.

Это у тебя возрастное. Пройдет.

а что, если изменить алгоритм Waterlaz'а таким образом, что если законичились краски -- возвращаемся на n шагов назад, перекрашиваем. если красок опять не хватило -- возвращаемся на n + 1 и т.д.

>>а что, если изменить алгоритм Waterlaz'а таким образом, что если законичились краски -- возвращаемся на n шагов назад, перекрашиваем. если красок опять не хватило -- возвращаемся на n + 1 и т.д.

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

> Ты что, носом быть тыкуемым приучен?

>->Сколько не продумывал

>->давольно

>->отсеч

>>>сторон (граней) ?

>Epic doublefacepalmfail.

Что я не нашел в этой части комментария никаких поинтеров на грамматические или лексические ошибки. Не конструктивно стоять на своем - это твой метод ведения диалога когда ты не знаешь что сказать? Либо давай точные ссылки где ошибка, либо засчитываю слив.

man _правила_русского_языка_

> Вранье. Осилив сказанное в пятом пункте, ты бы знал что решения будут браться из правильной таблицы связности и тем самым вопрос о валидности граничной раскраски не встает. Валидность состава красок легче наложить на найденные решения, нежели алгоритм прогона перековывать под эту валидность. И метод закраски соседей, как советуют в коментах, ничуть не предсказуемее в плане наткнуться на валидное по составу красок решение, нежели указанный мной. Хотя без цифр это предварительная оценка.

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

> Экспертное заключение: irq упорот и борз больше достаточного для ментального прогресса. Это у тебя возрастное. Пройдет.

Батенька, Фрейд про таких как ты много говорил. Ты бы прислушался.

А вообще лучше бы что-то по делу предложил, чем приближено кубировать сферических коней в вакууме.

   a b a
  b c d b
 a d x a c
  e b c e
   c e d

я правильно понял условие?

> я правильно понял условие? a b a b c d b a d x a c e b c e c e d

правильно

> правильно

задача ещё актуальна? рекурсивный алгоритм подойдёт?

да актуально. С радостью выслушаю.

из меня плохой сказочник =) так что просто приведу пример решения
(на перле; надеюсь, проблем с пониманием кода не возникнет):

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
#!/usr/bin/perl

use strict;
use warnings 'all';

my @colors = qw(a b c d e);
my @count = (4, 4, 4, 3, 3);

my @rel = ([], [0], [1], [0], [0,1,3], [1,2,4], [2,5], [3], [3,4,7], [], [5,6], [6,10],
           [7,8], [8,12], [10,13], [10,11,14], [12,13], [13,14,16], [14,15,17]);

my @cells = ('x') x 19;

sub iterate {
    my $cell = shift || 0;
    if ($cell == 19) {
        printf "%4s%2s%2s\n%3s%2s%2s%2s\n%2s%2s%2s%2s%2s\n%3s%2s%2s%2s\n%4s%2s%2s\n\n",
               @cells[0..2], @cells[3..6], @cells[7..11], @cells[12..15], @cells[16..18];
        exit;
    } elsif ($cell == 9) {
        iterate($cell + 1);
    } else {
        L:for my $i (0..$#colors) {
            next unless $count[$i];
            $cells[$cell] = $colors[$i];
            do { next L if $cells[$_] eq $cells[$cell] } for @{$rel[$cell]};
            --$count[$i];
            iterate($cell + 1);
            ++$count[$i];
        }
    }
}

iterate;

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

можно спрашивать :)

> можно спрашивать :)

в перле не силен, спрашиваю =)

без комментариев разобраться тяжело какой алгоритм. И так как все-таки в перле не силен, уточню: функция iterate ищет первое правильное решение или все-таки случайное.

> Файл все равно получается достаточно большой относительно решаемой задачи. В любом случае этим вариантом я пользовался давно порядка 6-8 лет назад. Все повороты были отброшены, файл ЕМНИП занимал более 50МБ.

Я не стал отбрасывать повороты и отражения, а отбросил только перестановки цветов (группы a-b-c и d-e). Получилось 784565 разных раскрасок. Каждая из них легко кодируется 18-ти разрядным числом в 5-ричной системе счисления, то есть 6-ю байтами. Размер бинарного массива будет 5*784565 байт, то есть менее 5 МБ. Ня?

=============================

Запуск на Core2 занял около 20 минут.

#include <algorithm>
#include <string>
#include <iostream>

class Coloring
{
	char c[18];

//			0		1		2
//		3		4		5		6
//	7		8				9		10
//		11		12		13		14
//			15		16		17

public:

	void Reset()
	{
		c[ 0] = 'a';
		c[ 1] = 'a';
		c[ 2] = 'a';
		c[ 3] = 'a';
		c[ 4] = 'b';
		c[ 5] = 'b';
		c[ 6] = 'b';
		c[ 7] = 'b';
		c[ 8] = 'c';
		c[ 9] = 'c';
		c[10] = 'c';
		c[11] = 'c';
		c[12] = 'd';
		c[13] = 'd';
		c[14] = 'd';
		c[15] = 'e';
		c[16] = 'e';
		c[17] = 'e';
	}

	bool Next()
	{
		return std::next_permutation(c, c + sizeof(c));
	}

	bool IsMonotoneABC() const
	{
		char max = 'a' - 1;
		for(int i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'a' || x == 'b' || x == 'c')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsMonotoneDE() const
	{
		char max = 'd' - 1;
		for(int i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'd' || x == 'e')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsGood() const
	{
		return
			c[ 0] != c[ 1] && c[ 0] != c[ 3] && c[ 0] != c[ 4] &&
			c[ 1] != c[ 2] && c[ 1] != c[ 4] && c[ 1] != c[ 5] &&
			c[ 2] != c[ 5] && c[ 2] != c[ 6] &&
			c[ 3] != c[ 4] && c[ 3] != c[ 7] && c[ 3] != c[ 8] &&
			c[ 4] != c[ 5] && c[ 4] != c[ 8] &&
			c[ 5] != c[ 6] && c[ 5] != c[ 9] &&
			c[ 6] != c[ 9] && c[ 6] != c[10] &&
			c[ 7] != c[ 8] && c[ 7] != c[11] &&
			c[ 8] != c[11] && c[ 8] != c[12] &&
			c[ 9] != c[10] && c[ 9] != c[13] && c[ 9] != c[14] &&
			c[10] != c[14] &&
			c[11] != c[12] && c[11] != c[15] &&
			c[12] != c[13] && c[12] != c[15] && c[12] != c[16] &&
			c[13] != c[14] && c[13] != c[16] && c[13] != c[17] &&
			c[14] != c[17] &&
			c[15] != c[16] &&
			c[16] != c[17];
	}

	std::string ToString() const
	{
		return std::string(c, c + sizeof(c));
	}
};

int main()
{
	Coloring c;
	c.Reset();
	while(c.Next()) if(c.IsGood()) if(c.IsMonotoneABC()) if(c.IsMonotoneDE())
	{
		std::cout << c.ToString() << std::endl;
	}
}

первое. если убрать «exit», будет искать/печатать все.

зы: могу на С дать, но он ещё сложнее ;)

s/5*784565/6*784565/

> Запуск на Core2 занял около 20 минут.

Ыыыы! Я идиот. Если собрать с -O3, запуск занимает 3 минуты.

> могу на С дать, но он ещё сложнее ;)

сложнее - не страшно, главное что понятнее будет. Но дело не в решении их может быть чуть меньше чем бесконечность. Лучше объясни твой алгоритм, если тебе не трудно. =)

> Запуск на Core2 занял около 20 минут.

Все это, конечно, хорошо. Но хочется составить алгоритм нахождения рандомного решения без записи и чтения из доп. файлов

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

int r = random() / (RAND_MAX) * SOLVE_AMOUNT;
for (int i=0; i < r; ++i)
{
 seek_solution;
 if (i == r) break; // дошли до нужного решения
}

Но хочется чего-то красивого и изящного. =)

> без комментариев разобраться тяжело какой алгоритм

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

> Но хочется чего-то красивого и изящного.

На целевой машине нет лишних 5 Мб оперативы? Если есть, то можно на этапе инициализации по алгоритму "от arsi" заполнять массив, а затем делать из него моментальную выборку. Думаю, при аккуратной имплементации его алгоритм на современном проце заполнит массив за несколько секунд.

Или хранить в исполнимом файле уже готовый массив - загрузка моментальная, но бинарник несколько распухает.

> Но хочется составить алгоритм нахождения рандомного решения без записи и чтения из доп. файлов

5 Мб не трудно запихнуть в массив на этапе компиляции.

> Думаю, при аккуратной имплементации его алгоритм на современном проце заполнит массив за несколько секунд.

irq, если хочешь, могу даже заимплементить на Си (или на C++ - мне все равно). Условие - твоя программа, использующая этот код, публикуется под GPL.

ок, вот на сях.
ищет _рандомное_ решение.

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
#include <stdio.h>                                     
#include <stdlib.h>                                    
#include <time.h>                                      

static const char colors[5] = "abcde";
static int left[5] = { 4, 4, 4, 3, 3 };
static char cells[19];                 
static const int rel[19][4] = {        
    {0}, {-1}, {-1},                   
    {-3}, {-4, -3, -1}, {-4, -3, -1}, {-4, -1},
    {-4}, {-5, -4, -1}, {0}, {-5, -4}, {-5, -1},
    {-5, -4}, {-5, -1}, {-4, -1}, {-5, -4, -1}, 
    {-4, -3}, {-4, -3, -1}, {-4, -3, -1}        
};                                              

static void randomize(char *p) {
    int n = 5, mask = 0;        
    while (n) {                 
        int v = 0, r = 1 + rand() % n--;
        for (; r; ++v)                  
            if ((mask & (1 << v)) == 0) 
                --r;                    
        *p++ = --v;                     
        mask |= 1 << v;                 
    }                                   
}                                       

static int iterate(int i) {
    int n = 5;             
    char *p = &cells[i];   
    const int *r;          
    char inx[5];           
                           
    if (i == 19) {         
        printf("  %c %c %c\n", cells[0], cells[1], cells[2]);
        printf(" %c %c %c %c\n", cells[3], cells[4], cells[5], cells[6]);
        printf("%c %c x %c %c\n", cells[7], cells[8], cells[10], cells[11]);
        printf(" %c %c %c %c\n", cells[12], cells[13], cells[14], cells[15]);
        printf("  %c %c %c\n\n", cells[16], cells[17], cells[18]);
        return 1;
    }

    if (i == 9)
        return iterate(i + 1);

    randomize(inx);
    while (n--) {
        int c = inx[n];
        int ok = 1;
        if (!left[c])
            continue;
        *p = colors[c];
        for (r = rel[i]; *r && ok; ++r)
            if (*p == p[*r])
                ok = 0;
        if (!ok)
            continue;
        --left[c];
        ok = iterate(i + 1);
        ++left[c];
        if (ok)
            return 1;
    }
    return 0;
}

int main() {
    srand(time(NULL));
    cells[9] = 'x';
    return !iterate(0);
}
-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

а по поводу объяснить… ой тяжело мне это ^_^'
посмотри на код, если не поймёшь, попробую как-нибудь объяснить =)

упс, строчку «cells[9] = 'x';» — нафиг.

> Или хранить в исполнимом файле уже готовый массив - загрузка моментальная, но бинарник несколько распухает.

Разкмеется можно, я этого не отрицаю. И считаю этот вариант одним из лучших. Но: <Немного оффтопа> В старые времена спектрумов (когда я, собственно говоря, знакомился с "умной" техникой) Очень ценолось и широко использовалась оптимизация на уровне математики, мат. модели. Если можно было генерировать данные "на лету" а не считывать их из большого файла, то выбиралось первое. Потом оптимизировался алгоритм. и в итоге все работало сравнительно быстро. Я, конечно, понимаю что: "железо сейчас быстрее...", "такая оптимизация не нужна..", и т.д. По большей части пунктов да, я согласен. Но чем плохо немного пошевелить мозгами и придумать такой алгоритм, чтобы нчего не хранить и не слишеом долго ждать. </оффтоп>

Очень интесует один вопрос, относительно рекурсивного метода:

Как понять, что дальше заполнить карту нельзя? Когда остановить рекурсию и на сколько шагов назад вернуться, если нельзя оставшимися цветами дальше заполнять карту?

> а по поводу объяснить… ой тяжело мне это ^_^' посмотри на код, если не поймёшь, попробую как-нибудь объяснить =)

Ок, посмотрю проверю, что не пойму - напишу в тред. Часиков через 12...

> Как понять, что дальше заполнить карту нельзя? Когда остановить рекурсию и на сколько шагов назад вернуться, если нельзя оставшимися цветами дальше заполнять карту?

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

> (на перле; надеюсь, проблем с пониманием кода не возникнет):

Ну, рекурсивно перебрать все возможные варианты - это наверное не совсем The Right Thing. Хотя, видимо, тут ничего лучше не придумать. Можно как вариант один раз сгенерировать дерево всех решений и затем ходить по нему рандомно.

> Можно как вариант один раз сгенерировать дерево всех решений и затем ходить по нему рандомно.

9414780 вариантов (это без отсеивания похожих) как-то тяжело представить в виде дерева ^_^'

кроме того, при таком количестве вариантов перебор будет не таким долгим. установил вот ради интереса счётчик в начало итерационной функции — количество вызовов в основном около 20…22 (при минимуме в 20), но часто доходит до 50, и редко — до 500, а ≥1000 вообще не замечал (хоть и не исключаю такую возможность). так что ничего страшного ;)

зы: при 268 вызовах: real 0m0.004s // user 0m0.000s // sys 0m0.000s ^_^

> 9414780 вариантов (это без отсеивания похожих) как-то тяжело представить в виде дерева ^_^'

Ну, это да. Хотя там должно быть много общих веток. В любом случае будет меньше файла в 50 мегабайт. :-)

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

Ну раз перебор не долог, то может и нормально.

А равномерность распределения гарантируется? Не могу сообразить...

эскиз.

#define COLOR1 0x01
#define COLOR2 0x02
#define COLOR3 0x04
#define COLOR4 0x08
#define COLOR5 0x10

n=5;
m[]={3,4,5,4,3};
shift[]={-1,-1,-1,0,0};


for(i=0;i<n;i++)
for(j=0;j<m[i];j++)
{
if(i>0)
{
jj=j+shift[i];
if(jj>0) neighbours|=m[i-1][jj]
jj=j+shift[i]+1;
if(jj>0) neighbours|=m[i-1][jj]
}
if(j>0) neighbours|=m[i][j-1]

m[i][j]=random_excluding(neighbours);
}

вопросы?

центр можно потом "продырявить". не суть важно.

for(i=0;i<n;i++)
for(j=0;j<m[i];j++)
{
+neighbours=0
if(i>0)
{