Brute force algorithm for game resolution Sudoku in C

6

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

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). What I did was: I am filling quadrant by quadrant, so I can check the previous quadrants and avoid filling the unit with repeated numbers. Then 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 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;
}

In the above check I check if the number already exists in any of the areas (row, column or quadrant) and if it exists it increments the variable numero_posicao to get the next number of the vector and check if it can be added to the array , if yes it is added, if not the loop repeats. I am using the if(numero_posicao > 8) check because this means that if it is greater than 8, it is because none of the numbers can be added in that position, ie it has entered a "dead end" when this occurs, I zero the quadrant jogo_tabuleiro[hey][how] = 0; and try l_i = linha_inicio; c_i = coluna_inicio; to fill it again the current quadrant, but when I try in this way the program goes into infinite loop (so the two lines are commented). How do I resolve this and fill in the board correctly?

    
asked by anonymous 28.06.2016 / 06:00

1 answer

3

This method is a brute-force algorithm.

The advantage of this algorithm is simplicity and its disadvantage is processing time.

So this method is used when simplicity of implementation is more important than speed.

The algorithm navigates between empty cells in a given order, sequentially filling numbers from the available options, OR goes back, removing incorrect numbers when cell filling is not possible.

Below is the description of a brute-force algorithm to solve Sodoku:

  

1 - Start with the first free cell;

     

2 - Fill in the cell with one of the possible numbers that do not violate the   rules of Sodoku. If you arrive at a deadlock that   fill the cell according to the rules, go to step 4.   otherwise, continue with step 3;

     

3 - Move to the next cell and go to step 2;

     

4 - Go back to the previous cell. Select another number and   cell. Go to step 3;

     

5 - Continue repeating the steps until all empty cells   are fulfilled.

Here are some interesting links:

Wikipedia (English): link

Sample Code (github): link

I hope I have helped.

    
28.06.2016 / 15:06