Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I

Arranjos

As linguagens de programação procuram dar suporte à implementaçao do conceito de vetores e matrizes existentes na matemática. Na linguagem C a base deste suporte são os arranjos. Um arranjo é constituído de uma seqüência indexável de variáveis todas do mesmo tipo.

Já vimos como utilizar as variáveis correspondentes aos tipos primitivos. Na linguagem C, além do tipos primitivo T (p.ex. int, double, char) podemos estruturar um “arranjo de T”.

Considere um programa, como no caso do cálculo dos dígitos verificadores do CPF, que precisa extrair os dígitos de um número armazenado em uma variável do tipo int. Uma possibilidade de concepção para este programa é a declaração de nove variáveis do tipo int; o trecho de programa abaixo declara nove variáveis e atribui um valor a duas delas:
int d0, d1, d2, d3, d4, d5, d6, d7, d8;
d0=cpf%10;
d1=cpf/10%10;

Com o uso de arranjos podemos criar uma estrutura que pode conter um número arbitrário de variáveis de um mesmo tipo. No trecho de programa abaixo é declarado um arranjo com nove componentes ou elementos ou variáveis do tipo int e é atribuido o valor da unidade decimal a um dos componentes deste arranjo:
int d[9];
d[0]=cpf%10;
d[1]=cpf/10%10;
No trecho acima d denota a estrutura do tipo "arranjo de int" e d[0] representa um componente ou variável do tipo int. Observe que não existe uma “variável” com nome “d”, existem nove variáveis indexáveis “d[i]”.

Podemos indexar os elementos de um arranjo de forma similar à notação da matemática. Indexar significa indicar um dos elementos do arranjo utilizando um índice. Os índices em C sempre começam de zero e o operador de indexação consiste em abre e fecha colchetes - []. Assim d[0] denota o primeiro elemento do arranjo.

A linguagem C permite que elementos de qualquer tipo possam se constituir na forma de arranjo. Assim a expressão geral para o tipo "arranjo de <tipo>" é:
"<tipo> <nome>[<tamanho>]"
conforme exemplos abaixo:
int ai[100];
double ad[200];
char ac[300];

Os componentes de um arranjo podem ser iniciados ou inicializados de forma semelhante às variáveis de tipos primitivos com o que parece ser literais do tipo arranjo.,utilizamos os inicializadores de arranjo :

int numDiasMes[]={0, 31,28,31,30,31,30,31,31, 30, 31, 30, 31};
int totalDias=0;
int i;
for(i=1; i<=12; i++) totalDias+=numDiasMes[i];

O trecho de programa acima declara um agregado do tipo arranjo denominado numDiasMes. Este agregado é iniciado (é iniciada a região de memória onde existem 13 variáveis indexáveis do tipo int). Cada variável int é iniciada com um dos 13 valores mostrados. Cada valor corresponde ao número de dias do mês de índice correspondente. A primeira variável de um arranjo em C corresponde ao índice 0 (zero). Como o primeiro mês, Janeiro, é tradicionalmente denotado pelo número 1, o trecho acima opta por ignorar o primeiro elemento do arranjo - numDiasMes[0].

Os iniciadores de arranjo não podem ser utilizados nas expressões dos comandos de atribuição! O trecho de programa abaixo não é compilável:

int numDiasMes[13];
numDiasMes={0, 31,28,31,30,31,30,31,31, 30, 31, 30, 31}; /* erro! */

A linguagem C tem poucas operações que permitem a manipulação do arranjo como um todo.Observe que, uma vez criado um bloco de memória para um arranjo, este bloco não pode ser “esticado” nem “encolhido”. Por outro lado o bloco pode ser criado de forma “dinâmica”:

int i;
scanf(“%d”,&i);
double ad[i];

No material sobre variáveis foi comentado que a linguagem C utiliza por diversas razões os chamados “ponteiros”. Dado um tipo T podemos sempre definir um tipo que é “ponteiro para T”. Os arranjos não são exceção, na verdade os projetistas da linguagem C definiram os arranjos de forma a fazê-los ficar bem próximos aos ponteiros: existe um relacionamento forte entre arranjos e ponteiros! Qualquer operação que pode ser feita com indexação de arranjos também pode ser feita com manipulação de ponteiros! Mas em geral a manipulação de ponteiros é menos intuitiva! portanto só use a “versão” ponteiro se tiver boas justificativas.

