[백트래킹] 스도쿠 2580 ○

문제 해설 및 주의사항

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

 

빈 칸의 경우에는 0이 주어진다

 

• baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

(원래 스도쿠는 백트래킹으로 풀 수 없는 문제이지만, 입력의 특이성으로 백트래킹으로 풀이가 가능한 문제이다. )

---

 

풀이

1. 브루트 포스

- 빈 칸에 모든 수를 넣어본다.

 

2. 백트래킹

- 모든 수를 넣어보지 않고, 가능하지 않은 수 (겹치는 수)는 건너 뛴다.

 

3. 검사

- 행 / 열 / 3x3 정사각형 / 을 검사해야 한다.

- c[i][j] : i 행에 숫자 j 가 있으면 true

- c2[i][j] : i 열에 숫자 j 가 있으면 true

- c3[i][j] : i 번째 3x3 박스에 숫자 j 가 있으면 true

 

4. 함수 구조

 

- 기저 사례 

- 검사 / 백트래킹

- 다음(재귀)

- 원상복귀

---

풀이코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 스도쿠 2580

int board[9][9];
/*
c[i][j] : i 행에 숫자 j 가 있으면 true
c2[i][j] : i 열에 숫자 j 가 있으면 true
c3[i][j] : i 번째 3x3 박스에 숫자 j 가 있으면 true
*/
bool c[9][10];
bool c1[9][10];
bool c2[9][10];

bool solve(int index){
	// 기저 사례 : 끝에 도달하면 출력
	if(index == 81){
		for(int i = 0; i < 9; i++){
			for(int j = 0; j < 9; j++){
				printf("%d ", board[i][j]);
			}
			printf("\n");
		}
		return true;
	}
	int x = index / 9, y = index % 9; 
	if(board[x][y] != 0 ){
		return solve(index + 1);
	}
	else{
		for(int i = 1; i <= 9; i++){
			int box = (x / 3)*3 + (y / 3);
			if(c[x][i] == false && c1[y][i] == false && c2[box][i] == false){
				c[x][i] = c1[y][i] = c2[box][i] = true;
				board[x][y] = i;
				if(solve(index + 1)){
					return true;
				}

				c[x][i] = c1[y][i] = c2[box][i] = false;
				board[x][y] = 0;
			}
		}
		
	}
	return false;
}

int main(){
	for(int i = 0; i < 9; i++){
		for(int j = 0; j < 9; j++){
			scanf("%d", &board[i][j]);
		}
	}
	fill_n(&c[0][0], 81, false);
	fill_n(&c1[0][0], 81, false);
	fill_n(&c2[0][0], 81, false);
	for(int i = 0; i < 9; i++){
		for(int j = 0; j < 9; j++){
			if(board[i][j] != 0){
				c[i][ board[i][j] ] = true;
				c1[j][ board[i][j] ] = true;
				int box = (j / 3) + (i / 3) * 3;
				c2[box][ board[i][j] ] = true;
			}
				
		}
	}
	solve(0);
	
}

 

퇴고

1. 배열 선언 시 인덱스 문제

- c c1 c2 배열은 각 행 / 열(0 ~ 8번 행 / 열) 및 박스를 검사하기 위함이었다. [i][j] 라면, i 번째 행 / 열 / 박스에 j 가 사용 되었는지 아닌지를 저장하는 배열이다. 그런데, 처음 선언시 [9][9] 라고 하여, j 의 범위인 1 ~ 9 를 충족시키지 못해서 예기치 못한 틀렸습니다가 자꾸 발생하였다.