스도쿠 (2239)

#include<iostream>
using namespace std;

int bCanNums[9][9][10];
int Board[9][9];

void UpdateCanNum(int X, int Y, int Num, bool bIsCan)
{
	if (Num == 0) return;

	int Delta = bIsCan ? -1 : 1;

	for (int i = 0; i < 9; ++i)
	{
		bCanNums[i][X][Num] += Delta;
		bCanNums[Y][i][Num] += Delta;
	}

	for (int y = 0; y < 3; ++y)
	{
		for (int x = 0; x < 3; ++x)
		{
			bCanNums[(Y / 3) * 3 + y][(X / 3) * 3 + x][Num] += Delta;
		}
	}

	return;
}

bool DFS(int Pos)
{
	if (Pos == 81) return true;

	int Y = Pos / 9;
	int X = Pos % 9;
	if (Board[Y][X] != 0) return DFS(Pos + 1);

	for (int i = 1; i < 10; ++i)
	{
		if (bCanNums[Y][X][i] == 0)
		{
			Board[Y][X] = i;
			UpdateCanNum(X, Y, i, false);
			if(DFS(Pos + 1)) return true;
			Board[Y][X] = 0;
			UpdateCanNum(X, Y, i, true);
		}
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);

	for (int y = 0; y < 9; ++y)
	{
		for (int x = 0; x < 9; ++x)
		{
			char Temp;
			cin >> Temp;
			Board[y][x] = Temp - '0';

			UpdateCanNum(x, y, Board[y][x], false);
		}
	}

	DFS(0);

	for (int y = 0; y < 9; ++y)
	{
		for (int x = 0; x < 9; ++x)
		{
			cout << Board[y][x];
		}
		cout << "\\n";
	}

	return 0;
}

근데 스도쿠가 만약에 9x9 가 아니라 좀 큰 판이라면

이게 좋은 거 같다.

#include<iostream>
using namespace std;

int Board[9][9];

// Row[A][B]는 A번째 행에 B라는 숫자가 존재한다는 의미
bool Row[9][10];
bool Col[9][10];
bool Square[9][10];

bool DFS(int Pos)
{
	if (Pos == 81) return true;

	int Y = Pos / 9;
	int X = Pos % 9;
	int SquareNum = Y / 3 * 3 + X / 3;

	if (Board[Y][X] != 0) return DFS(Pos + 1);

	for (int i = 1; i < 10; ++i)
	{
		if (!Row[Y][i] && !Col[X][i] && !Square[SquareNum][i])
		{
			Board[Y][X] = i;
			Row[Y][i] = true;
			Col[X][i] = true;
			Square[SquareNum][i] = true;
			if (DFS(Pos + 1)) return true;
			Board[Y][X] = 0;
			Row[Y][i] = false;
			Col[X][i] = false;
			Square[SquareNum][i] = false;
		}
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);

	for (int y = 0; y < 9; ++y)
	{
		for (int x = 0; x < 9; ++x)
		{
			char Temp;
			cin >> Temp;
			Board[y][x] = Temp - '0';

			Row[y][Board[y][x]] = true;
			Col[x][Board[y][x]] = true;
			Square[y / 3 * 3 + x / 3][Board[y][x]] = true;
		}
	}

	DFS(0);

	for (int y = 0; y < 9; ++y)
	{
		for (int x = 0; x < 9; ++x)
		{
			cout << Board[y][x];
		}
		cout << "\\n";
	}

	return 0;
}