Avançar para o conteúdo principal

Game of 15

Toda a gente conhece o jogo de puzzle em que existe um espaço livre para mover as peças para os lugares certos. Para quem não conhece pode sempre clicar aqui.

Imagem da wikipedia

Hoje vamos resolver o jogo em C.



Para começar utilizamos uma matriz 4x4 para o jogo.

int jogo[4][4];

Além desta matriz vamos definir outra para armazenar a solução do jogo.

int solucao[4][4];

Antes de mais nada criamos uma função para limpar e preparar a matriz de jogo e a matriz da solução:

//prepara a matriz do jogo
void limpar(void)
{
int l,c,conta=1;

    n_jogadas=0;
    for(l=0;l<4;l++){
        for(c=0;c<4;c++){
            jogo[l][c]=conta;
            solucao[l][c]=conta;
            conta++;
        }
    }
    jogo[3][3]=0;
    solucao[3][3]=0;
}

Também precisamos de uma função para mostrar o estado da matriz do jogo, assim:

//mostra a matriz do jogo
void mostrar(void)
{
int l,c;
    system("cls");
    for(l=0;l<4;l++){
        for(c=0;c<4;c++){
            if(jogo[l][c]>0){
                goto_xy(10+c*3,10+l*2);
                printf("%d",jogo[l][c]);
            }
        }
    }
}

Esta função utiliza a instrução goto_xy que não existe em C mas que está definida num header file que acompanha o código fonte do projeto.

Com as duas matrizes é fácil saber se o jogo foi resolvido, basta comparar as posições de uma matriz com a outra:

//terminou?!
int resolvido(void)
{
int l,c,r=1;
    for(l=0;l<4;l++){
        for(c=0;c<4;c++){
            if(solucao[l][c]!=jogo[l][c]) r=0;
        }
    }
    return r;
}

Como queremos que o computador resolva o jogo vamos utilizar uma tática simples, sempre que fizermos uma jogada guardamos o movimento realizado para mais tarde podermos reverter todos os movimentos até à posição inicial da matriz. Para isso vamos ter um vetor onde guardamos as jogadas e uma variável com o número de jogadas feitas.


int jogadas[100];
int n_jogadas;

Agora as funções que implementam as jogadas:


//move uma peça para a direita
void mover_direita(void)
{
int l,c;
int temp;

    pos_livre(c,l);
    if(coord_validas(c-1,l)==0) return;
    temp=jogo[l][c-1];
    jogo[l][c]=temp;
    jogo[l][c-1]=0;
    //guarda a jogada
    jogadas[n_jogadas]=DIREITA;
    n_jogadas++;
}
//move uma peça para a esquerda
void mover_esquerda(void)
{
int l,c;
int temp;

    pos_livre(c,l);
    if(coord_validas(c+1,l)==0) return;
    temp=jogo[l][c+1];
    jogo[l][c]=temp;
    jogo[l][c+1]=0;
    //guarda a jogada
    jogadas[n_jogadas]=ESQUERDA;
    n_jogadas++;
}
//move uma peça para cima
void mover_baixo(void)
{
int l,c;
int temp;

    pos_livre(c,l);
    if(coord_validas(c,l-1)==0) return;
    temp=jogo[l-1][c];
    jogo[l][c]=temp;
    jogo[l-1][c]=0;
    //guarda a jogada
    jogadas[n_jogadas]=BAIXO;
    n_jogadas++;
}
//move uma peça para baixo
void mover_cima(void)
{
int l,c;
int temp;

    pos_livre(c,l);
    if(coord_validas(c,l+1)==0) return;
    temp=jogo[l+1][c];
    jogo[l][c]=temp;
    jogo[l+1][c]=0;
    //guarda a jogada
    jogadas[n_jogadas]=CIMA;
    n_jogadas++;
}

Cada uma destas funções utiliza o seguinte algoritmo:
1. Descobrir as coordenadas do espaço livre na matriz (função pos_livre, apresentada a seguir)
2. Se as coordenadas do movimento não são válidas (função coord_validas, apresentada a seguir) não joga.
3. Guarda o número da peça a mover e troca com o 0 (zero) do espaço livre.
4. Guarda a jogada feita para mais tarde poder voltar atrás.
5. Adiciona um à variável n_jogadas.


