No passado

Nas nossas duas últimas não muito emocionante aventuras, nós vimos como resolver o sudoku e como lemos um arquivo de sudoku.

Agora, vamos finalmente resolver o sudoku!

Achando "conflitos"

Se você se lembra de como resolver o sudoku, nós vamos, basicamente, chutar os números! Então, precisamos de um jeito para ver se o número chutado pode ficar no quadrado onde a gente o colocou ou não.

Para isso, precisamos ver se não há o mesmo número na linha, na coluna ou no "sub-quadrado" em que o colocamos, ou seja, sem repetir o mesmo número.

Vamos fazer isso por partes. Primeiro, vamos checar a linha. Cada elemento da tabela que representa o sudoku tem dois índices, i e j, certo? O índice i é a linha e o j é a coluna. Logo, a linha da posição ij é a linha i! Vamos fazer uma função que olha todos os elementos da linha i e comparamos com o número que a gente chutou para o elemento ij. Se algum for igual, nós vamos retornar true, ou seja, achamos um conflito!

1
2
3
4
5
6
7
8
9
10
11
12

bool conflito_linha(int sudoku[][9], int i, int j) {
    int valor = sudoku[i][j]; // numero que chutamos para o ij
    // agora vamos olhar!
    for (int coluna = 0; coluna < 9; coluna++) {
        if (coluna != j && sudoku[i][coluna] == valor) {
            // se entrarmos nesse if nos achamos um erro :(
            return true;
        }
    }
    // se a gente chegou aqui e pq nao tem erro!
    return false;
}

Nessa função, nós olhamos todos os elementos da linha i, usando a variável coluna para marcar cada um. Só temos que ter cuidado para não olhar a coluna j, já que sempre teríamos um conflito!

Agora, vamos fazer o mesmo para checar se há um conflito na mesma coluna de ij. Como j é a coluna, basta olharmos todas as linhas!

1
2
3
4
5
6
7
8
9
10
11
12

bool conflito_coluna(int sudoku[][9], int i, int j) {
    int valor = sudoku[i][j]; // numero que chutamos para o ij
    // agora vamos olhar!
    for (int linha = 0; linha < 9; linha++) {
        if (linha != i && sudoku[linha][j] == valor) {
            // se entrarmos nesse if nos achamos um erro :(
            return true;
        }
    }
    // se a gente chegou aqui e pq nao tem erro!
    return false;
}

Agora precisamos olhar o subquadrado! Isso é um pouco mais chato, já que dependendo da posição ij do elemento, o subquadrado varia!

O jeito que eu acho mais fácil para olhar o subquadrado é assim: nós identificamos cada um deles pela posição do primeiro elemento da primeira linha de cada um: (0,0) para o primeiro, (0,3) para o segundo da primeira linha, (0,6) para o terceiro e, depois, (3,0) para o primeiro da segunda linha até chegarmos no quadrado (6,6).

Como fazemos para identificar esse elemento? É simples! Nós, primeiro, dividimos i e j por 3. Depois, nós multiplicamos por 3!

Você tem que lembrar que, em C++, divisão funciona como a divisão da quarta série: 7 dividido por 3 dá 2 e sobra 1, certo? Logo, 7 dividido por 3, e depois vezes 3, dá 6! Fazendo isso, a gente sempre acha o quadrado certo!

O que nós vamos fazer então é, dada nossa posição ij, encontrar qual o primeiro elemento do subquadrado que o ij está. Depois, nós olhamos os 9 elementos desse subquadrado (com cuidado para ignorar o ij!) e vemos se achamos o erro.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool conflito_subquadrado(int sudoku[][9], int i, int j) {
    int valor = sudoku[i][j];
    // Vamos achar o primeiro elemento do quadrado!
    int linha_primeiro = (i / 3) * 3;
    int coluna_primeiro = (j / 3) * 3;

    // agora so precisamos olha os 9 elementos do quadrado!
    for (int linha = linha_primeiro; linha <= (linha_primeiro + 3); linha++) {
        for (int coluna = coluna_primeiro; coluna <= (coluna_primeiro + 3); coluna++) {
            if (!(linha == i && coluna == j) && sudoku[linha][coluna] == valor) {
                // achamos conflito :(
                return true;
            }
        }
    }
    // sem conflitos!
    return false;
}

