URI (BEECROWD) - 1383 - Sudoku - Ad-Hoc - C e C++

Galera, hoje resolvi o problema Sudoku! Esse problema foi bem interessante de resolver, porque à primeira vista eu não havia entendido muito bem ele e depois fiquei bem satisfeito em conseguir o aceite.

Não é um exercício difícil, mas deu aquele orgulho ao conseguir resolver :)))

Confere abaixo a solução! Imagino que muita gente tenha resolvido de formas diferentes. Comente como foi que você pensou a solução deste exercício!

Um abraço!

Plataforma: URI (BEECROWD)

Problema: 1383

Enunciado:
O jogo de Sudoku espalhou-se rapidamente por todo o mundo, tornando-se hoje o passatempo mais popular em todo o planeta. Muitas pessoas, entretanto, preenchem a matriz de forma incorreta, desrespeitando as restrições do jogo. Sua tarefa neste problema é escrever um programa que verifica se uma matriz preenchida é ou não uma solução para o problema.

A matriz do jogo é uma matriz de inteiros 9 x 9 . Para ser uma solução do problema, cada linha e coluna deve conter todos os números de 1 a 9. Além disso, se dividirmos a matriz em 9 regiões 3 x 3, cada uma destas regiões também deve conter os números de 1 a 9. O exemplo abaixo mostra uma matriz que é uma solução do problema.

Linguagens: C e C++

Solução:

Criei algumas funções auxiliares aqui para ajudar. O primeiro passo é usar a função zeraDigitos para zerar todos os valores da matriz 9x9, pois o sudoku tem esse formato. Depois, criei duas funções de validação, uma para linha/coluna (o parâmetro flag indicará se analisa linha ou coluna), que é chamada uma vez para a linha e outra para a coluna, e outra para validar a sub-matriz 3x3, pois é necessário que nestes nove blocos 3x3 nenhum número se repita.

Todas as funções de verificação retornam zero se não há problemas e 1 caso haja. Assim, se esta função tiver um valor maior que zero (utilizei "diferente de zero", mas aqui funciona da mesma forma), ocorre um erro e a solução não é válida.

Código em C:

#include <stdio.h>

#define TAM 9

void zeraDigitos(int *dg) {
    int i;
    for (i = 0; i < TAM; i++)
        dg[i] = 0;
}

int valida(int v[TAM][TAM], int flag, int *dg) {
    int i, j;
    for (i = 0; i < TAM; i++) {
        for (j = 0; j < TAM; j++) {
            if (flag) {
                dg[v[i][j]]++;
                if (dg[v[i][j]] > 1)
                    return 1;
            }
            else {
                dg[v[j][i]]++;
                if (dg[v[j][i]] > 1)
                    return 1;
            }
        }
	zeraDigitos(dg);
    }
    return 0;
}

int validaSubMatrix(int v[TAM][TAM], int lInicio, int lFim, int cInicio, int cFim, int *dg) {
    int i, j;
    for (i = lInicio; i < lFim; i++) {
        for (j = cInicio; j < cFim; j++) {
	    dg[v[j][i]]++;
	    if (dg[v[j][i]] > 1)
		return 1;
	}
    }
    zeraDigitos(dg);
    return 0;
}

int main() {

    int n, mat[TAM][TAM], invalid, digits[TAM], cases, i, j;
    scanf("%i", &n);

    for (cases = 1; cases <= n; cases++) {
        for (i = 0; i < TAM; i++) {
	    zeraDigitos(digits);
	    for (j = 0; j < TAM; j++) {
		scanf("%i", &mat[i][j]);
		mat[i][j]--;
	    }
	}

	invalid = valida(mat, 1, digits) + valida(mat, 0, digits);

	for (i = 0; i < TAM; i+=3)
            for (j = 0; j < TAM; j+=3)
    		invalid += validaSubMatrix(mat, i, i + 3, j, j + 3, digits);

	printf("Instancia %i\n", cases);

	if (invalid)
	    printf("NAO\n\n");
	else
	    printf("SIM\n\n");
    }
    return 0;
}

Código em C++:

#include <iostream>

#define TAM 9

using namespace std;

void zeraDigitos(int *dg) {
    for (int i = 0; i < TAM; i++)
		dg[i] = 0;
}

int valida(int v[TAM][TAM], int flag, int *dg) {
    for (int i = 0; i < TAM; i++) {
	for (int j = 0; j < TAM; j++) {
	    if (flag) {

                dg[v[i][j]]++;
		if (dg[v[i][j]] > 1)
		    return 1;
	    }

            else {
		dg[v[j][i]]++;
		if (dg[v[j][i]] > 1)
		    return 1;
	    }
        }
	zeraDigitos(dg);
    }
    return 0;
}

int validaSubMatrix(int v[TAM][TAM], int lInicio, int lFim, int cInicio, int cFim, int *dg) {
    for (int i = lInicio; i < lFim; i++) {
        for (int j = cInicio; j < cFim; j++) {
            dg[v[j][i]]++;
            if (dg[v[j][i]] > 1)

                return 1;
        }
    }

    zeraDigitos(dg);

    return 0;
}

int main() {

    int n, mat[TAM][TAM], invalid, digits[TAM];
    cin >> n;

    for (int cases = 1; cases <= n; cases++) {
        for (int i = 0; i < TAM; i++) {
            zeraDigitos(digits);
            for (int j = 0; j < TAM; j++) {
                cin >> mat[i][j];
                mat[i][j]--;
            }
        }

        invalid = valida(mat, 1, digits) + valida(mat, 0, digits);
		
        for (int i = 0; i < TAM; i+=3)
            for (int j = 0; j < TAM; j+=3)
                invalid += validaSubMatrix(mat, i, i+3, j, j+3, digits);

	cout << "Instancia " << cases << endl;

        if (invalid)
            cout << "NAO" << endl << endl;
        else
            cout << "SIM" << endl << endl;
    }

    return 0;
}