# 1383 - Sudoku

## Descrição

{% embed url="<https://www.urionlinejudge.com.br/judge/pt/problems/view/1383>" %}

## Solução

Eu decidi separar o conjunto de regras em três funções diferentes:

1. Verificação de linha: verificar se todos os números aparecem na linha uma e apenas uma vez.
2. Verificação de coluna: verificar se todos os números aparecem na coluna uma e apenas uma vez.
3. Verificação de quadrado: verificar se todos os números aparecem no quadrado uma e apenas uma vez.

Daí executar o programa para cada uma das 9 linhas, 9 colunas e 9 quadrados.

Nas linguagens de programação onde era permitido, utilizei conjuntos para adicionar todos os números de uma determinada linha, coluna ou quadrado e depois verificar se tal conjunto tinha tamanho exatamente 9. Para linguagens onde tal estrutura não é trivial, utilizei um vetor para marcar cada número e se fosse marcar um número já marcado, apontar a irregularidade.

Para definir onde começa cada quadrado, onde `x` é o identificador do quadrado, fiz `3*(x/3)` para definir a linha e `3*(x%3)` para definir a coluna da coordenada de cada quadrado. Dessa maneira, temos as seguintes coordenadas para os 9 quadrados:

| Quadrado | Coordenada |
| -------- | ---------- |
| 0        | (0, 0)     |
| 1        | (0, 3)     |
| 2        | (0, 6)     |
| 3        | (3, 0)     |
| 4        | (3, 3)     |
| 5        | (3, 6)     |
| 6        | (6, 0)     |
| 7        | (6, 3)     |
| 8        | (6, 6)     |

{% tabs %}
{% tab title="C99" %}

```c
#include <stdio.h>

int sudoku[9][9];

int verificaLinha(int x){
    int numeros[10];

    for(int i = 0; i < 10; ++i){
        numeros[i] = 0;
    }

    for(int i = 0; i < 9; ++i){
        if(numeros[sudoku[x][i]])   return 0;
        numeros[sudoku[x][i]] += 1;
    }

    return 1;
}

int verificaColuna(int x){
    int numeros[10];

    for(int i = 0; i < 10; ++i){
        numeros[i] = 0;
    }

    for(int i = 0; i < 9; ++i){
        if(numeros[sudoku[i][x]])   return 0;
        numeros[sudoku[i][x]] += 1;
    }

    return 1;
}

int verificaQuadrado(int x){
    int numeros[10];
    int linha = 3*(x/3), coluna = 3*(x%3);

    for(int i = 0; i < 10; ++i){
        numeros[i] = 0;
    }

    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            if(numeros[sudoku[linha + i][coluna + j]])  return 0;
            numeros[sudoku[linha + i][coluna + j]] += 1;
        }
    }

    return 1;
}

int main(){
    int n;
    char* resposta;

    scanf("%d", &n);

    for(int k = 1; k <= n; ++k){
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                scanf("%d", &sudoku[i][j]);
            }
        }

        printf("Instancia %d\n", k);

        resposta = "SIM";
        for(int i = 0; i < 9; ++i){
            if(!verificaLinha(i) || !verificaColuna(i) || !verificaQuadrado(i)){
                resposta = "NAO";
                break;
            }
        }

        printf("%s\n\n", resposta);
    }

    return 0;
}
```

{% endtab %}

{% tab title="C++17" %}

```cpp
#include <iostream>
#include <set>

using namespace std;

int sudoku[9][9];

bool verificaLinha(int x){
    set<int> numeros;

    for(int i = 0; i < 9; ++i){
        numeros.insert(sudoku[x][i]);
    }

    return numeros.size() == 9;
}

bool verificaColuna(int x){
    set<int> numeros;

    for(int i = 0; i < 9; ++i){
        numeros.insert(sudoku[i][x]);
    }

    return numeros.size() == 9;
}

bool verificaQuadrado(int x){
    set<int> numeros;
    int linha = 3*(x/3), coluna = 3*(x%3);

    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            numeros.insert(sudoku[linha + i][coluna + j]);
        }
    }

    return numeros.size() == 9;
}

int main(){
    int n;
    string resposta;

    cin >> n;
    for(int k = 1; k <= n; ++k){
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                cin >> sudoku[i][j];
            }
        }

        cout << "Instancia " << k << endl;

        resposta = "SIM";
        for(int i = 0; i < 9; ++i){
            if(!verificaLinha(i) || !verificaColuna(i) || !verificaQuadrado(i)){
                resposta = "NAO";
                break;
            }
        }

        cout << resposta << endl << endl;
    }

    return 0;
}
```

{% endtab %}

{% tab title="JavaScript 12.18" %}

```javascript
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');

const verificaLinha = (sudoku, x) => {
    const numeros = new Set(sudoku[x]);
    return numeros.size === 9;
};

const verificaColuna = (sudoku, x) => {
    const numeros = new Set(sudoku.map((linha) => linha[x]));
    return numeros.size === 9;
}

const verificaQuadrado = (sudoku, x) => {
    let numeros = new Set();
    const linha = 3*(Math.floor(x/3)), coluna = 3*(x%3);

    for(let i = 0; i < 3; ++i){
        for(let j = 0; j < 3; ++j){
            numeros.add(sudoku[linha + i][coluna + j]);
        }
    }

    return numeros.size === 9;
}

let n = lines.shift();

for(let k = 1; k <= n; ++k){
    let sudoku = [];

    for(let i = 0; i < 9; ++i){
        sudoku.push(lines.shift().trim().split(' ').map((x) => parseInt(x)));
    }

    console.log(`Instancia ${k}`);

    let resposta = "SIM";
    for(let i = 0; i < 9; ++i){
        if(!verificaLinha(sudoku, i) || !verificaColuna(sudoku, i) || !verificaQuadrado(sudoku, i)){
            resposta = "NAO";
            break;
        }
    }

    console.log(resposta);
    console.log();
}
```

{% endtab %}

{% tab title="Python 3.9" %}

```python
from functools import reduce

def verificaLinha(sudoku, x):
    numeros = set(sudoku[x])
    return len(numeros) == 9

def verificaColuna(sudoku, x):
    numeros = set([sudoku[i][x] for i in range(9)])
    return len(numeros) == 9

def verificaQuadrado(sudoku, x):
    linha, coluna = 3*(x//3), 3*(x%3)
    numeros = set(list(reduce(list.__add__, [l[coluna:(coluna + 3)] for l in sudoku[linha:(linha + 3)]])))
    return len(numeros) == 9

n = int(input())
for k in range(1, n + 1):
    sudoku = []

    for i in range(9):
        sudoku.append([int(x) for x in input().strip().split(' ')])
    
    print(f"Instancia {k}")

    resposta = "SIM"
    for i in range(9):
        if(not verificaLinha(sudoku, i) or not verificaColuna(sudoku, i) or not verificaQuadrado(sudoku, i)):
            resposta = "NAO"
    
    print(resposta)
    print()
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xtecna.gitbook.io/solucoes-da-beecrowd/ad-hoc/1383-sudoku.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.