[ boj : 2239 ] 스도쿠

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

해설 : 대표적인 백트래킹 문제입니다.

모든 칸들을 확인하면서 만약 0 이 아니라면 다음칸으로 넘어가고, 0이면 1~9까지 전부 대입해 보면서 현재 스토쿠 규정에 어긋나는지 아닌지를 확인해 보면되겠죠.

 

살짝 버벅거리는 부분은 y 가 8번째 일때는 다음 줄로 넘어가서 (x+1,0) 부터 시작해야 할텐데 이걸 어떻게 해주지?

라는 생각이 들수 있을 텐데 이는 

'dfs(x + (y == 8), (y + 1) % 9)'

이런 식으로 해결할 수 있습니다.

 

#include<bits/stdc++.h>

using namespace std;

string board[9],ans[9];

void solve();
bool dfs(int x, int y);
bool check(int x, int y, int p);

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

	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	for (int i = 0; i < 9; i++)
		cin >> board[i];

	dfs(0, 0);
	for (int i = 0; i < 9; i++)
		cout << board[i] << "\n";
}
bool dfs(int x, int y)
{	
	if (x >= 9)return true;

	if (board[x][y] != '0')
		return dfs(x + (y == 8), (y + 1) % 9);

	for (int i = 1; i <= 9; i++) {
		board[x][y] = i + '0';
		if (check(x,y,board[x][y]-'0') && dfs(x + (y == 8), (y + 1) % 9))return true;
		board[x][y] = '0';
	}
	return false;
}
bool check(int x, int y, int p)
{
	for (int i = 0; i < 9; i++)
		if (i != y && board[x][i] - '0' == p)
			return false;
	for (int i = 0; i < 9; i++)
		if (i != x && board[i][y] - '0' == p)
			return false;
	int tx = (x / 3) * 3;
	int ty = (y / 3) * 3;
	for (int i = tx; i < tx + 3; i++)
		for (int j = ty; j < ty + 3; j++)
			if ((i != x && j != y) && board[i][j] - '0' == p)
				return false;
	return true;
}