문제

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

스도쿠의 기본 규칙은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

예제

---

풀이

빈칸 0에 숫자 a를 넣으려면, a가 속한 가로와 세로, 그리고 3*3 크기의 박스 내에 a라는 숫자가 없어야 하며, 이는 모든 영역에 동일하게 적용되는 규칙이다.

문제에서 주어진 규칙 그대로 구현하면 된다.

빈칸 0의 위치를 찾아서, 1부터 9까지의 숫자가 가로, 세로, 박스에 있는지 검사하고 없으면 넣고 다음 빈칸 위치를 찾으러 간다.

만약 빈칸 0에 1부터 9까지 모든 숫자를 넣을 수 없는 경우에는, 다시 이전 0으로 돌아와서 해당 빈칸에 다른 수를 넣어야 한다.

#include <iostream>
using namespace std;

const int N = 9; 
int arr[N][N]; 
bool found = false; 

bool promising(int r, int c, int num){ 
	for(int i = 0; i < N; i++){
		// 현재 행에 겹치는 숫자가 있으면 
		if(arr[r][i] == num) return false; 
		// 현재 열에 겹치는 숫자가 있으면 
		if(arr[i][c] == num) return false;
	}

	// 3x3 사각형 내에 겹치는 숫자가 있으면 
	for(int i = (r/3) * 3; i < (r/3) * 3 + 3; i++){
		for(int j = (c/3) * 3; j < (c/3) * 3 + 3; j++){
			if(arr[i][j] == num) return false; 
		}
	}

	// 모든 조건을 충족하면 true 
	return true; 
}

void dfs(int r, int c){ 
	// 행의 끝까지 오면 정답 출력 
	if(r == N){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				cout << arr[i][j] << " ";
			}
			cout << "\n";
		}
		found = true; 
		return; 
	}

	// 열의 끝까지 오면, 다음 행의 첫번째 열로 이동 
	if(c == N) dfs(r + 1, 0); 

	// 빈칸인지 검사 
	if(arr[r][c] == 0){
		for(int i = 1; i <= N; i++){ // 1~9 
        	// 유망하다면 
			if(promising(r, c, i)){
            	// 빈칸 (r, c)에 숫자 i를 넣어본다. 
				arr[r][c] = i; 
                
                // 재귀 호출 (다음 열로 이동) 
				dfs(r, c + 1); 
                
                // (r, c)에 1~9까지의 모든 숫자를 넣을 수 없다면 
                // 이 위치로 돌아와서 상태 복구 (빈칸에 다른 숫자 넣어보기 위해서)
				arr[r][c] = 0; 
			}

			// 해를 찾고 나서 이 위치로 돌아온 경우, dfs 함수 완전히 종료 
			if(found) return; 
		}
	}else{
		// 다음 열로 이동 
		dfs(r, c + 1); 
	}
}

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

	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> arr[i][j];
		}
	}

	dfs(0, 0); 

	return 0;
}