[골4] 2580 - 스도쿠

#include<iostream>

#define MAX 9
using namespace std;

int map[MAX][MAX];
bool row[MAX][MAX];
bool col[MAX][MAX];
bool square[MAX][MAX];

void Input()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			cin >> map[i][j];
			auto val = map[i][j];

			if (val != 0)
			{
				row[i][val] = col[j][val] = true;
				square[(i / 3) * 3 + (j / 3)][val] = true;
			}
		}
	}
}

void Print()
{
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
			cout << map[i][j] << " ";

		cout << endl;
	}
}

void DFS(int cnt = 0)
{
	int x = cnt / MAX;    // x 좌표
	int y = cnt % MAX;    // y 좌표

	if (cnt == 81)
	{
		Print();
		exit(0);
	}
	if (map[x][y] == 0)
	{
		for (int i = 1; i <= MAX; i++)
		{
			auto region = (x / 3) * 3 + (y / 3);

			if (!row[x][i] && 
				!col[y][i] && 
				!square[region][i])
			{
				row[x][i] = col[y][i] = true;
				square[region][i] = true;
				map[x][y] = i;
				DFS(cnt + 1);
				map[x][y] = 0;
				row[x][i] = col[y][i] = false;
				square[region][i] = false;
			}
		}
	}
	else 
		DFS(cnt + 1);
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	DFS();

	return 0;
}