Los 94 bits que se conseguian se obtienen de una organización como la que sigue:

FFFFCCCC x4 == 32
XFFFFCCCC x3 == 27
XXXFFFFCCCC x2 == 22
XXXXXFFFFCCCC x1 == 13

Donde FFFFCCCC son los 8 bits necesarios para identificar fila-columna, y las X son los bits necesarios para identificar la variante de barco. El x4, x3, etc denota la cantidad, con lo que ya se ve que la codificación es para los barcos de 1, 2, 3 y 4 piezas respectivamente. Es decir, las variantes de los de 4 piezas se codifican con XXXXX (5 bit). Al final hay el recuento de bits, que si se suma, da los 94 bits que teniamos hasta ahorra.

Mirando de optimizar el tema, se me ocurre como reducir 1 bit para la codificación de los barcos de 3 piezas. Actualmente se usan 6 bits (3+3), pero fijaos que, en lugar de codificar cada versión de barco de entre las 6 posibles, lo que podemos hacer es codificar la configuración de los 2 barcos, y además teniendo en cuenta que el orden de los barcos lo ponemos nosotros, con lo que se reduce la cosa.

Sabiendo que hay 6 versiones de cada barco, tenemos las siguientes posibilidades:
1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5, 3-6, 4-4, 4-5, 4-6, 5-5, 5-6, 6-6 (21 combinaciones en total)

Fijaos que no pongo ni la 2-1, ni la 3-1, 3-2, etc, ya que son la misma que la 1-2, 1-3, 2-3 solo que cambiando el orden en que vamos a poner los barcos (y el orden lo ponemos nosotros).

Vale, hasta aquí vemos que 21 posibilidades se codifican en 5 bits, y ya reducimos 1... tenemos 93.

Ahora la forma en que se pueden reducir los 5 bits (enteritos) para la codificación del tipo de barco de 4 piezas:

Recordemos que hay 19 posibilidades (de ahí los 5 bits). Bien, pues en lugar de codificarlo con bits, lo codificamos con el orden en que introducimos los 4 barcos de 1 unidad.

Estamos de acuerdo en que cada casilla de la matriz de 14x14 puede tener su número (del 0 al 195), con lo que las cuatro posiciones de los barcos pueden establecer un orden entre ellas (1, 2,3 y 4). Así pues, podemos introducir los barcos ordenados tal que 1-2-3-4, o los podemos introducir en plan 3-2-4-1.

Partiendo de ese principio, vemos que podemos introducir esos 4 barcos de 24 formas distintas:
1-2-3-4, 1-2-4-3, 1-3-2-4, 1-3-4-2, 1-4-2-3, 1-4-3-2,
2-1-3-4, 2-1-4-3, 2-3-1-4, 2-3-4-1, 2-4-1-3, 2-4-3-1,
3-1-2-4, 3-1-4-2, 3-2-1-4, 3-2-4-1, 3-4-1-2, 3-4-2-1,
4-1-2-3, 4-1-3-2, 4-2-1-3, 4-2-3-1, 4-3-1-2, 4-3-2-1.

Por lo tanto, sólo necesitamos ordenar la introducción de nuestros 4 barcos de forma que codifiquen una de las 19 versiones disponibles para el barco de 4 piezas, ahorrandonos de esta forma los 5 bits necesarios para esta codificación. (Las 5 ordenaciones restantes, simplemente no las usaremos nunca).

Por lo tanto, 93-5 = 88 bits.

Si no se entiende algo de la solución, lo aclaro con mucho gusto...

Como ya he dicho, cada casilla tiene su código (de 0 a 195). Pasar de coordenadas a "código" és tan fácil como hacer algo del estilo:

Q = X + Y*14 , entendiendo que empezamos a contar desde (0,0)

Luego, para saber en que orden has puesto los barcos, pues le calculas esa Q y si obtienes algo como:

34,3,141,98

pues sabes que el orden en que los has metido es:

2,1,4,3

y eso te codifica una versión del barco de 4.