Mrrl

Если в формулировке "расставить знаки, чтобы получить 100", то у меня осталось что-то такое:
https://www.dropbox.com/s/vktq0cllod4d34s/LuckyTic...

Отсортировать в порядке убывания, потом первые два элемента положить в разные кучки, а каждый следующий - в ту из кучек, где сумма на данный момент меньше. Работать будет не всегда (например, 25,25,20,20,9,1), зато не требует перебора.

Боюсь, что количество вариантов, даже если искать минимальные, будет сравнимо с 2^80 (или, хотя бы, 2^60) - замучаетесь искать. Но если очень хочется, то можно попробовать так:
- пусть у вас есть решатель (оптимизированный до предела), который по заданному набору клеток говорит ответ - 0 решений, одно или больше одного.
Ищете перебором по дереву. Сначала про первую клетку предполагаете, открыта она или нет, потом для обоих случаев - про вторую, и т.д.
Для любого набора открытых клеток в процессе перебора есть не меньше двух решений (иначе если оно одно - мы получили вариант ответа, а нуля не бывает, мы идём от известного решения).
Когда мы решаем, открывать ли следующую клетку, делаем следующее:
1) предположим, что мы не хотим её открывать. Откроем все клетки, идущие за ней, и посмотрим, сколько у нас решений. Если два - значит эту клетку нужно открыть обязательно, если нет, то можно и не открывать.
2) посмотрим, нужно ли открывать эту клетку. Для этого подставляем в неё по очереди все цифры, кроме правильной, и смотрим, есть ли решение. Если хотя бы один раз оно есть, то клетку можно и открыть. Если ни разу решения не нашлось (например, эта клетка - 9-я в ряду, в котором уже открыто 8 клеток), то открывать её не нужно, поскольку иначе набор будет не минимальным.

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

Насколько я понял, вам надо раскрасить вершины N-мерного куба (иначе как объяснить 2^N вершин и N рёбер?) в K цветов так, чтобы в 1-окрестности любой вершины (т.е. она сама плюс все её соседи) присутствовали все цвета.
Задача очень похожа на коды, исправляющие ошибки. Но там обычно ставится двойственное условие - чтобы в 1-окрестности любой вершины каждый цвет встречался не более одного раза.
Если N=2^m-1, то у задачи есть точное решение (c K=N+1), оно описывается кодом Хэмминга: все кодовые слова красим в один цвет, а множество вершин каждого другого цвета получаем из кодовых слов с помощью XOR с константой (своей для каждого цвета).
Для других N надо думать. Но в этом есть смысл только если я правильно понял задачу.

Я решал подобную задачу, заменяя самую часто встречающуюся пару символов новым символом (если она встречалась более трех раз) — правда, роль «символов» у меня играли слова. Самой длинной «часто встречающейся» подстрокой в «Мертвых Душах» оказалась «дама приятная во всех отношениях».

В случае, если нужно передать действительно произвольный код Хаффмана, то выиграть почти ничего нельзя. Код определяется N-элементным вектором m-битных чисел (с условием, что все элементы различны) — это буквы, отсортированные по кодам, и расстановкой скобок в выражении из N операндов — это двоичное дерево. Число векторов равно (2^m)!/(2^m-N)!, число деревьев — C(N,2*N)/(4*N-2). Если N заметно меньше, чем 2^m, то первое из этих чисел можно оценить как 2^(m*N), а второе — как 2^(2*N)/(4*N-2)/sqrt(pi*N). Общее число бит в их произведении — примерно m*N+2*N.
По мере приближения N к 2^m появляется возможность выиграть до 1.4*N бит (за счет того, что (2^m)!< (2^m)^(2^m).

Что-то не так в условии. 24-битных чисел всего 16*10^6, их никак не наберется 2^9.
И вопрос — нужно получить именно заданные коды Хаффмана, или достаточно, чтобы получились какие-нибудь эквивалентные по длине (а алгоритмы упаковки и распаковки сами договорятся, чтобы распакованные коды были именно теми, которые используются при упаковке основного сообщения)?

Задача сия мне попадалась неоднократно. В разных размерностях (от 1 до 6, причем шестимерное пространство было совсем не декартовым — оно описывало перемещения трехмерного пространства) и с разным числом точек, но всегда без точной формулировки. Хорошего решения я, кажется, не написал ни разу, каждый раз махал рукой и шел другим путем. Но мысли остались следующие.
1) без понятия «масштаб» задача не имеет смысла. То есть, прежде чем решать ее, надо задаться неким «размером окошка», «радиусом размытия точки», «шириной серой зоны» и т.п.
2) чаще всего этот размер заранее неизвестен. Если взять его с запасом, то результат будет правдоподобен, но неточен а если размер окажется слишком маленьким, то наоборот, найдется локальное скопление среди пустоты. Лучше всего, наверное, выбрать убывающую последовательность r1>r2>r3>r4… (например, для окна 2000х2000 это моут быть степени двойки от 128 до 8), найти квадрат со стороной r1, содержащий максимальное количество точек, в нем — квадрат со стороной r2, и т.д. В этом случае наш результат будет правдоподобен во всем диапазоне масштабов.
3) Искать границы квадратов с точностью до пикселя смысла нет. Если мы ищем квадрат NxN, то достаточно перебрать квадраты с шагом N/4 по каждой координате. Например, если мы ищем квадрат 128х128 на плоскости размером 2000х2000, то достаточно рассмотреть 3600 возможных положений этого квадрата (вершина имеет координаты от 0 до 1888 с шагом 32). Завести целочисленный массив такого размера. Каждая точка попадает в 16 квадратов (или меньше) — увеличить 16 ячеек на 1. Найти максимальную — она даст стартовый квадрат.
После этого в этом квадрате перебрать 25 квадратов 64х64, в максимальном из них 25 квадратов 32х32 и т.д.
Если r1 выбран слишком маленьким, а плоскость была слишком большой, то вместо массива (который был 60х60) можно воспользоваться каким-нибудь деревом (для экономии памяти и времени на инициализацию).
Не исключено, что имеет смысл просмотреть не одну последовательность квадратов, а несколько (выбрать 10 квадратов размером r1 с наибольшим весом, из всех квадратов со стороной r2, лежащих в них — 10 наибольших и т.д.) Но это будет писать сложнее, а сработает оно только если скопление выражено нечетко, а где-то есть разреженная туманность. Впрочем, в этой ситуации надо сразу уменьшать r1.