[C++][BAEKJOON][Bruteforce] 2580번 스도쿠 풀이 & 반례

[문제]

2580번: 스도쿠

 

[문제설명]

스도쿠 게임의 답을 찾는 문제 ~!

 

스도쿠 게임 조건은 아래 2가지다.

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

[문제 풀이]

첨엔 예시만 보고 가로, 세로, 3x3을 탐색해서 한칸만 비어서 바로 풀수 있는 칸을 풀고 다음 칸을 푸는 방식으로 구현했다. 결과는 대망... 아래 반례처럼 빈칸이 많을 때도 포함해서 모든 경우의 수를 구해야 하기 때문이다. 이 때, 답이 여러개일 때는 제일 처음 구해진걸 답으로 채택한다!!! exit(0); !!!

 

[틀린코드]

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

void Input();
void Stocoo();
bool FillNumber(bool *check_num, int x, int y, int index);
void Output();

int map[9][9];
vector<pair<pair<int, int>, bool>> blank;

int main() {
    Input();
    Stocoo();
    Output();
    return 0;
}

void Input() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> map[i][j];
            if (map[i][j] == 0) {
                blank.push_back(make_pair(make_pair(i, j), false));
            }
        }
    }
}

void Stocoo() {
    for (int i = 0; i < 9; i++) {
        int x = blank[i].first.first;
        int y = blank[i].first.second;

        bool check_num[10] = { false, };
        int check = 0;

        //가로
        for (int col = 0; col < 9; col++) {
            if (map[x][col] != 0) {
                check_num[map[x][col]] = true;
                check++;
            }
        }
        if (check == 8) { if (FillNumber(check_num, x, y, i)) continue; }
        memset(check_num, false, sizeof(check_num));
        check = 0;

        //세로
        for (int row = 0; row < 9; row++) {
            if (map[row][y] != 0) {
                check_num[map[row][y]] = true;
                check++;
            }
        }
        if (check == 8) { if (FillNumber(check_num, x, y, i)) continue; }
        memset(check_num, false, sizeof(check_num));
        check = 0;

        //3x3
        for (int row = x / 3 * 3; row < x / 3 * 3 + 3; row++) {
            for (int col = y / 3 * 3; col < y / 3 * 3 + 3; col++) {
                if (map[row][col] != 0) {
                    check_num[map[row][col]] = true;
                    check++;
                }
            }
        }
        if (check == 8) { if (FillNumber(check_num, x, y, i)) continue; }
    }
    for (int i = 0; i < blank.size(); i++) {
        if (!blank[i].second) {
            Stocoo();
        }
    }
}

bool FillNumber(bool *check_num, int x, int y, int index) {
    for (int i = 1; i < 10; i++) {
        if (!check_num[i]) {
            map[x][y] = i;
            blank[index].second = true;
            return true;
        }
    }
    return false;
}

void Output() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

즉, 풀이과정을 적어보면 다음과 같다.

1) bruteforce로 빈칸에 가로, 세로, 3x3 조건을 만족하는 1~9를 모두 넣어본다.

2) 만약 넣을 수 있는 수가 없다면 이전에 넣은 값이 문제이므로 backtracking으로 돌아가서(return) 다음 값을 넣어본다.

3) 모든 칸을 채웠다면 결과를 출력한다. 

 

근데 backtracking 에서 return해서 map[x][y] = 0; 구문을 적어줬는데, 이 구문이 없으면 오류가 나는 이유를 모르겠다.

낼 정신 맑을 때 다시 봐봐야지 ㅎㅎ...

 

[반례 예제]

TEST CASE # 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

SAMPLE ANSWER #1
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

 

TEST CASE # 2
0 2 0 9 0 5 0 0 0
5 9 0 0 3 0 2 0 0
7 0 0 6 0 2 0 0 5
0 0 9 3 5 0 4 6 0
0 5 4 0 0 0 7 8 0
0 8 3 0 2 7 5 0 0
8 0 0 2 0 9 0 0 4
0 0 5 0 4 0 0 2 6
0 0 0 5 0 3 0 7 0

 

SAMPLE ANSWER # 2
3 2 1 9 7 5 6 4 8
5 9 6 8 3 4 2 1 7
7 4 8 6 1 2 9 3 5
1 7 9 3 5 8 4 6 2
2 5 4 1 9 6 7 8 3
6 8 3 4 2 7 5 9 1
8 1 7 2 6 9 3 5 4
9 3 5 7 4 1 8 2 6
4 6 2 5 8 3 1 7 9

 

[코드]

#include <iostream>
#include <vector>
using namespace std;

void Input();
void Stocoo(int blank_index);
bool CheckNumber(int x, int y, int num);
void Output();

int map[9][9];
vector<pair<int, int>> blank_position;

int main() {
	Input();
	Stocoo(0);
	Output();
	return 0;
}

void Input() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				blank_position.push_back(make_pair(i, j));
			}
		}
	}
}

void Stocoo(int blank_index) {
	if (blank_index == blank_position.size()) {
		Output();
		exit(0); //모두가 0으로 이루어진 스도쿠처럼 답이 여러개일 수도 있는데,
				//그럴 때 제일 첫번째로 구해진 답을 정답으로 처리하고 더이상 구하지 않도록. 종료시킨다.
	}
	int x = blank_position[blank_index].first;
	int y = blank_position[blank_index].second;

	for (int num = 1; num < 10; num++) { // 1, 2, 3, 4, 5, 6, 7, 8, 9 하나씩 넣어보기
		//조건에 맞는지 체크
		if (CheckNumber(x, y, num)) {
			//조건에 맞으면 다음 blank 채우러가기
			map[x][y] = num;
			Stocoo(blank_index+1);//*****주의: blank_index++로 넣으면 안들가짐
			//다음걸 넣을게 없어서 return 됐을 때!
			//Backtracking으로 다시 gogo!
			map[x][y] = 0;//???????? 이 구문이 없으면 왜 안될까......

		}
		//조건에 맞지 않으면 다음 숫자 넣어보기
	}
}

bool CheckNumber(int x, int y, int num) {
	//가로
	for (int col = 0; col < 9; col++) {
		if (y != col && map[x][col] == num) {
			return false;
		}
	}
	//세로
	for (int row = 0; row < 9; row++) {
		if (x != row && map[row][y] == num) {
			return false;
		}
	}
	//3x3
	for (int row = x / 3 * 3; row < x / 3 * 3 + 3; row++) {//0,1,2,3,4,5,6,7,8,9 구역으로 나눔
		for (int col = y / 3 * 3; col < y / 3 * 3 + 3; col++) {
			if (x != row && y != col && map[row][col] == num) {
				return false;
			}
		}
	}
	return true;
}

void Output() {
	cout << "\n";
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
}