#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int matrice[9][9] = {
	{3,0,6,5,0,8,4,0,0},
	{5,2,0,0,0,0,0,0,0},
	{0,8,7,0,0,0,0,3,1},
	{0,0,3,0,1,0,0,8,0},
	{9,0,0,8,6,3,0,0,5},
	{0,5,0,0,9,0,6,0,0},
	{1,3,0,0,0,0,2,5,0},
	{0,0,0,0,0,0,0,7,4},
	{0,0,5,2,0,6,3,0,0}
};

void afisare()
{
	int i, j;
	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
		{
			printf("%d\t", matrice[i][j]);
		}
		printf("\n\n");
	}
}

int numar(int *row, int *col)
{
	int num = 0;
	int i, j;
	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
		{

			if (matrice[i][j] == 0)
			{
				*row = i;
				*col = j;
				num = 1;
				return num;
			}
		}
	}
	return num;
}

int verificare(int n, int r, int c)
{
	int i, j;
	for (i = 0; i < 9; i++)
	{
		if (matrice[r][i] == n)
			return 0;
	}
	for (i = 0; i < 9; i++)
	{
		if (matrice[i][c] == n)
			return 0;
	}

	int row_start = (r / 3) * 3;
	int col_start = (c / 3) * 3;
	for (i = row_start; i < row_start + 3; i++)
	{
		for (j = col_start; j < col_start + 3; j++)
		{
			if (matrice[i][j] == n)
				return 0;
		}
	}
	return 1;
}

int rezolvare()
{
	int row;
	int col;

	if (numar(&row, &col) == 0)
		return 1;
	int n, i;

	for (i = 1; i <= 9; i++)
	{
		if (verificare(i, row, col))
		{
			matrice[row][col] = i;

			if (rezolvare())
				return 1;

			matrice[row][col] = 0;
		}
	}
	return 0;
}

int main()
{
	if (rezolvare())
		afisare();
	else
		printf("Nu exista solutie\n");
	system("pause");
	return 0;
}