Game resolution Sudoku giving infinite loop in C

Navigation
-1

I have the following code in 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();
}

My goal is to complete and solve the entire board by following the rules of the game, ie a number (from 1 to 9) can not be repeated in the same row, column or quadrant (3 by 3). Following my logic, it was supposed to be working, however it never solved "first" and most of the time it goes into infinite loop. What I did was: I am filling quadrant by quadrant, so I can check the previous quadrants and avoid filling the matrix with repeated numbers. So I created three functions, one to check if the number generated already exists in one quadrant, another to check the line and the other one to column (each one returns 1 if the number exists and 0 if it does not exist) and I use their return in the following verification: 

if(verifica_quadrante == 1 || verifica_linha == 1 || verifica_coluna == 1) {
    c_i -= 1;
} else {
    jogo_tabuleiro[l_i][c_i] = numero_novo;
}
In the above condition I check if the number already exists in any of the areas (quadrant, row or column), if the number exists it decrements from for referring to the column and if it does not exist it adds the number in the matrix, or this loop will repeat itself until a number is generated that does not exist in any of the areas.

I'm using the following for within the func_tabuleiro function: 

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

The above code serves to fill the nine quadrants of the matrix, quadrant by quadrant and after that for I just draw the board.

As I said earlier, most of the time it goes into an infinite loop, that is, I need to recompile the code several times until it manages to generate the board. Below is the result of the maximum number of quadrants that it can populate (8) after multiple code recompilations (with for(int sla = 0; sla < 8; sla++) ), < 8 because that is the maximum it can achieve, if I change to < 9 , or

How to correct this infinite loop so that the board / matrix can always be filled in the correct way when it is first run?

    
asked by anonymous 20.06.2016 / 00:00

1 answer

4

I have not analyzed all the code to see if there are other problems. But a potential problem with your code is that you do the following in the snippet that attempts to mount each column / row (the two for threaded in the func_numeros call):

  • Sorts a random number between 0 and 9.
  • Search if the number you've drawn has already been used.
  • If the number drawn has not yet been used, use it (and jump to step 5).
  • If the number drawn has already been used, return to step 1.
  • Continue the program ...

    • Well, the principle of a random draw is that it is ... random! There is no guarantee that you will always have different numbers. It's a matter of elementary statistics: all numbers in the draw range are just as likely to be drawn with each new draw!

    For example, you make a draw and take the number 3 (it has a 10% chance of being drawn since the range is 0 to 9). In the next draw, the chance to get the number 3 again is: 10%! It is certain that all other numbers together have a 90% chance of being drawn. But there is still a chance to get out of the 3.

      

    See this code sample in Ideone that generates 100 numbers   random number between 0 and 9. I tested once and got the following   result:

         

    1 2 3 4 5 6 7 8 9 10 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

         

    It can be seen in bold in these 100 example calls that it was   need to generate 20 numbers (twice what is needed!) so that all   numbers were obtained (the last one was number 2). Notice how many   times the number 7 was produced unnecessarily.

    So this algorithm essentially works, but it has a serious problem. As you draw a new number without considering the ones already used , your program can take a long time, and this much may be even tending to infinity (or large enough to give you the impression that you've crashed in loop). It may seem silly or perfectionism to worry about this repetition of numbers in such a small range (0 to 9), but if you consider that your algorithm looks for whether the number already exists in the section, in the row and column, the computational cost of doing the search for an already drawn number is very expensive.

    The ideal solution then is that before you start these calculations (your for double loop), you mount a list with the numbers 0-9, sort out the order they will get (this is called random permutation) and then go one by one by removing the used number from the list (you can use a data structure of stack , for example).

    An example code that does random permutation on a vector is this: 

    #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;
}

    It was based on the examples from this page . See running on Ideone .

        
    20.06.2016 / 05:23
    Exception in thread "AWT-EventQueue-0" java.lang.ClassCastException: [Ljava.lang.Object; can not be cast to [Lbr.com.jcom.modelo.Marca; o What should I study? [closed]