Sudoku game resolution giving infinite loop in C

Question

I have the following code on 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 fill and solve the entire board by following the rules of the game, that is, a number (from 1 to 9) cannot be repeated in the same row, column or quadrant (3 by 3). Following my logic, it was supposed to be working, but it never resolves "first" and most of the time it goes into infinite loop. What I did was: I’m filling in quadrant by quadrant, so I can check the previous quadrants and avoid filling in the matrix with repeated numbers. Then I created three functions, one to check if the generated number already exists in a quadrant, another to check the row and the other to column (each returns 1 if the number exists and 0 if it does not exist) and use their return in the following check:

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 decreases from the for referring to the column and if it does not exist it adds the number in the matrix, that is, this loop will repeat until a number is generated that does not exist in any of the areas.

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

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

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

As I said before, most of the time it enters an infinite loop, that is, I need to recompile the code several times until it can generate the board. Below is the result of the maximum quadrants he can fill (8) after several recompilations of the code (with the value for(int sla = 0; sla < 8; sla++)), < 8 because that’s as much as he can get if I change it to < 9, that is, to fill everything, it always stays in infinite loop (even re-running the code multiple times).

How to fix this infinite loop so that the board/matrix can always be filled in the correct way right at the first run?

Answer 1

I didn’t go through all the code to see if there were any other problems. But a potential problem with your code is that you do the following in the section that attempts to assemble each column/row (both for chained in the call of func_numeros):

1. Draw a number at random between 0 and 9.
2. Search if the drawn number has already been used.
3. If the drawn number has not yet been used, use it (and skip to step 5).
4. If the drawn number has already been used, return to step 1.
5. Continues 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 is a matter of elementary statistics: all numbers in the range of the draw have the same probability of being drawn at each new draw!

For example, you draw 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 take the number 3 again is: 10%! It is right that all other numbers have, together, 90% chance of being drawn. But there’s still a chance to get out the 3.

Behold this example of code in Ideone that generates 100 numbers random between 0 and 9. I tested once and got the following outworking:

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

You can see, in bold in these 100 example calls, that was necessary to generate 20 numbers (double the necessary!) so that all the numbers were obtained (the last was number 2). Note how many times number 7 was produced unnecessarily.

So this algorithm of yours essentially works, but it has a serious problem. How do you draw a new number without taking into account those already used, your program may take a long time, and that much may be even tending to infinity (or be large enough to give you the impression that you have looped). It may seem silly or perfectionism to worry about these repetitions of numbers in such a small range (0 to 9), but if you consider that your algorithm looks if the number already exists in the section, row and column, the computational cost of searching for an already drawn number is very expensive.

The ideal solution then is that before starting these calculations (your loop for double), you assemble a list of the numbers from 0 to 9, sort the order they will be in (this is called random permutation) and then use one by one, removing the used number from the list (you can use a data structure of pile, for example).

An example of code that does random permutation on an array 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;
}

He was based on the examples of that page. See running in Ideone.