Указание любой произвольной сетки 9x9 требует указания позиции и значения каждого квадрата. Наивное кодирование для этого может дать 81 (x, y, значение) триплетов, требуя 4 бита для каждого x, y и значения (1-9 = 9 значений = 4 бита) в общей сложности 81x4x3 = 972 бита. При нумерации каждого квадрата можно уменьшить информацию о местоположении до 7 бит, отбрасывая бит для каждого квадрата и в общей сложности 891 бит. Задав предопределенный порядок, можно уменьшить его более радикально, до 4 битов для каждого значения, всего 324 бита. Однако в судоку могут отсутствовать номера. Это обеспечивает возможность уменьшения количества чисел, которые должны быть указаны, но может потребовать дополнительных битов для указания позиций. Используя нашу 11-битную кодировку (положение, значение), мы можем указать головоломку с подсказками с 11 бит, например, минимальная (17) головоломка требует 187 бит. Лучшее кодирование, о котором я до сих пор думал, - это использовать один бит для каждого пробела, чтобы указать, заполнен ли он, и, если да, следующие 4 бита кодируют число. Это требует 81 + 4 n битов, 149 для минимальной загадки ( n = 17 ). Существует ли более эффективная кодировка, желательно без базы данных каждой действующей настройки судоку? (Бонусные баллы за решение общего n из N × N головоломки)
Мне только что пришло в голову, что многие головоломки будут чередованием другой или просто перестановкой цифр. Возможно, это поможет уменьшить количество необходимых бит.
Согласно Википедии ,
Число классических сеток 9 × 9 для решения судоку составляет 6 670 903 752 021 072 936 960 (последовательность A107739 в OEIS) или приблизительно .
Если я правильно сделал свою математику ( ), что составляет 73 (72.498) битов информации для справочной таблицы.
Но:
Было показано, что число принципиально различных решений, когда учитываются симметрии, такие как вращение, отражение, перестановка и перемаркировка, составляет всего 5 472 730 538 [15] (последовательность A109741 в OEIS).
Это дает 33 (32,35) бита, поэтому вполне возможно, что умный метод указания того, какую перестановку использовать, может получить меньше полных 73 битов.
Ответы:
Да. Я могу думать о кодировке, улучшающей вашу 149-битную кодировку как минимум9×9 головоломкой в 6 или 9 бит, в зависимости от условия. Это без базы данных или какого-либо реестра других решений или частичных плат. Здесь это идет:
Сначала вы используете бита для кодирования числа m с минимальным количеством появлений на доске. Следующие 4 бита кодируют фактическое число л в раз м появляется. Следующие 7 л биты кодирования каждой из позиций , в которых4 m 4 ℓ m 7ℓ появляется.m
Следующие биты являются флагами, указывающими, имеют ли оставшиеся позиции номер или нет (вы просто пропускаете позиции, в которых находится m ). Где бы ни был один из этих битов , следующие 3 бита указывают, какое это число (в упорядоченном наборе { 1 , … , 9 } без m ). Например, если m = 4 и 3 бита равны , то число в соответствующей позиции на плате является 5-м (считая от 0) в наборе { 1 , 2 , 3 ,81−ℓ m {1,…,9} m m=4 {1,2,3,5,6,7,8,9} 6 j<m j−1 j>m j−2 ℓ будут добавлены ) бита для кодирования остальной платы на этом шаге.3(n−ℓ)
1
101
, так что это 6 . Числа j < m будут закодированы в двоичном виде как j - 1 , а числа j > m будут закодированы как j - 2 . Так как мы уже написали ℓ позиций, только 3 ( n - ℓТаким образом, общее число битов , необходимых для кодирования плату с помощью этой процедуры ,
Для отметим, что ℓ может быть 0 или 1 (в общем, ℓ ≤ ⌊ n / 9 ⌋ ). Таким образом, B может быть 140 или 143 в зависимости от того, есть ли число на доске.n=17 ℓ ℓ≤⌊n/9⌋ B
Стоит отметить, что решение Кевина намного лучше в общем случае. Это кодирование использует не более 149 бит только для или для n = 20 при условии, что ℓ = 0 . По крайней мере, это показывает общую идею о том, как воспользоваться тем фактом, что N = 9 очень близко к 2 ⌊ log 2 N which (что означает, что мы склонны «терять память», используя 4 бита на значение, поскольку 4 бита позволяют нам, чтобы выразить N = 16 чисел, а также.n∈{17,18,19} n=20 ℓ=0 N=9 2⌊log2N⌋ N=16
0111
0001
0100100
011100010100100
0
1
0
1
0000000100101100
110
(шестое число, считая от 0 в списке111
. Полная кодировка выглядит следующим образом:Полная кодировка есть
01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000
, и читатель может проверить, что длина этой строки действительно 143 :-)источник