Какое минимальное количество битов требуется для хранения головоломки судоку?

28

Примечание: речь идет о стандартной головоломке судоку 9х9. Решение должно поддерживать только разрешенные, легальные загадки . Таким образом, решение не должно поддерживать пустые ячейки и может полагаться на свойства решенной головоломки судоку.

Мне было интересно, но я не мог придумать ответ, который меня устраивал. Наивное решение будет использовать один байт для каждой ячейки (81 ячейка), всего 648 бит. Более сложное решение будет хранить всю головоломку судоку под номером 9 (одна цифра на ячейку) и потребовать бит.log2(981))=257

Но его все еще можно улучшить, например, если вы знаете 8 из 9 чисел в подсетке 3x3, вы можете тривиально вывести 9-е число. Вы можете продолжить эти мысли до такой степени, что этот вопрос сводится к тому, каково количество уникальных решенных судоку? Теперь вы можете использовать огромную таблицу поиска, которая отображает каждое двоичное число в головоломку судоку, но это не будет полезным решением.

Итак, мой вопрос:

Без использования таблицы поиска, какое минимальное количество битов требуется для хранения головоломки судоку и по какому алгоритму?

orlp
источник
3
Есть ли действительно качественная разница между отсутствием 9-го числа в 3х3, строке или столбце и просто хранением минимального судоку с пустыми пробелами, который имеет это уникальное решение? «Не нужно поддерживать пустые ячейки» - это всего лишь красная сельдь, если это необходимо для оптимального решения.
Wooble
19
Поскольку существует 6,67 × 10 ^ 21 решенного судоку («QSCGZ» 2003; Felgenhauer и Jarvis 2005) и log_2 (6,67 × 10 ^ 21) = 72,4…, нижняя граница составляет 73 бита (даже если вы используете поиск по огромной таблице) , Если вам не нужно различать по существу одинаковые решения с точки зрения симметрии, эта нижняя граница не применяется.
Цуёси Ито
9
Этот вопрос станет хорошим конкурсом для программистов.
Питер Шор
1
Аналогичная нижняя граница для практически идентичных решений составляет 33 бита.
Чарльз
3
Зачем вам нужен справочный стол? Вы можете просто перечислять решения Судоку по одному, пока не достигнете желаемого числа.
Зируи Ван

Ответы:

19

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

В каждом блоке 3x3 после первого, когда вы заполнили одну строку или столбец блока, три из оставшихся шести цифр локализуются в одной строке. Сначала выберите их местоположения, а затем заполните оставшиеся три ячейки. (Таким образом, фактический порядок заполнения ячеек может варьироваться в зависимости от того, что вы уже знаете, но количество вариантов никогда не превышает того, что я показал.)

После того, как вы заполнили эти ячейки, все звезды определены.

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

6 5 4 * * * 6 3 3
3 3 2 * * * 5 3 2
3 2 1 * * * 4 2 1

6 3 3 6 5 4 * * *
5 3 2 3 3 2 * * *
4 2 1 3 2 1 * * *

Если я рассчитал правильно, это дает 87 бит. В последнем блоке 3x3 есть некоторая дополнительная экономия, согласно комментарию Питера Шора: каждое значение локализовано в одной из четырех ячеек, и каждая строка содержит по крайней мере одну ячейку только с четырьмя возможными значениями, поэтому, безусловно, факторы в этом блок должен начинаться с 4, а не с 6, но я не понимаю остальных факторов в ответе Шора.

Дэвид Эппштейн
источник
4
Вы также можете уменьшить количество вариантов при заполнении шестого поля 3х3. Это поле становится 4,3,2 / 3,2,1 / 2,1,1 на общую сумму 83 бита, если я правильно рассчитал.
Питер Шор
@ Питер - нет. 3 цифры справа могут быть такими же, как цифры выше. Вы не знаете, что все они разные. Наиболее достоверные уникальные числа - 3, поэтому первая коробка - это выбор из шести предметов. (Это одно место является примером. Это верно и для других.)
Хоган
@ Дэвид - продолжая мой комментарий к Питеру, я не думаю, что твои цифры неверны. Во втором ящике у вас есть, 6 5 4 4 3 2 3 2 1я думаю, это должно быть 6 5 4 6 5 4 3 2 1в худшем случае.
Хоган
Хоган, нет, см. Часть в моем ответе о том, что «заполнив одну строку или столбец поля, вы всегда можете выбрать следующую строку или столбец для заполнения, в которой будет не более четырех возможных значений. "
Дэвид Эппштейн
@ Давид - позволяет пометить 3 x 3s 1,1 1,2 1,3 слева направо сверху вниз. Пусть помечают квадраты A - я иду слева направо сверху вниз. Местоположение D в 1,3 знает 3 числа в 3x3, в котором оно находится (A, B, C), и оно знает 3 числа в 1,2 (D, E, F), но оно не знает, что эти 6 чисел различны. Это могут быть те же 3 числа из ячеек 3,1 и 2,1, таким образом, есть варианты MAX 6.
Хоган
13