Agora, só precisamos juntar essas 3 funções de verificar para ver se o número que chutamos pode ou não ficar no lugar que o colocamos! Como um conflito (dentre os 3 possíveis) já ferra tudo, podemos simplesmente ver se algum deles retornou verdadeiro:

1
2
3
4
5

bool conflito(int sudoku[][9], int i, int j) {
    return conflito_linha(sudoku, i, j) ||
        conflito_coluna(sudoku, i, j) ||
        conflito_subquadrado(sudoku, i, j);
}

Pronto!

Mudando um pouco nossa leitura

Nós precisamos mudar um pouco a função que lê nosso sudoku, porque precisamos guardar uma lista das posições ij da tabela que não são fixas, ou seja, que devemos preencher.

Para isso, vamos usar um vector do C++. Ela vai guardar pares, também do C++, que vão ter dois números, o i e o j (eu não vou usar listas porque não quero usar iteradores XD).

A única coisa que precisamos mudar na nossa função de leitura é que, toda vez que acharmos um 0, que representa um buraco, nós guardamos o par ij na nossa lista de vazios.

1
2
3
4
5
6
7
8
9
10
11

void ler_sudoku(int sudoku][9], char nome[128], vector< pair<int, int> >& vazios) {
    ifstream arquivo(nome, ifstream::in);
    for (unsigned i = 0; i < 9; i++) {
        for (unsigned j = 0; j < 9; j++) {
            arquivo >> sudoku[i][j];
            if (sudoku[i][j] == 0) {
                vazios.push_back(make_pair(i, j));
            }
        }
    }
}

Como eu disse, a única diferença é que quando lemos um 0 na posição ij nós colocamos na nossa lista de vazios o par ij.

Resolvendo o sudoku!

Agora nós temos tudo que precisamos, finalmente, para resolver o sudoku!

Para resolver, vamos fazer assim: nós pegamos o primeiro par ij na nossa lista de vazios e colocamos o número 1 nele. Depois checamos se aconteceu algum conflito: se estiver tudo bem, nós pegamos o próximo cara da lista e colocamos 2 e assim por diante. Se tivermos um conflito, somamos 1 no cara ij. Caso nós sejamos muito azarados, algum par ij não vai poder ser preenchido com nenhum número até 9. Mas não se desespere! Basta nós voltarmos para o cara anterior e aumentarmos ele em um! Nós repetimos isso até conseguir colocar algum número no último cara da lista de vazios!

Finalmente, nossa função resolve!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void resolve(int sudoku[][9], vector< pair<int, int> >& vazios) {
    unsigned it = 0;
    // enquanto nao conseguirmos preencher o ultimo cara
    while (it < vazios.size()) {
        int i = vazios[it].first;
        int j = vazios[it].second;
        // Estamos agora no cara ij
        // se ele for 9 ja era!
        if (sudoku[i][j] == 9) {
            sudoku[i][j] = 0;
            --it;
            continue;
        }
        sudoku[i][j]++;
        if (conflito(sudoku, i, j) == false) {
            // se nao der conflito maravilha! proximo!
            ++it;
        }
    }
}

Só falta escrevermos nossa função main:

1
2
3
4
5
6
7
8
9
10
11

int main() {
    char nome[128];
    int sudoku[9][9];
    vector< pair<int, int> > vazios;
    cout << "Qual e o nome do arquivo? ";
    cin >> nome;
    ler_sudoku(sudoku, nome, vazios);
    resolve(sudoku, vazios);
    imprimir_sudoku(sudoku);
    return 0;
}

E pronto! Espero que você tenha gostado e aprendido que, às vezes, a solução mais porca é suficiente!

Mais uma vez, o código está aqui.