Каждая клетка поля обычной шахматной доски кодируется минимально
возможным и одинаковым количеством бит. Сколько информации (в
Байтах) нужно, чтобы записать все возможные ходы фигуры короля? (Для
справки: размер шахматной доски 8х8; король может ходить по прямым
и диагоналям; каждый ход описывается указанием начальной и конечной
клетки)

Какая разница, как кодируется клетка поля? Для обозначения её координаты достаточно 6 битов, но сама доска кодируется простой последовательностью 64 значений [тип фигуры и цвет либо пустая]. Но у короля в общем случае 8 ходов. Я понимаю, рассматриваются не все возможные ходы короля в процессе игры, их, грубо говоря, бесконечно, а только варианты одного хода. На него нужно, понятное дело, три бита, но в шахматах записывается иначе: тип фигуры, позиция, цель; например: Фh5:f7 (ферзь с h5 на f7). Т. е. 3 бита на фигуру (6 вариантов фигур), 6 битов на начало хода и столько же на конец, независимо, король это или другая фигура. Задание не совсем понятно написано.