A declaração

int a[10];

define um arranjo com 10 variáveis: a[0], a[1],...a[9];

A notação a[i] refere-se ao i-ésimo elemento do arranjo. Se pa é um ponteiro para um inteiro declarado como:

int *pa;

então atribuição

pa=&a[0];

ajusta pa para apontar para o elemento de índice 0 de a (primeiro elemento). e a expressão:

*(pa+k)

refere-se ao elemento de índice k ou (k+1)-ésimo elemento do arranjo a (dizemos que k é o “offset” ou deslocamento). Na linguagem C o tipo “char []” equivale ao tipo “char *”

Os arranjos de caracteres têm um papel especial na linguagem C e serão tratados com mais detalhes em outra página WWW. Veja por exemplo que eles têm mais de uma possibilidade de inicialização:

char c1[]={'A', 'B', 'C', 0};
char c2[]=”ABC”;

Por convenção os arranjos de caracteres na linguagem C correspondem a “strings” e “strings” são arranjos de caracteres que têm como “último caractere”(convencionalmente) o caractere nulo (todos os bits em zero!).

A representação de uma “matriz” na linguagem C pode feita utilizando um arranjo de arranjos. Veja abaixo um exemplo de representação de uma matriz identidade 3x3 utilizando um arranjo de arranjos de ints e utilizando também o mecanismo de inicialização:
int matIdent[3][3]={ {1,0,0}, {0,1,0}, {0,0,1}};

Quando se mistura o “operador” de indexação (modificador arranjo) com o “operador” de indireção (modificador ponteiro) nas declarações temos que aplicar as regras de prioridade e associação da tabela do material de expressões. Consider a seguinte expressão:

int *id[5];

Sem considerar as questões de prioridade e associatividade haveria pelo menos duas possibilidades de interpretação: (i) id corresponde a um arranjo de 5 ponteiros para ints, ou (ii) id corresponde a um ponteiro para um arranjo de 5 ints. A figura abaixo ilustra as opções:

Pela tabela podemos observar que o operador de indexação tem prioridade sobre indireção e a interpretação adequada é a primeira: id corresponde a um arranjo de 5 ponteiros para int, se quisermos ter certeza disso basta usar a expressão equivalente int *(id[5]); e observar que é possível indexar id:
int ai[5]={100,200,300,400,500};
int *id[5];
id[0]=&ai[0]; id[1]=&ai[1]; ...
for(i=0; i<5; i++) printf(“%d\n”, *id[i]);
Para obter a interpretação (ii) a expressão correspondente é int (*id)[5]; (ponteiro para arranjos de 5 ints). O uso no caso desta última interpretação é diferente:
int ai[5]={100,200,300,400,500};
int (*id)[5];
id=&ai;
for(i=0; i<5; i++) printf(“%d\n”, (*id)[i]);

Exercícios:

Uma relação definida sobre n elementos pode ser representada utilizando um arranjo de arranjos de ints. O arranjo de arranjos deve corresponder a uma matriz quadrada de tamanho n*n. Considere que r contém uma referência para tal arranjo. O componente r[i][j] é “verdadeiro” (valor diferente de zero) quando o elemento correspondente a i está relacionado com o elemento correspondente a j. Se r[i][j] é “falso” (valor igual a zero) então i não se relaciona com j. A partir desta definição é fácil ver que podemos definir 16 relações sobre o conjunto {a,b}. são exemplos destas relações o conjunto vazio representado por{{false, false},{false, false}}, o conjunto{(a,b),(b,a)} representado por {{false,true},{true,false}} e o conjunto {(a,a), (a,b), (b,a), (b,b)} representado por {{true, true}, {true,true}}. Escreva um programa que para uma dada relação representada como descrito:

· Testa se a relação é simétrica

· Testa se a relação é assimétrica.

· Testa se a relação é anti-simétrica.

· Testa se a relação é transitiva.

· Testa se a relação é reflexiva

· Testa se a relação é de equivalência.

Os arranjos nos permitem expressar alguns algoritmos para ordenação dos valores.

Quadrados Mágicos

