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.