Estou escrevendo uma base de tabela para uma variante do xadrez japonês. Para indexar a base da tabela, codifico cada posição do xadrez como um número inteiro. Em uma das etapas de codificação, eu codifico onde as peças estão no quadro. Como o método atual é um pouco complicado, deixe-me explicar o problema de maneira simplificada.

A codificação

Na base do jogo final, eu tenho (digamos) seis peças de xadrez distintas que quero distribuir em um tabuleiro com 9 quadrados. Eu posso ingenuamente representar suas posições por seis (a, b, c, d, e, f) onde cada uma das variáveisa paraf é um número no intervalo de 0 a 8, inclusive indicando onde a peça de xadrez correspondente está localizada.

No entanto, essa representação não é ótima: não há duas peças de xadrez que possam ocupar o mesmo quadrado, mas a codificação mencionada permite felizmente isso. Podemos codificar a mesma posição por seis tuplas [a, b ', c', d ', e', f '] Ondea é o mesmoa como antes,b ' é um número de 0 a 7, inclusive indicando o número do quadrado em que a segunda peça está. Isso funciona atribuindo um número de 0 a 7 a cada quadrado em que a primeira peça não está. Por exemplo, se a primeira peça estiver no quadrado 3, os números quadrados da segunda peça serão:

1st piece: 0 1 2 3 4 5 6 7 8
2nd piece: 0 1 2 - 3 4 5 6 7

as outras peças são codificadas da mesma forma,c ' como um número de 0 a 6,d ' como um número de 0 a 5, etc. Por exemplo, a codificação ingênua (5, 2, 3, 0, 7, 4) produz a codificação compacta (5, 2, 2, 0, 3, 1):

1st: 0 1 2 3 4 5 6 7 8 --> 5
2nd: 0 1 2 3 4 - 5 6 7 --> 2
3rd: 0 1 - 2 3 - 4 5 6 --> 2
4th: 0 1 - - 2 - 3 4 5 --> 0
5th: - 0 - - 1 - 2 3 4 --> 3
6th: - 0 - - 1 - 2 - 3 --> 1

Na minha codificação real, o número de peças que eu quero codificar não é fixo. O número de quadrados no tabuleiro, porém, é.

A questão

Como posso converter eficientemente a representação ingênua em representação compacta e vice-versa? Eu uso o padrão C99 para o programa. No contexto desta pergunta, não estou interessado em respostas que usem construções não-padrão, montagem em linha ou intrínsecas.

Esclarecimento de perguntas

Como parece haver alguma confusão sobre a questão:

A questão é encontrar uma maneira praticamente eficiente de implementar a conversão entre osingênuo e acompactar representações de posiçãoAmbas as representações sãon-tuplos de números inteiros em determinados intervalos. A questão não é sobre como codificar essas representações em qualquer outra coisa.Em um dos casos que tenho, o número de quadrados é 25 e o número de peças é até 12. No entanto, estou interessado em uma implementação que funcione para um espaço de parâmetros razoável (por exemplo, até 64 quadrados e até 32 peças) .Não estou interessado em representações ou codificações alternativas, especialmente representações ou codificações que não são ideais.Também não estou interessado em observar que ocompactar representação não vale o esforço.Também não estou interessado em respostas que usem intrínsecas, montagem em linha ou quaisquer outras construções não-padrão (exceto talvez as descritas pelo POSIX).