-1

Possuo o seguinte código em C:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Variáveis globais
int jogo_tabuleiro[9][9] = {0};

int func_quadrante(int quadrante, int numero) {
    int retorno_quadrante = 0;
    int linha_inicio, linha_final, coluna_inicio, coluna_final;

    if(quadrante == 0) {
        linha_inicio = 0;
        coluna_inicio = 0;

        linha_final = 2;
        coluna_final = 2;
    } else if(quadrante == 1) {
        linha_inicio = 0;
        coluna_inicio = 3;

        linha_final = 2;
        coluna_final = 5;
    } else if(quadrante == 2) {
        linha_inicio = 0;
        coluna_inicio = 6;

        linha_final = 2;
        coluna_final = 8;
    } else if(quadrante == 3) {
        linha_inicio = 3;
        coluna_inicio = 0;

        linha_final = 5;
        coluna_final = 2;
    } else if(quadrante == 4) {
        linha_inicio = 3;
        coluna_inicio = 3;

        linha_final = 5;
        coluna_final = 5;
    } else if(quadrante == 5) {
        linha_inicio = 3;
        coluna_inicio = 6;

        linha_final = 5;
        coluna_final = 8;
    } else if(quadrante == 6) {
        linha_inicio = 6;
        coluna_inicio = 0;

        linha_final = 8;
        coluna_final = 2;
    } else if(quadrante == 7) {
        linha_inicio = 6;
        coluna_inicio = 3;

        linha_final = 8;
        coluna_final = 5;
    } else if(quadrante == 8) {
        linha_inicio = 6;
        coluna_inicio = 6;

        linha_final = 8;
        coluna_final = 8;
    }

    for(int l_i = linha_inicio; l_i <= linha_final; l_i++) {
        for(int c_i = coluna_inicio; c_i <= coluna_final; c_i++) {
            if(jogo_tabuleiro[l_i][c_i] == numero) {
                retorno_quadrante = 1;
            }
        }
    }

    return retorno_quadrante;
}

int func_linha(int linha, int numero) {
    int retorno_linha = 0;

    for(int c = 0; c < 9; c++) {
        if(jogo_tabuleiro[linha][c] == numero) {
            retorno_linha = 1;
        }
    }

    return retorno_linha;
}

int func_coluna(int coluna, int numero) {
    int retorno_coluna = 0;

    for(int l = 0; l < 9; l++) {
        if(jogo_tabuleiro[l][coluna] == numero) {
            retorno_coluna = 1;
        }
    }

    return retorno_coluna;
}

void func_numeros(int numeros_quadrante) { 
    // Preenchendo todo o tabuleiro (quadrante por quadrante)
    int linha_inicio, coluna_inicio, linha_final, coluna_final;
    int quadrante_tabuleiro = numeros_quadrante;
    int numero_novo;

    if(quadrante_tabuleiro == 0) {
        linha_inicio = 0;
        coluna_inicio = 0;

        linha_final = 2;
        coluna_final = 2;
    } else if(quadrante_tabuleiro == 1) {
        linha_inicio = 0;
        coluna_inicio = 3;

        linha_final = 2;
        coluna_final = 5;
    } else if(quadrante_tabuleiro == 2) {
        linha_inicio = 0;
        coluna_inicio = 6;

        linha_final = 2;
        coluna_final = 8;
    } else if(quadrante_tabuleiro == 3) {
        linha_inicio = 3;
        coluna_inicio = 0;

        linha_final = 5;
        coluna_final = 2;
    } else if(quadrante_tabuleiro == 4) {
        linha_inicio = 3;
        coluna_inicio = 3;

        linha_final = 5;
        coluna_final = 5;
    } else if(quadrante_tabuleiro == 5) {
        linha_inicio = 3;
        coluna_inicio = 6;

        linha_final = 5;
        coluna_final = 8;
    } else if(quadrante_tabuleiro == 6) {
        linha_inicio = 6;
        coluna_inicio = 0;

        linha_final = 8;
        coluna_final = 2;
    } else if(quadrante_tabuleiro == 7) {
        linha_inicio = 6;
        coluna_inicio = 3;

        linha_final = 8;
        coluna_final = 5;
    } else if(quadrante_tabuleiro == 8) {
        linha_inicio = 6;
        coluna_inicio = 6;

        linha_final = 8;
        coluna_final = 8;
    }

    for(int l_i = linha_inicio; l_i <= linha_final; l_i++) {
        for(int c_i = coluna_inicio; c_i <= coluna_final; c_i++) {
            numero_novo = rand() % 9 + 1;

            int verifica_quadrante = func_quadrante(quadrante_tabuleiro, numero_novo);
            int verifica_linha = func_linha(l_i, numero_novo);
            int verifica_coluna = func_coluna(c_i, numero_novo);

            if(verifica_quadrante == 1 || verifica_linha == 1 || verifica_coluna == 1) {
                c_i -= 1;
            } else {
                jogo_tabuleiro[l_i][c_i] = numero_novo;
            }
        }
    }
}