Продолжая с ответом @ peter, вот список возможностей наихудшего случая для каждой ячейки, когда вы заполняете его, начиная с верхнего левого

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

6   6   3       6   5   4       3   2   1
5   5   2       5   5   3       3   2   1
4   4   1       4   2   1       3   2   1

3   3   3       3   3   3       1   1   1
2   2   2       2   2   2       1   1   1
1   1   1       1   1   1       1   1   1

это составляет для 4,24559E + 29 возможностей или 99 бит

редактировать: забыл, что последний квадрат полностью определяется всеми остальными

чокнутый урод
источник
Очень хорошо!! Позвольте мне добавить, что для меня неясно, что вы могли бы когда-нибудь реализовать эти худшие возможности для настоящего решения Судоку (особенно если вы используете сложный алгоритм, который использует некоторые методы Судоку, чтобы сузить возможности, для которых числа могут идти в ячейке ).
Питер Шор
@peter, но вам нужно добавить это сужение в en и decoding, и я понял, что если вам нужно выбрать один и не устанавливать порядок (самый простой способ, но не оптимальный), вам нужно добавить это и в кодировку
храповик урод
Нет, если вы используете один и тот же алгоритм для определения наилучшей ячейки в процедуре en и декодирования, он даст одинаковую ячейку (поскольку он работает с теми же данными), поэтому процедуры en и decoding будут синхронизированы, и вам не нужно добавлять порядок в кодировку. Эта идея также заставляет работать алгоритм сжатия данных LZW.
Питер Шор
Я думаю, что минимальные биты, необходимые для хранения правильной головоломки судоку, не являются вычислимой функцией (Колмогоров). Однако 103 бита Питера / Храповика кажутся хорошей границей.
Марцио Де Биаси
2
@Vor: Технически машина Тьюринга, которая выводит правильное количество битов при задании головоломки судоку в качестве входных данных, конечна, потому что входной набор конечен, поэтому «сколько битов необходимо для описания этой головоломки» можно «тривиально» вычислить. Я говорю, что на самом деле мы могли бы найти такую ​​машину Тьюринга явно (в принципе, вычисления потребовали бы слишком много времени), потому что она не может быть сложнее, чем вычисление конечного префикса числа Омеги.
Аарон Стерлинг
5

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

d1N1d1d2N2d1d2N=iNi

72.4

Изменить: страница Википедии по математике судоку помогает нам прояснить картину. Также полезна таблица, составленная Эдом Расселом .

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

  1. Нормализуйте конфигурацию так, чтобы ее верхний ряд был 123456789.
  2. Узнайте, к какой из 44 различных конфигураций он принадлежит. Статья в Википедии дает алгоритм для этого. В таблице указано количество классов эквивалентности для каждой конфигурации, а также количество дополнений.
  3. Определите порядковый номер конфигурации трех верхних строк в своем классе эквивалентности. Это можно сделать двумя способами: либо с использованием списка всех классов эквивалентности (всего 36288 во всех классах эквивалентности), либо путем поиска способа быстрого перечисления всех из них.
  4. Нормализуйте оставшиеся строки, отсортировав строки 4-6 и 7-9 по их первому столбцу, а затем отсортируйте эти два блока строк произвольным образом. Это уменьшает количество завершений в 72 раза.
  5. 220
  6. ijkCi,DiCi+jDi+k9!72

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

