[C++] 백준 2580 스도쿠

문제 링크

---

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

2580번: 스도쿠

접근 방법

---

 

스도쿠의 빈칸을 채우기 위한 조건은 3가지가 있다.

1. 빈칸을 포함하는 행에 1~9까지 숫자가 단 한번씩만 존재해야함

2. 빈칸을 포함하는 열에 1~9까지 숫자가 단 한번씩만 존재해야함

3. 빈칸을 포함하는 정사각형(3X3)에 1~9까지 숫자가 단 한번씩만 존재해야함

 

(단계 1). 현재 빈칸에 대해 1~9까지 차례대로 위 조건을 검사,

            모든 빈칸이 채워졌다면 단계 4로 이동

(단계 2). 검사 도중 숫자 x가 위의 세 조건을 모두 만족한다면 다음 빈칸으로 이동 후 (단계 1)진행

(단계 3). 현재 빈칸에서 어떤 숫자도 만족 할 수 없다면 전 빈칸으로 이동 후 x+1~9에 대해 (단계 1)진행

(단계 4). 완성된 스도쿠 출력 후 종료

 

소스 코드

---

#include <iostream>
#include <vector>
#include <utility>

using namespace std;
vector<pair<int, int>> blank;
int sudoku[9][9] = {0};

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

int check1(int num, int row) { //행 지정
	for (int i = 0; i < 9; i++) {
		if (sudoku[row][i] == num) { //열 검사
			return 0;
		}
	}
	return 1;
}

int check2(int num, int col) {  //열 지정
	for (int i = 0; i < 9; i++) {
		if (sudoku[i][col] == num) { //열 검사
			return 0;
		}
	}
	return 1;
}

int check3(int num, int row, int col) { // 행,열
	int x = row / 3;
	int y = col / 3;
	x = x * 3;
	y = y * 3;
	for (int i = x; i < x + 3; i++) {
		for (int j = y; j < y + 3; j++) {
			if (sudoku[i][j] == num) { // 3X3박스 검사
				return 0;
			}
		}
	}
	return 1;
}

void solve_sudoku(int cnt) {
	if (cnt == blank.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << sudoku[i][j] << " ";
			}
			cout << "\n";
		}
		exit(0);
	}
	else {
		for (int i = 1; i <= 9; i++) { //빈칸을 채워넣을 숫자
			int x = blank[cnt].first;
			int y = blank[cnt].second;
			if (check1(i, x) * check2(i, y) * check3(i, x, y) == 1) { //조건을 모두 만족할때
				sudoku[x][y] = i;
				solve_sudoku(cnt + 1);
				sudoku[x][y] = 0;
			}
		}
	}
}

int main() {
	make_sudoku();
	solve_sudoku(0);
}

개발 환경 : VS 2019

질문, 지적 환영입니다.