void func_tabuleiro() {
    for(int sla = 0; sla < 9; sla++) {
        func_numeros(sla);
    }

    printf("|=================================|\n| - | 1  2  3 | 4  5  6 | 7  8  9 |\n|=================================|\n");

    for(int linha = 0; linha < 9; linha++) {
        if(linha == 3 || linha == 6) {
            printf("|   |---------+---------+---------|\n");
        }

        for(int coluna = 0; coluna < 9; coluna++) {
            if(coluna == 0) {
                printf("| %d |", linha + 1);
            }

            if(jogo_tabuleiro[linha][coluna] == 0) {
                printf("   ");
            } else {
                printf(" %d ", jogo_tabuleiro[linha][coluna]);
            }

            if(coluna == 2 || coluna == 5) {
                printf("|");
            }

            if(coluna == 8)  {
                printf("|\n");
            }
        }

        if(linha == 8) {
            printf("|=================================|\n");
        }
    }
}

main() {
    srand(time(NULL)); // Inicializando função rand

    func_tabuleiro();
}

O meu objetivo é de preencher e resolver todo o tabuleiro seguindo as regras do jogo, ou seja, um número (de 1 a 9) não pode se repetir na mesma linha, coluna ou quadrante (3 por 3). Seguindo a minha lógica, era para estar funcionando, porém ele nunca resolve "de primeira" e na maioria das vezes entra em loop infinito. O que eu fiz foi: estou preenchendo quadrante por quadrante, assim posso verificar os quadrantes anteriores podendo evitar o preenchimento da matriz com números repetidos. Então criei três funções, uma para verificar se o número gerado já existe em um quadrante, outra para verificar a linha e a outra para coluna (cada uma retorna 1 se o número existir e 0 se não existir) e utilizo o retorno delas na seguinte verificação:

if(verifica_quadrante == 1 || verifica_linha == 1 || verifica_coluna == 1) {
    c_i -= 1;
} else {
    jogo_tabuleiro[l_i][c_i] = numero_novo;
}

Na condição acima eu verifico se o número já existe em alguma das áreas (quadrante, linha ou coluna), se o número existir ele decrementa do for referente à coluna e se não existir ele adiciona o número na matriz, ou seja, esse loop vai se repetir até ser gerado um número que não exista em nenhuma das áreas.

Estou utilizando o seguinte for dentro da função func_tabuleiro:

for(int sla = 0; sla < 9; sla++) {
    func_numeros(sla);
}

O código acima serve para ir preenchendo os nove quadrantes da matriz, quadrante por quadrante e após esse for eu apenas desenho o tabuleiro.

Assim como disse anteriormente, na maioria das vezes ele entra em loop infinito, ou seja, preciso recompilar o código várias vezes até ele conseguir gerar o tabuleiro. Abaixo está o resultado do máximo de quadrantes que ele consegue preencher (8) após várias recompilações do código (com o valor for(int sla = 0; sla < 8; sla++)), < 8 porque esse é o máximo que ele consegue, se eu alterar para < 9, ou seja, para preencher tudo, ele sempre fica em loop infinito (mesmo re-executando o código múltiplas vezes).

Máximo que consegue preencher

Como corrigir esse loop infinito para que o tabuleiro/matriz possa ser sempre preenchida da maneira correta logo na primeira execução?

6
  • 1
    Bom, eu não entendo a sua lógica, mas há mesmo algum potencial para entrar em loop infinito ai justamente porque você decrementa a variável c_i . Esse decremento não faz muito sentido pra mim (você poderia tentar explicá-lo?). Num cenário em que o seu valor acabou de se tornar n, por exemplo, esse decremento o faz se tornar n-1 justamente antes de retornar ao laço - que vai fazer o valor voltar a n! Qual é o objetivo disso? 19/06/2016 às 22:51
  • 1
    Outro problema potencialmente grave do seu código é que a escolha dos números é aleatória. Isso faz com que o seu algoritmo não seja determinístico, e por isso possa demorar muuuiiiitooo tempo (e parecer ser um loop infinito mesmo que não seja). Por exemplo, se as chamadas de rand() ficarem gerando 3, 7, 9, 3, 7, 9, 3, 7, 9, 3, 7, 9,... o seu algoritmo nunca irá terminar! Se a sua escolha de algoritmo é essa, o mais indicado é você usar uma lista com os números de 0 a 9 e ir removendo os utilizados da lista. 19/06/2016 às 22:54
  • Então, @LuizVieira, eu utilizo o decremento na variável c_i para ele repetir o laço até ele gerar um número inexistente no quadrante, linha ou coluna para assim poder adicionar ele à matriz. Sobre a aleatoriedade, poderia explicar melhor essa lista de números (1 a 9)? Pois gostaria que fosse o mais aleatório possível...
    – Igor
    19/06/2016 às 23:34
  • Bom, se você precisa repetir mantendo o controle da variável c_i, deveria preferencialmente utilizar um while ao invés de um for. Como eu disse, há ai um potencial para loop infinito, não tô dizendo que é necessariamente o problema. De fato, o problema mais seguramente está na aleatoriedade. O que eu sugeri é você criar uma lista (em C um vetor mesmo serve) com os números de 0 a 9, organizá-los aleatoriamente (leia sobre permutação aleatória e dê uma olhada no último exemplo dessa página) e então ir utilizando-os um a um. 20/06/2016 às 0:07
  • Poderia dar um exemplo de como utilizar o while? Pois estou utilizando o for para poder inserir o número gerado na posição correta... Em relação à permutação aleatória, devo utilizar ela pela possibilidade do rand() gerar números iguais mesmo aleatoriamente?
    – Igor
    20/06/2016 às 0:16

