Примечание: речь идет о стандартной головоломке судоку 9х9. Решение должно поддерживать только разрешенные, легальные загадки . Таким образом, решение не должно поддерживать пустые ячейки и может полагаться на свойства решенной головоломки судоку.
Мне было интересно, но я не мог придумать ответ, который меня устраивал. Наивное решение будет использовать один байт для каждой ячейки (81 ячейка), всего 648 бит. Более сложное решение будет хранить всю головоломку судоку под номером 9 (одна цифра на ячейку) и потребовать бит.
Но его все еще можно улучшить, например, если вы знаете 8 из 9 чисел в подсетке 3x3, вы можете тривиально вывести 9-е число. Вы можете продолжить эти мысли до такой степени, что этот вопрос сводится к тому, каково количество уникальных решенных судоку? Теперь вы можете использовать огромную таблицу поиска, которая отображает каждое двоичное число в головоломку судоку, но это не будет полезным решением.
Итак, мой вопрос:
Ответы:
Вдоль тех же строк, что и в ответе фаната-храповика, если вы заполняете не отмеченные звездочкой ячейки в следующей матрице по 3x3 за раз, всегда выбирая следующее поле для заполнения, чтобы оно было таким, которое разделяет строки или столбцы с ящиком, который вы уже заполнив, вы получите образец, подобный следующему для количества вариантов на шаг (сначала заполняйте верхнюю среднюю ячейку, затем верхнюю правую рамку и т. д.).
В каждом блоке 3x3 после первого, когда вы заполнили одну строку или столбец блока, три из оставшихся шести цифр локализуются в одной строке. Сначала выберите их местоположения, а затем заполните оставшиеся три ячейки. (Таким образом, фактический порядок заполнения ячеек может варьироваться в зависимости от того, что вы уже знаете, но количество вариантов никогда не превышает того, что я показал.)
После того, как вы заполнили эти ячейки, все звезды определены.
Если я рассчитал правильно, это дает 87 бит. В последнем блоке 3x3 есть некоторая дополнительная экономия, согласно комментарию Питера Шора: каждое значение локализовано в одной из четырех ячеек, и каждая строка содержит по крайней мере одну ячейку только с четырьмя возможными значениями, поэтому, безусловно, факторы в этом блок должен начинаться с 4, а не с 6, но я не понимаю остальных факторов в ответе Шора.
источник
6 5 4 4 3 2 3 2 1
я думаю, это должно быть6 5 4 6 5 4 3 2 1
в худшем случае.Продолжая с ответом @ peter, вот список возможностей наихудшего случая для каждой ячейки, когда вы заполняете его, начиная с верхнего левого
это составляет для 4,24559E + 29 возможностей или 99 бит
редактировать: забыл, что последний квадрат полностью определяется всеми остальными
источник
Вам не нужен полный справочный стол для достижения оптимальной сжимаемости. Я полагаю, что современные компьютеры, использующие очень разумную справочную таблицу, способны подсчитать количество ограниченных Судоку, которые являются Судоку с некоторыми цифрами, уже имеющимися на месте. Используя это, вот как вы кодируете (декодирование аналогично).
Изменить: страница Википедии по математике судоку помогает нам прояснить картину. Также полезна таблица, составленная Эдом Расселом .
Оказывается, что если вы рассматриваете только три верхние строки, то, по сути, есть только 44 различных конфигурации для рассмотрения. В таблице вы можете найти общее количество конфигураций, эквивалентных любой заданной (при условии, что верхняя строка равна 123456789), и общее количество завершений каждой из них. Учитывая судоку, вот как мы бы вычислили его порядковый номер:
Эта процедура обратима и генерирует судоку из порядкового номера. Обратите внимание, что счет Судоку был сокращен до нескольких минут (в 2006 году; см. Страницу обсуждения статьи в Википедии) или меньше, поэтому я ожидаю, что на современном компьютере этот подход будет очень практичным и займет несколько секунд или меньше.
источник
Вот алгоритм, который, я подозреваю, даст довольно хорошее кодирование. У вас есть готовая судоку, которую вы хотите сжать, и, скажем, вы уже закодировали некоторые ее ячейки, так что есть частичная судоку (не обязательно с уникальным решением) с заполненными ячейками.
Используйте фиксированный алгоритм, чтобы подсчитать, сколько чисел можно поместить в каждую пустую ячейку. Найдите первую лексикографическую ячейку, в которую можно поместить наименьшее количество различных чисел, и закодируйте, какое из этих чисел входит в нее (так что если ячейка может содержать только 3, 7 или 9, 3 кодируется как «0». ", 7 на" 1 "и 9 на" 2 "). Кодируйте полученную последовательность, используя арифметическое кодирование (которое учитывает количество возможных чисел, которые может содержать ячейка).
Я не знаю, какой длины будет полученная двоичная последовательность, но я подозреваю, что она довольно короткая, особенно если ваш алгоритм подсчета количества чисел, помещаемых в ячейку, достаточно сложен.
Если бы у вас был хороший алгоритм, который оценивал вероятность каждой ячейки, содержащей данное число, вы могли бы сделать еще лучше.
источник
Любые комментарии и критика приветствуются
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)
источник
Я бы пошел со следующим простым анализом:
Каждое значение может быть сохранено в 4 битах (в диапазоне от 1 до 9, эти три бита даже допускают 0-16)
Я думаю, я мог бы уменьшить его до:
где
Редактировать: Нео Стиль: я знаю латекс.
источник
Это число отличается для каждого судоку. Одним из правил для судоку является то, что у него есть только одно решение.
Итак, если вы посмотрите на пример, это минимальный объем данных, которые вы должны хранить.
Если вы работаете с противоположной стороны, вы можете удалить цифру за цифрой и запустить солвер для результата, чтобы увидеть, есть ли у него точно одно решение. Если это так, вы можете удалить еще одну цифру. Если нет, вы должны восстановить эту цифру и попробовать другую. Если вы не можете, вы нашли минимум.
Поскольку большинство головоломок начинаются в основном с пустого места, кодирование длин серий, вероятно, даст хорошие результаты.
источник