Um quadrado mágico de ordem Ncorresponde a uma matriz quadrada NxN onde os NxN valores são distintos e correspondem aos inteiros 1,2...NxN, além disso em cada linha, em cada coluna, em cada diagonal a soma dos elementos resulta em um mesmo valor denominado Constante Mágica=N(NxN+1)/2. Não existem quadrados mágicos de ordem 2! Um exemplo de quadrado mágico de ordem 3 é: {{2,7,6},{9,5,1},{4,3,8}} Para os quadrados de ordem 3, 4, 5, ... a constante mágica é 15, 34, 65, 111, 175, 260, ...

Faça um programa que testa se um arranjo de arranjos de ints corresponde a um quadrado mágico. Se você não conseguir uma boa solução veja esta solução incompleta.

Quadrados Latinos

Um quadrado latino corresponde a uma matriz quadrada NxN onde os valores tanto nas linhas quanto nas colunas correspondem a uma permutação do valores 0,1,2,...N-1 (ou 1,2 , ...N) ou mais genericamente as linhas e colunas correspondem a permutações de N símbolos distintos. Existem apenas dois quadrados latino 2x2: {{0,1},{1,0}} (ou {{1,2},{1,2}}) e {{1,0},{0,1}}.

Existem quantos quadrados latinos 3x3? Estes números formam uma seqüência e estão presentes em uma página de um sítio WWW que coleciona seqüências de inteiros(http://www.research.att.com/~njas/sequences/A002860)

01:1,
02:2,
03:12,
04:576,
05:161280,
06:812851200,
07:61479419904000,
08:108776032459082956800,
09:5524751496156892842531225600,
10:9982437658213039871725064756920320000,
11:776966836171770144107444346734230682311065600000

Faça um programa que testa se um arranjo de arranjos de ints codifica um quadrado latino (Considere representações utilizando int[][] e char[][]).

Existem várias técnicas para gerar de maneira sistemática “matrizes candidatas” a serem quadrados latinos. Uma técnica simples (e ineficiente) corresponde a esta função:
#define N 5
void gera(int m[][N], int ordem){
int i,j;
for(i=N-1; i>=0; i--)
    for(j=N-1; j>=0; j--){
      m[i][j]=ordem%N;
      ordem=ordem/N;
    }
}
Esta função gera todas as matrizes onde o elemento m[i][j] é um valor da gama de 0 a N-1, ou seja são N*N “dígitos” cada um podendo assumir N valores. A geração é controlada pelo parâmetro ordem. Para N=2 são 4 dígitos binários, devem ser geradas 16 matrizes, onde ordem 0 corresponde a {{0,0},{0,0}}, ordem 1 corresponde a {{0,0},{0,1}} e ordem 15 corresponde a {{1,1},{1,1}}. Para N=3 são 9 dígitos “trinários” devem ser geradas 19.683 matrizes, para N=4 são 16 dígitos cada um variando de 0 a 3, devem ser geradas 4.294.967.296 matrizes.

Uma técnica um pouco mais eficiente consiste em gerar as linhas (ou as colunas) a priori e gerar linha por linha ao invés de gerar elemento a elemento. Para a função abaixo, onde N=4, deveremos gerar apenas 331.776 matrizes ao invés de 4.294.967.296:

int perm[24][N]={{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},
                 {0,3,1,2},{0,3,2,1},{1,0,2,3},{1,0,3,2},
                 {1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
                 {2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},
                 {2,3,0,1},{2,3,1,0},{3,0,1,2},{3,0,2,1},
                 {3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0}};
void gera(int m[][N], int ordem){
int i,j;
int lin[4];
lin[0]=ordem%24;
lin[1]=ordem/24%24;
lin[2]=ordem/(24*24)%24;
lin[3]=ordem/(24*24*24)%24;
for(i=N-1; i>=0; i--)
    for(j=N-1; j>=0; j--)
      m[N-1-i][j]=perm[lin[i]][j];
}

A indexação acima pode ser simplificada (p.ex. m[N-1-i][j] pode ser substituido por m[i][j]). A forma acima é apenas para tornar a apresentação mais inteligível em termos de “lexicografia”. A geração de matrizes no caso da função acima pode ser entendida como sendo a geração de números de N dígitos onde cada dígito pode ter N! valores. Técnicas mais sofisticadas são necessárias para tratar matrizes maiores.

Sudoku

Um sudoku “clássico” é um quadrado latino 9x9 com restrições adicionais: cada um dos nove quadrados 3x3 devem conter símbolos distintos! Conforme visto acima temos:
5524751496156892842531225600 quadrados latinos; segundo Bertram Felgenhauer and Frazer Jarvis temos:
6670903752021072936960 grades de sudoku; As restrições adicionais reduziram da ordem de 10 elevado a 6!Uma redução da ordem de um milhão!

O programa abaixo verifica as restrições relacionadas ao arranjo 9x9 ser um quadrado latino:
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE !FALSE

int sudokuValido(int s[][9]){
int i,j,k;
int m,n;
int digVisto[10];

for(i=0; i<9; i++){
    for(k=1; k<10; k++) digVisto[k]=FALSE;
    for(j=0; j<9; j++){
      if(digVisto[s[i][j]]){
         printf("Repete o digito %d na linha %d\n", s[i][j],i);
         return FALSE;
      }
      digVisto[s[i][j]]=TRUE;
    }
    for(k=1; k<10; k++) digVisto[k]=FALSE;
    for(j=0; j<9; j++){
      if(digVisto[s[j][i]]){
      printf("Repete o digito %d na coluna %d\n", s[j][i],i);
      return FALSE;
      }
      digVisto[s[j][i]]=TRUE;
    }
}
return TRUE;
}

int main(int argc, char *argv[])
{
    int s[9][9]={{5,3,4,6,7,8,9,1,2},
                 {6,7,2,1,9,5,3,4,8},
                 {1,9,8,3,4,2,5,6,7},
                 {8,5,9,7,6,1,4,2,3},
                 {4,2,6,8,5,3,7,9,1},
                 {7,1,3,9,2,4,8,5,6},
                 {9,6,1,5,3,7,2,8,4},
                 {2,8,7,4,1,9,6,3,5},
                 {3,4,5,2,8,6,1,7,9}};
if(sudokuValido(s))
    printf("sudoku ok!\n");
system("PAUSE");
return 0;
}

Complete o programa acima para verificar se os nove quadrados 3x3 contêm digitos distintos, completando assim a verificação da validade do sudoku. Se depois de insistir (não clique agora!) não conseguir uma boa solução veja esta sugestão.

O programa abaixo mostra uma outra maneira de verificar a unicidade dos elementos das linhas e colunas:
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE !FALSE
int sudokuValido(int s[][9]){
int i,j,k,v;
int m,n;
for(i=0; i<9; i++){
    for(j=0; j<9; j++){
      v=s[i][j];
      for(k=j+1; k<9; k++)
        if(v==s[i][k]){
           printf("Repete o digito %d na linha %d\n", s[i][j],i);
           return FALSE;
        }
  }
    for(j=0; j<9; j++){
      v=s[j][i];
      for(k=j+1; k<9; k++)
        if(v==s[k][i]){
        printf("Repete o digito %d na coluna %d\n", s[j][i],i);
        return FALSE;
        }
    }
}
return TRUE;
}

int main(int argc, char *argv[])
{
    int s[9][9]={{5,3,4,6,7,8,9,1,2},
                 {6,7,2,1,9,5,3,4,8},
                 {1,9,8,3,4,2,5,6,7},
                 {8,5,9,7,6,1,4,2,3},
                 {4,2,6,8,5,3,7,9,1},
                 {7,1,3,9,2,4,8,5,6},
                 {9,6,1,5,3,7,2,8,4},
                 {2,8,7,4,1,9,6,3,5},
                 {3,4,5,2,8,6,1,7,9}};
if(sudokuValido(s))
    printf("sudoku ok!\n");
system("PAUSE");
return 0;
}

Quantas matrizes 3x3 envolvendo os valores de 1 a 9 podem ser construídas? A geração de sudokus a partir da geração de matrizes de quadrados latinos utilizando a geração elemento a elemento é inviável. Teriamos que gerar da ordem de 10 elevado a 77 matrizes. A geração de sudokus a partir de quadrados latinos com geração linha a linha, também é inviável, envolve a geração de 9 elevado a 9!= 362880 matrizes, ou seja “apenas” da ordem de 10 elevado a 50.

Kenken

Um Kenken é um quadrado latino NxN com restrições adicionais: são demarcadas regiões ou gaiolas ou jaulas (cages) (conexas!) e são associadas a estas regiões um valor e uma operação aritmética (a exceção é quando a região consiste de somente uma célula e neste caso existe apenas o valor). Um kenken válido além de obedecer às restrições dos quadrados latinos obedece à restrição de que uma região demarcada deve ter células com valores tais que usando a operação aritmética associada obtem-se o valor associado à região. Invente algumas maneiras de codificar um Kenken.
Observe o exemplo a seguir:

Poderiamos codifica-lo, por exemplo, como sendo um (i)arranjo 4x4 de ints para os valores. As regiões poderiam ser representadas (REP1) na forma de um arranjo contendo identificadores de regiões: int cage[4][4]={{1,1,2,2}, {3,4,4,5},{3,6,7,8},{6,6,7,8}} ou (REP2) na forma de uma lista contendo identificadores de células: 1: {(0,0), (0,1)}, 2: {(0,2), (0,3)}, 3:{(1,0),(2,0)}, 4:{(1,1),(1,2)}, 5:{(1,3)}, 6:{(2,1),(3,0),(3,1)}, 7:{(2,2),(3,2)}, 8:{(2,3),(3,3)}

Faça um programa que transforma um kenken na forma REP1 para a forma REP2

Faça um programa que transforma um kenken na forma REP2 para a forma REP1

Faça um programa que dada uma configuração de kenken ele determina se é uma configuração válida.

Imagine outras representações para o Kenken, quais as vantagens? quais as desvantagens?

Vários programas podem ser feitos explorando problemas simples mas motivadores e que trazem grande aprendizado:

1. Faça programas que aceitem diferentes codificações para configurações do clássico jogo-da-velha e imprimem uma dada configuração. Algumas sugestões de codificação:
char jv[3][3]={“XOO”, “OXX”, “OOX”};
char jv[3][3]={{‘X’,’O’, ‘O’},{‘O’, ‘X’, ‘X.’}, {‘O’, ‘O’, ‘X’}};
int jv[3][3]={{2,1,1},{1,2,2}, {1,1,2}};
int jv[3][3]={{-1,1,1},{1,-1,-1},{1,1,-1}};

2. Faça programas que verifiquem se uma dada configuração de jogo da velha, codificada de alguma forma, é valida, (defina esta “validade estática”). Considere a seguinte codificação:
int jv[3][3]={{-1,0,0},{0,1,0},{0,0,0}};
Nesta codificação uma posição não preenchida do jogo é codificada com o valor int 0, uma opção do jogador

3. Uma outra opção de codificação é codificar a ordem das jogadas de cada jogador. Na codificação abaixo o primeiro jogador tem sua jogadas codificadas com valores negativos, as posições não preenchidas estão codificadas com o valor 0 e as jogadas do segundo jogador estão codificadas com valores positivos:
int jv1[3][3]={{0,0,0},{0,0,0},{0,0,0}};
int jv2[3][3]={{0,0,0},{0,-1,0},{0,0,0}};
int jv3[3][3]={{1,0,0},{0,-1,0},{0,0,0}};
int jv4[3][3]={{1,0,0},{-2,-1,0},{0,0,0}};
int jv5[3][3]={{1,0,0},{-2,-1,2},{0,0,0}};

4. Faça um programa que verifica se uma configuração de jogo-da-velha pode ser a jogada seguinte de uma outra configuração.

5. Faça um programa que gera e imprime quais são as configurações que podem corresponder às jogadas seguintes de uma dada configuração.

6. Vários outros jogos e quebra-cabeças podem ser usados na confecção de programas simples. No jogo “Nurikabe”(haverá discussões à frente na disciplina) você recebe usualmente um tabuleiro quadrado de NxN posições (mas existem nurikabes de tamanho NxM). Em algumas posições existem números maiores ou iguais a 1. Estes números especificam o número de posições do tabuleiro que não devem ser cobertas com blocos de cobertura (BC) seguindo algumas regras: (i)os BCs não podem formar áreas maiores que 2x2 e de um BC você deve poder ir até outro BC qualquer através de conexões laterais (não vale diagonais!), as posições de áreas não cobertas devem ter contiguidade lateral (não vale conexão pelas diagonais!).
Considere a seguinte codificação de um jogo de Nurikabe em um tabuleiro 5x5:
int nurikabe[5][5]={{3,0,0,0,2},{0,0,0,0,0},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
Nesta codificação os números maiores que zero representam o número de posições que não devem ser cobertas e os zeros representam as posições que podem ou não cobertas.
uma solução para esta instância é:
int solucao[5][5]={{3,0,0,-1,2}, {-1,-1,-1,-1,0}, {2,-1,0,4,-1},{0,-1,0,0,-1}, {-1,-1,-1,-1,-1}};
Nesta codificação as posições que foram cobertas são indicadas através do valor -1
Faça um programa que testa se uma dada configuração é solução para uma instância de nurikabe.

7. Faça um programa que gera “algumas” configurações iniciais para uma dada solução de Nurikabe. Por exemplo, para a solução apresentada anteriormente:
int solucao[5][5]={{3,0,0,-1,2}, {-1,-1,-1,-1,0}, {2,-1,0,4,-1},{0,-1,0,0,-1}, {-1,-1,-1,-1,-1}};
podemos ter as seguintes configurações iniciais (além da apresentada):
int nurikabe[5][5]={{0,3,0,0,2},{0,0,0,0,0},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
int nurikabe[5][5]={{0,0,3,0,2},{0,0,0,0,0},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
int nurikabe[5][5]={{3,0,0,0,0},{0,0,0,0,2},{2,0,0,4,0},{0,0,0,0,0},{0,0,0,0,0};
int nurikabe[5][5]={{0,0,3,0,0},{0,0,0,0,2},{0,0,0,0,0},{2,0,4,0,0},{0,0,0,0,0};

8. Faça um programa que dado um arranjo representando uma configuração de minas no estilo do jogo “varrendo as minas” ele gera os números de 0 a 8 que representam o número de minas que circundam uma dada posição. Assim, dada uma área retangular onde as minas são representadas pelo número 9:
****9**
**9***9
9999***
99*9**9
*999**9
(o asterisco * representa posições que não são minas!) deverá ser gerada a matriz:
0112911
2494129
9999222
9989329
3999229

Considere um arranjo 2x2x2 contendo 8 elementos com os valores 1,2,3,4,5,6,7,8; Dê a definição e inicialização na linguagem C deste arranjo tal que as linhas (saguão) sejam (1,2) (3,4), (5,6) e (7,8), as colunas (torres) sejam (1,3), (2,4), (5,7) e (6,8) e as profundidades (corredores) sejam (1,5), (2,6), (3,7) e (4,8).

O jogo “Mastermind” tem grande número de variantes. A variante mais “tradicional” corresponde a 6 objetos distintos devem ser escolhidos 4 deles e a resposta a uma tentativa de advinhar a escolha consiste em dois componentes: (i) número de objetos corretos na posição correta e (ii) número de objetos corretos na posição incorreta. Considere que os seis objetos possíveis são os valores 0,1,2,3,4 e 5; considere que a escolha foi 0112 (dentre as 6x6x6x6=1296 possíveis). A resposta pode ser codificada em um número de dois dígitos onde a unidade corresponde aos objetos corretos na posição incorreta e a dezena corresponde aos objetos corretos na posição correta.

Faça um programa que examina o espaço de soluções do jogo mastermind. Qual a melhor estratégia para a primeira jogada? Existem basicamente somente 5 tipos de escolhas iniciais 0000, 0001, 0011, 0012, 0123!

Verifique se a distribuição dos valores de respostas para a primeira tentativa na tabela abaixo estão corretos:

Resp		0000	0001	0011	0012	0123
0	00	625	256	256	81	16
1	01	0	308	256	276	152
2	10	500	317	256	182	108
3	02	0	61	96	222	312
4	11	0	156	208	230	252
5	20	150	123	114	105	96
6	03	0	0	16	44	136
7	12	0	27	36	84	132
8	21	0	24	32	40	48
9	30	20	20	20	20	20
10	04	0	0	1	2	9
11	13	0	0	0	4	8
12	22	0	3	4	5	6
13	40	1	1	1	1	1

Observe que a escolha com “menor máximo”é 0011 ! (retirado de http://www.tnelson.demon.co.uk/mastermind/).