1 Resposta 1

4

Eu não analisei todo o código para ver se há outros problemas. Mas um potencial problema do seu código é que você faz o seguinte no trecho que faz a tentativa de montar cada coluna/linha (os dois for encadeados na chamada de func_numeros):

  1. Sorteia um número aleatoriamente entre 0 e 9.
  2. Procura se o número sorteado já foi utilizado.
  3. Se o número sorteado ainda não foi utilizado, utiliza-o (e pula pro passo 5).
  4. Se o número sorteado já foi utilizado, volta ao passo 1.
  5. Continua o programa...

Bom, o princípio de um sorteio aleatório é que ele é... aleatório! Não há garantia de que você terá sempre números distintos. É uma questão de estatística elementar: todos os números no intervalo do sorteio têm a mesma probabilidade de ser sorteados a cada novo sorteio!

Por exemplo, você faz um sorteio e tira o número 3 (ele tem 10% de chance de ser sorteado, já que o intervalo é de 0 a 9). No próximo sorteio, a chance de tirar o número 3 novamente é: 10%! Tá certo que todos os outros números têm, juntos, 90% de chance de serem sorteados. Mas ainda existe a chance de sair o 3.

Veja esse exemplo de código no Ideone que gera 100 números aleatórios entre 0 e 9. Eu testei uma vez e obtive o seguinte resultado:

1 7 3 7 4 7 5 9 7 7 4 0 6 0 4 9 3 8 0 2 6 1 6 6 9 6 4 5 3 1 5 5 8 8 2 2 6 7 2 4 5 6 5 2 7 9 2 0 8 2 3 4 4 9 1 3 6 6 9 9 7 5 4 6 3 6 9 0 4 1 4 0 8 9 2 5 9 4 6 7 6 0 2 1 0 3 4 6 9 4 5 7 9 0 3 3 7 2 3 1

Pode-se observar, em negrito nessas 100 chamadas de exemplo, que foi necessário gerar 20 números (o dobro do necessário!) para que todos os números fossem obtidos (o último foi o número 2). Observe quantas vezes o número 7 foi produzido desnecessariamente.

Assim, esse seu algoritmo essencialmente funciona, mas ele tem um problema grave. Como você sorteia um novo número sem considerar os que já foram utilizados, o seu programa pode demorar muito, e esse muito pode ser mesmo tendendo ao infinito (ou ser suficientemente grande para te dar a impressão de que travou em loop). Pode parecer bobagem ou perfeccionismo se preocupar com esse repetições de números em um intervalo tão pequeno (0 a 9), mas se você considerar que o seu algoritmo procura se o número já existe na seção, na linha e na coluna, o custo computacional de fazer a busca por um número já sorteado fica bem caro.

A solução ideal então é que antes de iniciar esses cálculos (o seu laço for duplo), você monte uma lista com os números de 0 a 9, sorteie a ordem que eles ficarão (isto é chamado de permutação aleatória) e então vá utilizando um por um, removendo o número utilizado da lista (pode usar uma estrutura de dados de pilha, por exemplo).

Um exemplo de código que faz permutação aleatória em um vetor é esse:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int randomInteger(int low, int high)
{
    int k;
    double d;
    d = (double)rand() / ((double)RAND_MAX + 1);
    k = (int) (d * (high - low + 1));
    return low + k;
}

void permutacaoAleatoria(int v[], int n) {
    int r, k, t;
    for (k = n - 1; k > 0; k--) {
        r = randomInteger(0, k);
        t = v[k], v[k] = v[r], v[r] = t;
    }
}

void randomize()
{
    srand(time(NULL));
}

int main() {

    int nums[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    randomize();
    permutacaoAleatoria(nums, 10);
    int i;
    printf("Valores no vetor: [");
    for (i = 0; i < 10; i++)
        printf("%s%d", (i != 0 ? ", " : ""), nums[i]);
    printf("]");
    return 0;
}

Ele foi baseado nos exemplos dessa página. Veja executando no Ideone.

2
  • Obrigado pela resposta, fiz as mudanças no meu código em relação ao while e a permutação, porém agora o erro que ocorre é: ele preenche todo o tabuleiro, mas quando chega em uma posição em que o número não pode ser preenchido ele preenche com lixo e se eu prevenir esse lixo (vindo da nums[]) somente o último quadrante é preenchido... Devo criar outra pergunta para o meu problema ou editar a atual?
    – Igor
    24/06/2016 às 22:30
  • Olá Igor. Por nada. Crie outra pergunta. Este site não é um fórum. :) Lembre-se de adicionar na sua outra pergunta os trechos relevantes de código. Ah, e se essa resposta lhe foi útil, por favor considere marcá-la como aceita. 24/06/2016 às 23:01

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .