#include <iostream>
using namespace std;
const int LINHAS = 9;
const int COLUNAS = 9;
void imprimirTabuleiro(int tabuleiro[][COLUNAS]) {
for (int i = 0; i < LINHAS; i++) {
for (int j = 0; j < COLUNAS; j++) {
cout << tabuleiro[i][j] << " ";
}
cout << endl;
}
}
bool encontrarVazio(int tabuleiro[][COLUNAS], int& linha, int& coluna) {
for (linha = 0; linha < LINHAS; linha++) {
for (coluna = 0; coluna < COLUNAS; coluna++) {
if (tabuleiro[linha][coluna] == 0) {
return true;
}
}
}
return false;
}
bool ehValido(int tabuleiro[][COLUNAS], int linha, int coluna, int num) {
for (int i = 0; i < LINHAS; i++) {
if (tabuleiro[linha][i] == num) {
return false;
}
if (tabuleiro[i][coluna] == num) {
return false;
}
}
int boxLinha = linha - linha % 3;
int boxColuna = coluna - coluna % 3;
for (int i = boxLinha; i < boxLinha + 3; i++) {
for (int j = boxColuna; j < boxColuna + 3; j++) {
if (tabuleiro[i][j] == num) {
return false;
}
}
}
return true;
}
bool resolverSudoku(int tabuleiro[][COLUNAS]) {
int linha, coluna;
if (!encontrarVazio(tabuleiro, linha, coluna)) {
return true;
}
for (int num = 1; num <= 9; num++) {
if (ehValido(tabuleiro, linha, coluna, num)) {
tabuleiro[linha][coluna] = num;
if (resolverSudoku(tabuleiro)) {
return true;
}
tabuleiro[linha][coluna] = 0;
}
}
return false;
}
int main() {
int tabuleiro[LINHAS][COLUNAS] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
cout << "Tabuleiro inicial:" << endl;
imprimirTabuleiro(tabuleiro);
if (resolverSudoku(tabuleiro)) {
cout << "Solucao encontrada:" << endl;
imprimirTabuleiro(tabuleiro);
} else {
cout << "Nao foi possivel encontrar uma solucao magrao." << endl;
}
return 0;
}