Юваль Фильмус
источник
2
Можно ли эффективно посчитать решения для ограниченного судоку? Это # P-complete, если вы обобщаете размер и допускаете пропуски в произвольных местах.
Tsuyoshi Ito
2
Как я уже упоминал в своем ответе, арифметическое кодирование обеспечит почти оптимальное сжатие для этого сценария.
Питер Шор
1
Возможно, вы правы, но ваше утверждение подразумевает, что количество сеток судоку (6,67 × 10 ^ 21) легко вычислить на современном компьютере. Это действительно можно вычислить, но это легко?
Цуёси Ито
2
Я получил такое впечатление от одной из статей, описывающих, как сделать расчет. Вы можете даже вычислить некоторые из «более тяжелых» данных при предварительной обработке и сохранить их в таблице разумного размера - выигрыш в скорости может быть значительным. Насколько я помню, это заняло у них всего несколько часов, и это несколько лет назад. Теперь предположим, что вы используете стол, чтобы сделать его в 1000 раз быстрее. Более того, на каждом этапе цифры уменьшаются в геометрической прогрессии, поэтому большая часть работы, вероятно, сосредоточена на первом этапе.
Юваль Фильмус
1
@tsuyoshi Я полагаю, что есть какая-то версия / расширение BDD, которое делает вычисления относительно простыми - мне нужно немного покопаться, но я знаю, что они использовались для некоторых довольно сложных комбинаторных задач подсчета.
Стивен Стадницки
4

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

Используйте фиксированный алгоритм, чтобы подсчитать, сколько чисел можно поместить в каждую пустую ячейку. Найдите первую лексикографическую ячейку, в которую можно поместить наименьшее количество различных чисел, и закодируйте, какое из этих чисел входит в нее (так что если ячейка может содержать только 3, 7 или 9, 3 кодируется как «0». ", 7 на" 1 "и 9 на" 2 "). Кодируйте полученную последовательность, используя арифметическое кодирование (которое учитывает количество возможных чисел, которые может содержать ячейка).

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

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

Питер Шор
источник
3

Любые комментарии и критика приветствуются

69.96171.72

1.) Хранение головоломки подразумевает хранение решения (информация теоретически).

t(α)α2t(α)αt(3) =2.444443

Pα4t(α)α2

Mβ×α4β2t(α)α22t(α)α2{0,±1}β=kt(α)α2k

V=MPβ|α2|M{0,±1}

Vβlogα2=2kt(α)α2logα

α=3t(α) =32kt(α)α2logα=69.96k85.86kk=2139.92171.72bits

MP

A.)k2t(α)1

B.)t(α)t(α)kt(α)α4Ct(α)α2α4(3α21)Ct(α)α23t(α)

t(α)α2

C.)k

D.) VVO((Vmax))=O(|α2|)2βlogα2=2kt(α)α2logα

2k2A.)B.)C.)D.)8973

против
источник
1

Это должно сообщить о реализации компактного кодирования завершенного судоку (аналогично предложению Zurui Wang 9/14/11).

Ввод - это верхний ряд и первые 3 цифры второго ряда. Они уменьшены до 1-9! и 1-120 и объединены до <= 4,4x10 ^ 7. Они используются как данные для лексикографического подсчета всех частичных сукокусов из 30 цифр до соответствующей последовательности. Затем окончательный отсчет до всех 81 цифры делается тем же способом. Эти 3 последовательности хранятся в виде 32-разрядных целых чисел, не превышающих 26 бит, поэтому они могут быть сжаты в дальнейшем. Весь процесс занимает около 3 минут, а первые 30 цифр занимают большую часть времени. Декодирование аналогично - за исключением совпадений, а не судоку.

Скоро - Пересмотр включает первые 3 цифры 2-й строки в перечислении 30-значных дополнений (2-й 32-разрядный код), сравнение с перечислением Джарвиса (Jscott, 3/1615)

jscott
источник
1
К вашему сведению: если вы создали две учетные записи и хотели бы объединить их, см. Cstheory.stackexchange.com/help/merging-accounts
DW
0

Я бы пошел со следующим простым анализом:

Каждое значение может быть сохранено в 4 битах (в диапазоне от 1 до 9, эти три бита даже допускают 0-16)

9×9=81

8×8

Я думаю, я мог бы уменьшить его до:

b=log2(v)(n1)

где

v

n

Редактировать: Нео Стиль: я знаю латекс.

Альфа
источник
-2

Это число отличается для каждого судоку. Одним из правил для судоку является то, что у него есть только одно решение.

Итак, если вы посмотрите на пример, это минимальный объем данных, которые вы должны хранить.

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

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

Аарон Дигулла
источник
Этот жадный подход не обязательно достигает минимума, возможно, вам нужно тщательно выбирать, какую цифру удалять на каждом шаге.
Диего де Эстрада
Это просто пример. Google для "генераторов головоломки судоку", чтобы получить более сложные.
Аарон Дигулла
5
Я действительно не понимаю, почему вы ожидаете, что это будет работать особенно хорошо. Кажется, это скорее интуитивное чувство, чем ответ.
Джо Фицсимонс