//procura a posicao livre
void pos_livre(int &x,int &y)
{
int l,c;

    for(l=0;l<4;l++){
        for(c=0;c<4;c++){
            if(jogo[l][c]==0){
                x=c;
                y=l;
                return;
            }
        }
    }
}
//devolve 0 se as coordenadas estão fora da matriz
//devolve 1 se as coordenadas são válidas
int coord_validas(int x,int y)
{
    if(x<0 || y<0) return 0;
    if(x>3 || y>3) return 0;
    return 1;
}

Para terminar o programa faltam duas funções, uma para baralhar o puzzle e outra para resolver.
Aqui ficam:

//resolve o jogo
void resolver(void)
{
int n;

    for(n=n_jogadas-1;n>=0;n--){
        if(jogadas[n]==ESQUERDA) mover_direita();
        if(jogadas[n]==DIREITA) mover_esquerda();
        if(jogadas[n]==CIMA) mover_baixo();
        if(jogadas[n]==BAIXO) mover_cima();
        mostrar();
        Sleep(50);
    }
}
//baralha
void baralhar(void)
{
int movimento,temp,sorteia;
    srand(time(NULL));
    for(temp=0;temp<50;temp++){
        mostrar();
        Sleep(50);
        sorteia=rand()%4+1;
        switch(sorteia){
            case ESQUERDA :
                            mover_esquerda();
                            break;
            case DIREITA :
                            mover_direita();
                            break;
            case CIMA :
                            mover_cima();
                            break;
            case BAIXO :
                            mover_baixo();
                            break;
        }
    }
}

Esta versão da função baralhar mostra as jogadas ao mesmo tempo que baralha isso pode ser alterado removendo a linha que chama a função mostrar().

Agora para terminar de verdade aqui fica a função main:

int main(int argc,char *argv[])
{
char op;

    limpar();
    baralhar();
    while(1){
        mostrar();
        printf("\n\n\nOpcao (e,d,c,b,r):");
        scanf("%c",&op);
        if(op=='e') mover_esquerda();
        if(op=='d') mover_direita();
        if(op=='c') mover_cima();
        if(op=='b') mover_baixo();
        if(op=='r') resolver();
        if(resolvido()) break;
    }
    mostrar();
    system("pause");
    return 1;
}

Aqui chegados só falta jogar e quando não conseguir resolver o puzzle basta escolher r.

O código fonte.







Comentários

Mensagens populares deste blogue

Vamos fazer um carro com o Unity 3D

Neste artigo vamos fazer um carro, simples, com o Unity 3D. A ideia é utilizar o motor de física do Unity 3D para simular o comportamento do carro. Os passos a seguir são: [1] - Criar um projeto novo

C# IEnumerable e IEnumerator

Neste artigo vamos aprender como utilizar a interface IEnumerator por forma a permitir utilizar um ciclo foreach num conjunto ou coleção de dados. A maior parte das coleções (listas e outras) já implementam a interface, mas neste caso vamos personalizar a maneira como percorremos a lista. Quando utilizamos código assim: foreach(Class c in Collection) { ... } O compilador converte este código em algo assim: IEnumerator cc = Collection.GetEnumerator() while(cc.MoveNext()) { c=(Class)cc.Current; ... } Ao implementar a interface IEnumerable significa que a classe implementa uma versão da função GetEnumerator() que deve devolver uma classe que implemente a interface IEnumerator. Vamos explorar um exemplo. Começamos pela classe client Esta classe permitirá guardar os dados dos clientes, existindo um campo para indicar se o cliente ainda está ativo ou não. De seguida temos uma classe que define uma lista de clientes e que implementa a interface IEnumerable que de

React - Introdução

 Neste post vamos fazer uma breve introdução ao React. React é uma framework javascript e por isso é importante ter conhecimentos desta linguagem de programação para melhor compreender o seu funcionamento. O que é necessário? Para construir páginas com React é necessário ter instalado a framework Node e o seu instalador de packages o npm. Com o Node instalado basta abrir uma janela da linha de comandos, eu aconselho utilizar o novo Windows Terminal ou o Cmder . Na sua linha de comando escolhida execute o comando: npx create-react-app Tutorial01 Este comando vai criar uma pasta com o nome Tutorial01 e instalar dos os ficheiros necessários para construir a sua primeira aplicação React dentro dessa pasta. De seguida entramos na pasta criada com o comando: cd Tutorial01 E iniciamos a aplicação com o comando: npm start Deve conseguir ver uma página com o seguinte aspeto: A partir daqui, até fechar a linha de comando, todas as alterações feitas aos ficheiros da sua aplicação são automaticam