6

Possuo o seguinte código escrito em C:

#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 linha_inicio, linha_final, coluna_inicio, coluna_final;

    if(quadrante >= 0 && quadrante <= 2) {
        linha_inicio = 0;
    } else if(quadrante >= 3 && quadrante <= 5) {
        linha_inicio = 3;
    } else {
        linha_inicio = 6;
    }

    if(quadrante == 0 || quadrante == 3 || quadrante == 6) {
        coluna_inicio = 0;
    } else if(quadrante == 1 || quadrante == 4 || quadrante == 7) {
        coluna_inicio = 3;
    } else {
        coluna_inicio = 6;
    }

    linha_final = linha_inicio + 2;
    coluna_final = coluna_inicio + 2;

    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) {
                return 1;
            }
        }
    }

    return 0;
}

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

    return 0;
}

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

    return 0;
}

// função para ordenar os itens do vetor de maneia aleatória
void permutacaoAleatoria(int v[]) {
    int randomico, auxiliar;

    for (int k = 8; k > 0; k--) {
        randomico = rand() % 8 + 0;

        auxiliar = v[k];

        v[k] = v[randomico];
        v[randomico] = auxiliar;
    }
}

void func_numeros() {
    // Preenchendo todo o tabuleiro (quadrante por quadrante)
    for(int numeros_quadrante = 0; numeros_quadrante < 9; numeros_quadrante++) {
        int linha_inicio, coluna_inicio, linha_final, coluna_final;
        int numero_novo;

        if(numeros_quadrante >= 0 && numeros_quadrante <= 2) {
            linha_inicio = 0;
        } else if(numeros_quadrante >= 3 && numeros_quadrante <= 5) {
            linha_inicio = 3;
        } else {
            linha_inicio = 6;
        }

        if(numeros_quadrante == 0 || numeros_quadrante == 3 || numeros_quadrante == 6) {
            coluna_inicio = 0;
        } else if(numeros_quadrante == 1 || numeros_quadrante == 4 || numeros_quadrante == 7) {
            coluna_inicio = 3;
        } else {
            coluna_inicio = 6;
        }

        linha_final = linha_inicio + 2;
        coluna_final = coluna_inicio + 2;

        int nums[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

        permutacaoAleatoria(nums);

        for(int l_i = linha_inicio; l_i <= linha_final; l_i++) {
            for(int c_i = coluna_inicio; c_i <= coluna_final; c_i++) {
                int verifica_quadrante = 1;
                int verifica_linha = 1;
                int verifica_coluna = 1;

                int numero_novo;
                int numero_posicao = -1;

                while(verifica_quadrante == 1 || verifica_linha == 1 || verifica_coluna == 1) {
                    numero_posicao++;

                    if(numero_posicao > 8) {
                        for(int hey = linha_inicio; hey <= linha_final; hey++) {
                            for(int how = coluna_inicio; how <= coluna_final; how++) {
                                jogo_tabuleiro[hey][how] = 0;
                            }
                        }

                        numero_posicao = 0;

//                      l_i = linha_inicio;
//                      c_i = coluna_inicio;
                    }

                    verifica_quadrante = func_quadrante(numeros_quadrante, nums[numero_posicao]);
                    verifica_linha = func_linha(l_i, nums[numero_posicao]);
                    verifica_coluna = func_coluna(c_i, nums[numero_posicao]);

                    numero_novo = numero_posicao;
                }

                jogo_tabuleiro[l_i][c_i] = nums[numero_novo];
            }
        }   
    }
}

void func_tabuleiro() {
    func_numeros();

    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). O que eu fiz foi: estou preenchendo quadrante por quadrante, assim posso verificar os quadrantes anteriores podendo evitar o preenchimento da unidade 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 no seguinte while:

while(verifica_quadrante == 1 || verifica_linha == 1 || verifica_coluna == 1) {
    numero_posicao++;

    if(numero_posicao > 8) {
        for(int hey = linha_inicio; hey <= linha_final; hey++) {
            for(int how = coluna_inicio; how <= coluna_final; how++) {
                jogo_tabuleiro[hey][how] = 0;
            }
        }

        numero_posicao = 0; // setando posição inicial (para não pegar lixo)

//      l_i = linha_inicio;
//      c_i = coluna_inicio;
    }

    verifica_quadrante = func_quadrante(numeros_quadrante, nums[numero_posicao]);
    verifica_linha = func_linha(l_i, nums[numero_posicao]);
    verifica_coluna = func_coluna(c_i, nums[numero_posicao]);

    numero_novo = numero_posicao;
}

Na verificação acima eu verifico se o número já existe em alguma das áreas (linha, coluna ou quadrante) e se existir ele incrementa a variável numero_posicao para pegar o próximo número do vetor e verificar se ele pode ser adicionado à matriz, se sim ele é adicionado, se não o loop se repete. Estou utilizando a verificação if(numero_posicao > 8), pois isso significa que, se for maior que 8, é porque nenhum dos números pode ser adicionado naquela posição, ou seja, entrou em um "beco sem saída", quando isso ocorre, eu zero o quadrante jogo_tabuleiro[hey][how] = 0; e tento l_i = linha_inicio; c_i = coluna_inicio; para ele preencher novamente o quadrante atual, porém quando tento dessa maneira o programa entra em loop infinito (por isso as duas linhas estão comentadas). Como resolver isso e preencher o tabuleiro corretamente?

3
  • 1
    Olha, não estou com muito tempo hoje para ver o seu caso, mas me interessei por ele. Vou começar com a seguinte dica para simplificar bastante o seu código: int linha_inicio = (quadrante / 3) * 3; int linha_final = linha_inicio + 2; int coluna_inicio = quadrante % 3; int coluna_final = coluna_inicio + 2; Commented 28/06/2016 às 7:03
  • @VictorStafusa obrigado pela atenção, atualizei o código onde simplifiquei a área da qual vc se refere (adicionei também numero_posicao = 0 dentro do while). Não utilizei seu código pq, por exemplo, se o quadrante fosse 2 (último da primeira linha de quadrantes), então linha_inicio deveria ser 0 e usando a sua conta linha_inicio = (quadrante / 3) * 3 o resultado da linha_inicio para esse quadrante seria 2... Obrigado novamente pela sugestão!
    – Igor
    Commented 28/06/2016 às 16:47
  • é que linha_inicio = (quadrante / 3) * 3 resulta em [0, 0, 0, 3, 3, 3, 6, 6, 6]. O motivo disso é que a divisão de inteiros é uma divisão inteira, e portanto o 1/3 ou 2/3 que resultaria na divisão exata são descartados. Quanto as colunas, seria int coluna_inicio = (quadrante % 3) * 3, que resulta em [0, 3, 6, 0, 3, 6, 0, 3, 6]. Commented 28/06/2016 às 18:15

1 Resposta 1

3

Este método se trata de um algoritmo de força bruta.

A vantagem desse algoritmo é a simplicidade e sua desvantagem está no tempo de processamento.

Logo, este método é usado quando a simplicidade de implementação é mais importante que a velocidade.

O algoritmo navega entre as células vazias em uma determinada ordem, preenchendo sequencialmente os números a partir das opções disponíveis, OU retrocede, removendo as numerações incorretas quando o preenchimento da célula não for possível.

Segue abaixo a descrição de um algoritmo de força bruta para solucionar o Sodoku:

1 - Comece com a primeira célula livre;

2 - Preencha a célula com um dos possíveis números que não violam as regras do Sodoku. Se você chegar em um impasse que impossibilite o preenchimento da célula conforme as regras, vá para o passo 4. Caso contrário, continue no passo 3;

3 - Mova-se para o próxima célula e vá para o passo 2;

4 - Volte para a célula anterior. Selecione outro número e preencha a célula. Vá para o passo 3;

5 - Continue repetindo os passos até que todas as células vazias estejam preenchidas.

Seguem alguns links interessantes:

Wikipedia (Inglês): https://en.wikipedia.org/wiki/Sudoku_solving_algorithms

Código Exemplo (github): https://gist.github.com/oni64/5176102

Espero ter ajudado.

1
  • Obrigado pelas instruções, mas esses 5 passos eu já estou aplicando no meu algoritmo, não estou?
    – Igor
    Commented 28/06/2016 às 16:56

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 .